1 /* Variable tracking routines for the GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA. */
20
21 /* This file contains the variable tracking pass. It computes where
22 variables are located (which registers or where in memory) at each position
23 in instruction stream and emits notes describing the locations.
24 Debug information (DWARF2 location lists) is finally generated from
25 these notes.
26 With this debug information, it is possible to show variables
27 even when debugging optimized code.
28
29 How does the variable tracking pass work?
30
31 First, it scans RTL code for uses, stores and clobbers (register/memory
32 references in instructions), for call insns and for stack adjustments
33 separately for each basic block and saves them to an array of micro
34 operations.
35 The micro operations of one instruction are ordered so that
36 pre-modifying stack adjustment < use < use with no var < call insn <
37 < set < clobber < post-modifying stack adjustment
38
39 Then, a forward dataflow analysis is performed to find out how locations
40 of variables change through code and to propagate the variable locations
41 along control flow graph.
42 The IN set for basic block BB is computed as a union of OUT sets of BB's
43 predecessors, the OUT set for BB is copied from the IN set for BB and
44 is changed according to micro operations in BB.
45
46 The IN and OUT sets for basic blocks consist of a current stack adjustment
47 (used for adjusting offset of variables addressed using stack pointer),
48 the table of structures describing the locations of parts of a variable
49 and for each physical register a linked list for each physical register.
50 The linked list is a list of variable parts stored in the register,
51 i.e. it is a list of triplets (reg, decl, offset) where decl is
52 REG_EXPR (reg) and offset is REG_OFFSET (reg). The linked list is used for
53 effective deleting appropriate variable parts when we set or clobber the
54 register.
55
56 There may be more than one variable part in a register. The linked lists
57 should be pretty short so it is a good data structure here.
58 For example in the following code, register allocator may assign same
59 register to variables A and B, and both of them are stored in the same
60 register in CODE:
61
62 if (cond)
63 set A;
64 else
65 set B;
66 CODE;
67 if (cond)
68 use A;
69 else
70 use B;
71
72 Finally, the NOTE_INSN_VAR_LOCATION notes describing the variable locations
73 are emitted to appropriate positions in RTL code. Each such a note describes
74 the location of one variable at the point in instruction stream where the
75 note is. There is no need to emit a note for each variable before each
76 instruction, we only emit these notes where the location of variable changes
77 (this means that we also emit notes for changes between the OUT set of the
78 previous block and the IN set of the current block).
79
80 The notes consist of two parts:
81 1. the declaration (from REG_EXPR or MEM_EXPR)
82 2. the location of a variable - it is either a simple register/memory
83 reference (for simple variables, for example int),
84 or a parallel of register/memory references (for a large variables
85 which consist of several parts, for example long long).
86
87 */
88
89 #include "config.h"
90 #include "system.h"
91 #include "coretypes.h"
92 #include "tm.h"
93 #include "rtl.h"
94 #include "tree.h"
95 #include "hard-reg-set.h"
96 #include "basic-block.h"
97 #include "flags.h"
98 #include "output.h"
99 #include "insn-config.h"
100 #include "reload.h"
101 #include "sbitmap.h"
102 #include "alloc-pool.h"
103 #include "fibheap.h"
104 #include "hashtab.h"
105 #include "regs.h"
106 #include "expr.h"
107 #include "timevar.h"
108 #include "tree-pass.h"
109
110 /* Type of micro operation. */
111 enum micro_operation_type
112 {
113 MO_USE, /* Use location (REG or MEM). */
114 MO_USE_NO_VAR,/* Use location which is not associated with a variable
115 or the variable is not trackable. */
116 MO_SET, /* Set location. */
117 MO_COPY, /* Copy the same portion of a variable from one
118 location to another. */
119 MO_CLOBBER, /* Clobber location. */
120 MO_CALL, /* Call insn. */
121 MO_ADJUST /* Adjust stack pointer. */
122 };
123
124 /* Where shall the note be emitted? BEFORE or AFTER the instruction. */
125 enum emit_note_where
126 {
127 EMIT_NOTE_BEFORE_INSN,
128 EMIT_NOTE_AFTER_INSN
129 };
130
131 /* Structure holding information about micro operation. */
132 typedef struct micro_operation_def
133 {
134 /* Type of micro operation. */
135 enum micro_operation_type type;
136
137 union {
138 /* Location. */
139 rtx loc;
140
141 /* Stack adjustment. */
142 HOST_WIDE_INT adjust;
143 } u;
144
145 /* The instruction which the micro operation is in, for MO_USE,
146 MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent
147 instruction or note in the original flow (before any var-tracking
148 notes are inserted, to simplify emission of notes), for MO_SET
149 and MO_CLOBBER. */
150 rtx insn;
151 } micro_operation;
152
153 /* Structure for passing some other parameters to function
154 emit_note_insn_var_location. */
155 typedef struct emit_note_data_def
156 {
157 /* The instruction which the note will be emitted before/after. */
158 rtx insn;
159
160 /* Where the note will be emitted (before/after insn)? */
161 enum emit_note_where where;
162 } emit_note_data;
163
164 /* Description of location of a part of a variable. The content of a physical
165 register is described by a chain of these structures.
166 The chains are pretty short (usually 1 or 2 elements) and thus
167 chain is the best data structure. */
168 typedef struct attrs_def
169 {
170 /* Pointer to next member of the list. */
171 struct attrs_def *next;
172
173 /* The rtx of register. */
174 rtx loc;
175
176 /* The declaration corresponding to LOC. */
177 tree decl;
178
179 /* Offset from start of DECL. */
180 HOST_WIDE_INT offset;
181 } *attrs;
182
183 /* Structure holding the IN or OUT set for a basic block. */
184 typedef struct dataflow_set_def
185 {
186 /* Adjustment of stack offset. */
187 HOST_WIDE_INT stack_adjust;
188
189 /* Attributes for registers (lists of attrs). */
190 attrs regs[FIRST_PSEUDO_REGISTER];
191
192 /* Variable locations. */
193 htab_t vars;
194 } dataflow_set;
195
196 /* The structure (one for each basic block) containing the information
197 needed for variable tracking. */
198 typedef struct variable_tracking_info_def
199 {
200 /* Number of micro operations stored in the MOS array. */
201 int n_mos;
202
203 /* The array of micro operations. */
204 micro_operation *mos;
205
206 /* The IN and OUT set for dataflow analysis. */
207 dataflow_set in;
208 dataflow_set out;
209
210 /* Has the block been visited in DFS? */
211 bool visited;
212 } *variable_tracking_info;
213
214 /* Structure for chaining the locations. */
215 typedef struct location_chain_def
216 {
217 /* Next element in the chain. */
218 struct location_chain_def *next;
219
220 /* The location (REG or MEM). */
221 rtx loc;
222 } *location_chain;
223
224 /* Structure describing one part of variable. */
225 typedef struct variable_part_def
226 {
227 /* Chain of locations of the part. */
228 location_chain loc_chain;
229
230 /* Location which was last emitted to location list. */
231 rtx cur_loc;
232
233 /* The offset in the variable. */
234 HOST_WIDE_INT offset;
235 } variable_part;
236
237 /* Maximum number of location parts. */
238 #define MAX_VAR_PARTS 16
239
240 /* Structure describing where the variable is located. */
241 typedef struct variable_def
242 {
243 /* The declaration of the variable. */
244 tree decl;
245
246 /* Reference count. */
247 int refcount;
248
249 /* Number of variable parts. */
250 int n_var_parts;
251
252 /* The variable parts. */
253 variable_part var_part[MAX_VAR_PARTS];
254 } *variable;
255
256 /* Hash function for DECL for VARIABLE_HTAB. */
257 #define VARIABLE_HASH_VAL(decl) (DECL_UID (decl))
258
259 /* Pointer to the BB's information specific to variable tracking pass. */
260 #define VTI(BB) ((variable_tracking_info) (BB)->aux)
261
262 /* Macro to access MEM_OFFSET as an HOST_WIDE_INT. Evaluates MEM twice. */
263 #define INT_MEM_OFFSET(mem) (MEM_OFFSET (mem) ? INTVAL (MEM_OFFSET (mem)) : 0)
264
265 /* Alloc pool for struct attrs_def. */
266 static alloc_pool attrs_pool;
267
268 /* Alloc pool for struct variable_def. */
269 static alloc_pool var_pool;
270
271 /* Alloc pool for struct location_chain_def. */
272 static alloc_pool loc_chain_pool;
273
274 /* Changed variables, notes will be emitted for them. */
275 static htab_t changed_variables;
276
277 /* Shall notes be emitted? */
278 static bool emit_notes;
279
280 /* Local function prototypes. */
281 static void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
282 HOST_WIDE_INT *);
283 static void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
284 HOST_WIDE_INT *);
285 static void bb_stack_adjust_offset (basic_block);
286 static bool vt_stack_adjustments (void);
287 static rtx adjust_stack_reference (rtx, HOST_WIDE_INT);
288 static hashval_t variable_htab_hash (const void *);
289 static int variable_htab_eq (const void *, const void *);
290 static void variable_htab_free (void *);
291
292 static void init_attrs_list_set (attrs *);
293 static void attrs_list_clear (attrs *);
294 static attrs attrs_list_member (attrs, tree, HOST_WIDE_INT);
295 static void attrs_list_insert (attrs *, tree, HOST_WIDE_INT, rtx);
296 static void attrs_list_copy (attrs *, attrs);
297 static void attrs_list_union (attrs *, attrs);
298
299 static void vars_clear (htab_t);
300 static variable unshare_variable (dataflow_set *set, variable var);
301 static int vars_copy_1 (void **, void *);
302 static void vars_copy (htab_t, htab_t);
303 static tree var_debug_decl (tree);
304 static void var_reg_set (dataflow_set *, rtx);
305 static void var_reg_delete_and_set (dataflow_set *, rtx, bool);
306 static void var_reg_delete (dataflow_set *, rtx, bool);
307 static void var_regno_delete (dataflow_set *, int);
308 static void var_mem_set (dataflow_set *, rtx);
309 static void var_mem_delete_and_set (dataflow_set *, rtx, bool);
310 static void var_mem_delete (dataflow_set *, rtx, bool);
311
312 static void dataflow_set_init (dataflow_set *, int);
313 static void dataflow_set_clear (dataflow_set *);
314 static void dataflow_set_copy (dataflow_set *, dataflow_set *);
315 static int variable_union_info_cmp_pos (const void *, const void *);
316 static int variable_union (void **, void *);
317 static void dataflow_set_union (dataflow_set *, dataflow_set *);
318 static bool variable_part_different_p (variable_part *, variable_part *);
319 static bool variable_different_p (variable, variable, bool);
320 static int dataflow_set_different_1 (void **, void *);
321 static int dataflow_set_different_2 (void **, void *);
322 static bool dataflow_set_different (dataflow_set *, dataflow_set *);
323 static void dataflow_set_destroy (dataflow_set *);
324
325 static bool contains_symbol_ref (rtx);
326 static bool track_expr_p (tree);
327 static bool same_variable_part_p (rtx, tree, HOST_WIDE_INT);
328 static int count_uses (rtx *, void *);
329 static void count_uses_1 (rtx *, void *);
330 static void count_stores (rtx, rtx, void *);
331 static int add_uses (rtx *, void *);
332 static void add_uses_1 (rtx *, void *);
333 static void add_stores (rtx, rtx, void *);
334 static bool compute_bb_dataflow (basic_block);
335 static void vt_find_locations (void);
336
337 static void dump_attrs_list (attrs);
338 static int dump_variable (void **, void *);
339 static void dump_vars (htab_t);
340 static void dump_dataflow_set (dataflow_set *);
341 static void dump_dataflow_sets (void);
342
343 static void variable_was_changed (variable, htab_t);
344 static void set_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
345 static void clobber_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
346 static void delete_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
347 static int emit_note_insn_var_location (void **, void *);
348 static void emit_notes_for_changes (rtx, enum emit_note_where);
349 static int emit_notes_for_differences_1 (void **, void *);
350 static int emit_notes_for_differences_2 (void **, void *);
351 static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
352 static void emit_notes_in_bb (basic_block);
353 static void vt_emit_notes (void);
354
355 static bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *);
356 static void vt_add_function_parameters (void);
357 static void vt_initialize (void);
358 static void vt_finalize (void);
359
360 /* Given a SET, calculate the amount of stack adjustment it contains
361 PRE- and POST-modifying stack pointer.
362 This function is similar to stack_adjust_offset. */
363
364 static void
stack_adjust_offset_pre_post(rtx pattern,HOST_WIDE_INT * pre,HOST_WIDE_INT * post)365 stack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre,
366 HOST_WIDE_INT *post)
367 {
368 rtx src = SET_SRC (pattern);
369 rtx dest = SET_DEST (pattern);
370 enum rtx_code code;
371
372 if (dest == stack_pointer_rtx)
373 {
374 /* (set (reg sp) (plus (reg sp) (const_int))) */
375 code = GET_CODE (src);
376 if (! (code == PLUS || code == MINUS)
377 || XEXP (src, 0) != stack_pointer_rtx
378 || GET_CODE (XEXP (src, 1)) != CONST_INT)
379 return;
380
381 if (code == MINUS)
382 *post += INTVAL (XEXP (src, 1));
383 else
384 *post -= INTVAL (XEXP (src, 1));
385 }
386 else if (MEM_P (dest))
387 {
388 /* (set (mem (pre_dec (reg sp))) (foo)) */
389 src = XEXP (dest, 0);
390 code = GET_CODE (src);
391
392 switch (code)
393 {
394 case PRE_MODIFY:
395 case POST_MODIFY:
396 if (XEXP (src, 0) == stack_pointer_rtx)
397 {
398 rtx val = XEXP (XEXP (src, 1), 1);
399 /* We handle only adjustments by constant amount. */
400 gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS &&
401 GET_CODE (val) == CONST_INT);
402
403 if (code == PRE_MODIFY)
404 *pre -= INTVAL (val);
405 else
406 *post -= INTVAL (val);
407 break;
408 }
409 return;
410
411 case PRE_DEC:
412 if (XEXP (src, 0) == stack_pointer_rtx)
413 {
414 *pre += GET_MODE_SIZE (GET_MODE (dest));
415 break;
416 }
417 return;
418
419 case POST_DEC:
420 if (XEXP (src, 0) == stack_pointer_rtx)
421 {
422 *post += GET_MODE_SIZE (GET_MODE (dest));
423 break;
424 }
425 return;
426
427 case PRE_INC:
428 if (XEXP (src, 0) == stack_pointer_rtx)
429 {
430 *pre -= GET_MODE_SIZE (GET_MODE (dest));
431 break;
432 }
433 return;
434
435 case POST_INC:
436 if (XEXP (src, 0) == stack_pointer_rtx)
437 {
438 *post -= GET_MODE_SIZE (GET_MODE (dest));
439 break;
440 }
441 return;
442
443 default:
444 return;
445 }
446 }
447 }
448
449 /* Given an INSN, calculate the amount of stack adjustment it contains
450 PRE- and POST-modifying stack pointer. */
451
452 static void
insn_stack_adjust_offset_pre_post(rtx insn,HOST_WIDE_INT * pre,HOST_WIDE_INT * post)453 insn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre,
454 HOST_WIDE_INT *post)
455 {
456 *pre = 0;
457 *post = 0;
458
459 if (GET_CODE (PATTERN (insn)) == SET)
460 stack_adjust_offset_pre_post (PATTERN (insn), pre, post);
461 else if (GET_CODE (PATTERN (insn)) == PARALLEL
462 || GET_CODE (PATTERN (insn)) == SEQUENCE)
463 {
464 int i;
465
466 /* There may be stack adjustments inside compound insns. Search
467 for them. */
468 for ( i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
469 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
470 stack_adjust_offset_pre_post (XVECEXP (PATTERN (insn), 0, i),
471 pre, post);
472 }
473 }
474
475 /* Compute stack adjustment in basic block BB. */
476
477 static void
bb_stack_adjust_offset(basic_block bb)478 bb_stack_adjust_offset (basic_block bb)
479 {
480 HOST_WIDE_INT offset;
481 int i;
482
483 offset = VTI (bb)->in.stack_adjust;
484 for (i = 0; i < VTI (bb)->n_mos; i++)
485 {
486 if (VTI (bb)->mos[i].type == MO_ADJUST)
487 offset += VTI (bb)->mos[i].u.adjust;
488 else if (VTI (bb)->mos[i].type != MO_CALL)
489 {
490 if (MEM_P (VTI (bb)->mos[i].u.loc))
491 {
492 VTI (bb)->mos[i].u.loc
493 = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset);
494 }
495 }
496 }
497 VTI (bb)->out.stack_adjust = offset;
498 }
499
500 /* Compute stack adjustments for all blocks by traversing DFS tree.
501 Return true when the adjustments on all incoming edges are consistent.
502 Heavily borrowed from pre_and_rev_post_order_compute. */
503
504 static bool
vt_stack_adjustments(void)505 vt_stack_adjustments (void)
506 {
507 edge_iterator *stack;
508 int sp;
509
510 /* Initialize entry block. */
511 VTI (ENTRY_BLOCK_PTR)->visited = true;
512 VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET;
513
514 /* Allocate stack for back-tracking up CFG. */
515 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
516 sp = 0;
517
518 /* Push the first edge on to the stack. */
519 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
520
521 while (sp)
522 {
523 edge_iterator ei;
524 basic_block src;
525 basic_block dest;
526
527 /* Look at the edge on the top of the stack. */
528 ei = stack[sp - 1];
529 src = ei_edge (ei)->src;
530 dest = ei_edge (ei)->dest;
531
532 /* Check if the edge destination has been visited yet. */
533 if (!VTI (dest)->visited)
534 {
535 VTI (dest)->visited = true;
536 VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust;
537 bb_stack_adjust_offset (dest);
538
539 if (EDGE_COUNT (dest->succs) > 0)
540 /* Since the DEST node has been visited for the first
541 time, check its successors. */
542 stack[sp++] = ei_start (dest->succs);
543 }
544 else
545 {
546 /* Check whether the adjustments on the edges are the same. */
547 if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust)
548 {
549 free (stack);
550 return false;
551 }
552
553 if (! ei_one_before_end_p (ei))
554 /* Go to the next edge. */
555 ei_next (&stack[sp - 1]);
556 else
557 /* Return to previous level if there are no more edges. */
558 sp--;
559 }
560 }
561
562 free (stack);
563 return true;
564 }
565
566 /* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative
567 to the argument pointer. Return the new rtx. */
568
569 static rtx
adjust_stack_reference(rtx mem,HOST_WIDE_INT adjustment)570 adjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment)
571 {
572 rtx addr, cfa, tmp;
573
574 #ifdef FRAME_POINTER_CFA_OFFSET
575 adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl);
576 cfa = plus_constant (frame_pointer_rtx, adjustment);
577 #else
578 adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl);
579 cfa = plus_constant (arg_pointer_rtx, adjustment);
580 #endif
581
582 addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa);
583 tmp = simplify_rtx (addr);
584 if (tmp)
585 addr = tmp;
586
587 return replace_equiv_address_nv (mem, addr);
588 }
589
590 /* The hash function for variable_htab, computes the hash value
591 from the declaration of variable X. */
592
593 static hashval_t
variable_htab_hash(const void * x)594 variable_htab_hash (const void *x)
595 {
596 const variable v = (const variable) x;
597
598 return (VARIABLE_HASH_VAL (v->decl));
599 }
600
601 /* Compare the declaration of variable X with declaration Y. */
602
603 static int
variable_htab_eq(const void * x,const void * y)604 variable_htab_eq (const void *x, const void *y)
605 {
606 const variable v = (const variable) x;
607 const tree decl = (const tree) y;
608
609 return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl));
610 }
611
612 /* Free the element of VARIABLE_HTAB (its type is struct variable_def). */
613
614 static void
variable_htab_free(void * elem)615 variable_htab_free (void *elem)
616 {
617 int i;
618 variable var = (variable) elem;
619 location_chain node, next;
620
621 gcc_assert (var->refcount > 0);
622
623 var->refcount--;
624 if (var->refcount > 0)
625 return;
626
627 for (i = 0; i < var->n_var_parts; i++)
628 {
629 for (node = var->var_part[i].loc_chain; node; node = next)
630 {
631 next = node->next;
632 pool_free (loc_chain_pool, node);
633 }
634 var->var_part[i].loc_chain = NULL;
635 }
636 pool_free (var_pool, var);
637 }
638
639 /* Initialize the set (array) SET of attrs to empty lists. */
640
641 static void
init_attrs_list_set(attrs * set)642 init_attrs_list_set (attrs *set)
643 {
644 int i;
645
646 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
647 set[i] = NULL;
648 }
649
650 /* Make the list *LISTP empty. */
651
652 static void
attrs_list_clear(attrs * listp)653 attrs_list_clear (attrs *listp)
654 {
655 attrs list, next;
656
657 for (list = *listp; list; list = next)
658 {
659 next = list->next;
660 pool_free (attrs_pool, list);
661 }
662 *listp = NULL;
663 }
664
665 /* Return true if the pair of DECL and OFFSET is the member of the LIST. */
666
667 static attrs
attrs_list_member(attrs list,tree decl,HOST_WIDE_INT offset)668 attrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset)
669 {
670 for (; list; list = list->next)
671 if (list->decl == decl && list->offset == offset)
672 return list;
673 return NULL;
674 }
675
676 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP. */
677
678 static void
attrs_list_insert(attrs * listp,tree decl,HOST_WIDE_INT offset,rtx loc)679 attrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc)
680 {
681 attrs list;
682
683 list = pool_alloc (attrs_pool);
684 list->loc = loc;
685 list->decl = decl;
686 list->offset = offset;
687 list->next = *listp;
688 *listp = list;
689 }
690
691 /* Copy all nodes from SRC and create a list *DSTP of the copies. */
692
693 static void
attrs_list_copy(attrs * dstp,attrs src)694 attrs_list_copy (attrs *dstp, attrs src)
695 {
696 attrs n;
697
698 attrs_list_clear (dstp);
699 for (; src; src = src->next)
700 {
701 n = pool_alloc (attrs_pool);
702 n->loc = src->loc;
703 n->decl = src->decl;
704 n->offset = src->offset;
705 n->next = *dstp;
706 *dstp = n;
707 }
708 }
709
710 /* Add all nodes from SRC which are not in *DSTP to *DSTP. */
711
712 static void
attrs_list_union(attrs * dstp,attrs src)713 attrs_list_union (attrs *dstp, attrs src)
714 {
715 for (; src; src = src->next)
716 {
717 if (!attrs_list_member (*dstp, src->decl, src->offset))
718 attrs_list_insert (dstp, src->decl, src->offset, src->loc);
719 }
720 }
721
722 /* Delete all variables from hash table VARS. */
723
724 static void
vars_clear(htab_t vars)725 vars_clear (htab_t vars)
726 {
727 htab_empty (vars);
728 }
729
730 /* Return a copy of a variable VAR and insert it to dataflow set SET. */
731
732 static variable
unshare_variable(dataflow_set * set,variable var)733 unshare_variable (dataflow_set *set, variable var)
734 {
735 void **slot;
736 variable new_var;
737 int i;
738
739 new_var = pool_alloc (var_pool);
740 new_var->decl = var->decl;
741 new_var->refcount = 1;
742 var->refcount--;
743 new_var->n_var_parts = var->n_var_parts;
744
745 for (i = 0; i < var->n_var_parts; i++)
746 {
747 location_chain node;
748 location_chain *nextp;
749
750 new_var->var_part[i].offset = var->var_part[i].offset;
751 nextp = &new_var->var_part[i].loc_chain;
752 for (node = var->var_part[i].loc_chain; node; node = node->next)
753 {
754 location_chain new_lc;
755
756 new_lc = pool_alloc (loc_chain_pool);
757 new_lc->next = NULL;
758 new_lc->loc = node->loc;
759
760 *nextp = new_lc;
761 nextp = &new_lc->next;
762 }
763
764 /* We are at the basic block boundary when copying variable description
765 so set the CUR_LOC to be the first element of the chain. */
766 if (new_var->var_part[i].loc_chain)
767 new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
768 else
769 new_var->var_part[i].cur_loc = NULL;
770 }
771
772 slot = htab_find_slot_with_hash (set->vars, new_var->decl,
773 VARIABLE_HASH_VAL (new_var->decl),
774 INSERT);
775 *slot = new_var;
776 return new_var;
777 }
778
779 /* Add a variable from *SLOT to hash table DATA and increase its reference
780 count. */
781
782 static int
vars_copy_1(void ** slot,void * data)783 vars_copy_1 (void **slot, void *data)
784 {
785 htab_t dst = (htab_t) data;
786 variable src, *dstp;
787
788 src = *(variable *) slot;
789 src->refcount++;
790
791 dstp = (variable *) htab_find_slot_with_hash (dst, src->decl,
792 VARIABLE_HASH_VAL (src->decl),
793 INSERT);
794 *dstp = src;
795
796 /* Continue traversing the hash table. */
797 return 1;
798 }
799
800 /* Copy all variables from hash table SRC to hash table DST. */
801
802 static void
vars_copy(htab_t dst,htab_t src)803 vars_copy (htab_t dst, htab_t src)
804 {
805 vars_clear (dst);
806 htab_traverse (src, vars_copy_1, dst);
807 }
808
809 /* Map a decl to its main debug decl. */
810
811 static inline tree
var_debug_decl(tree decl)812 var_debug_decl (tree decl)
813 {
814 if (decl && DECL_P (decl)
815 && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl)
816 && DECL_P (DECL_DEBUG_EXPR (decl)))
817 decl = DECL_DEBUG_EXPR (decl);
818
819 return decl;
820 }
821
822 /* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). */
823
824 static void
var_reg_set(dataflow_set * set,rtx loc)825 var_reg_set (dataflow_set *set, rtx loc)
826 {
827 tree decl = REG_EXPR (loc);
828 HOST_WIDE_INT offset = REG_OFFSET (loc);
829 attrs node;
830
831 decl = var_debug_decl (decl);
832
833 for (node = set->regs[REGNO (loc)]; node; node = node->next)
834 if (node->decl == decl && node->offset == offset)
835 break;
836 if (!node)
837 attrs_list_insert (&set->regs[REGNO (loc)], decl, offset, loc);
838 set_variable_part (set, loc, decl, offset);
839 }
840
841 /* Delete current content of register LOC in dataflow set SET and set
842 the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). If
843 MODIFY is true, any other live copies of the same variable part are
844 also deleted from the dataflow set, otherwise the variable part is
845 assumed to be copied from another location holding the same
846 part. */
847
848 static void
var_reg_delete_and_set(dataflow_set * set,rtx loc,bool modify)849 var_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify)
850 {
851 tree decl = REG_EXPR (loc);
852 HOST_WIDE_INT offset = REG_OFFSET (loc);
853 attrs node, next;
854 attrs *nextp;
855
856 decl = var_debug_decl (decl);
857
858 nextp = &set->regs[REGNO (loc)];
859 for (node = *nextp; node; node = next)
860 {
861 next = node->next;
862 if (node->decl != decl || node->offset != offset)
863 {
864 delete_variable_part (set, node->loc, node->decl, node->offset);
865 pool_free (attrs_pool, node);
866 *nextp = next;
867 }
868 else
869 {
870 node->loc = loc;
871 nextp = &node->next;
872 }
873 }
874 if (modify)
875 clobber_variable_part (set, loc, decl, offset);
876 var_reg_set (set, loc);
877 }
878
879 /* Delete current content of register LOC in dataflow set SET. If
880 CLOBBER is true, also delete any other live copies of the same
881 variable part. */
882
883 static void
var_reg_delete(dataflow_set * set,rtx loc,bool clobber)884 var_reg_delete (dataflow_set *set, rtx loc, bool clobber)
885 {
886 attrs *reg = &set->regs[REGNO (loc)];
887 attrs node, next;
888
889 if (clobber)
890 {
891 tree decl = REG_EXPR (loc);
892 HOST_WIDE_INT offset = REG_OFFSET (loc);
893
894 decl = var_debug_decl (decl);
895
896 clobber_variable_part (set, NULL, decl, offset);
897 }
898
899 for (node = *reg; node; node = next)
900 {
901 next = node->next;
902 delete_variable_part (set, node->loc, node->decl, node->offset);
903 pool_free (attrs_pool, node);
904 }
905 *reg = NULL;
906 }
907
908 /* Delete content of register with number REGNO in dataflow set SET. */
909
910 static void
var_regno_delete(dataflow_set * set,int regno)911 var_regno_delete (dataflow_set *set, int regno)
912 {
913 attrs *reg = &set->regs[regno];
914 attrs node, next;
915
916 for (node = *reg; node; node = next)
917 {
918 next = node->next;
919 delete_variable_part (set, node->loc, node->decl, node->offset);
920 pool_free (attrs_pool, node);
921 }
922 *reg = NULL;
923 }
924
925 /* Set the location part of variable MEM_EXPR (LOC) in dataflow set
926 SET to LOC.
927 Adjust the address first if it is stack pointer based. */
928
929 static void
var_mem_set(dataflow_set * set,rtx loc)930 var_mem_set (dataflow_set *set, rtx loc)
931 {
932 tree decl = MEM_EXPR (loc);
933 HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
934
935 decl = var_debug_decl (decl);
936
937 set_variable_part (set, loc, decl, offset);
938 }
939
940 /* Delete and set the location part of variable MEM_EXPR (LOC) in
941 dataflow set SET to LOC. If MODIFY is true, any other live copies
942 of the same variable part are also deleted from the dataflow set,
943 otherwise the variable part is assumed to be copied from another
944 location holding the same part.
945 Adjust the address first if it is stack pointer based. */
946
947 static void
var_mem_delete_and_set(dataflow_set * set,rtx loc,bool modify)948 var_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify)
949 {
950 tree decl = MEM_EXPR (loc);
951 HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
952
953 decl = var_debug_decl (decl);
954
955 if (modify)
956 clobber_variable_part (set, NULL, decl, offset);
957 var_mem_set (set, loc);
958 }
959
960 /* Delete the location part LOC from dataflow set SET. If CLOBBER is
961 true, also delete any other live copies of the same variable part.
962 Adjust the address first if it is stack pointer based. */
963
964 static void
var_mem_delete(dataflow_set * set,rtx loc,bool clobber)965 var_mem_delete (dataflow_set *set, rtx loc, bool clobber)
966 {
967 tree decl = MEM_EXPR (loc);
968 HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
969
970 decl = var_debug_decl (decl);
971 if (clobber)
972 clobber_variable_part (set, NULL, decl, offset);
973 delete_variable_part (set, loc, decl, offset);
974 }
975
976 /* Initialize dataflow set SET to be empty.
977 VARS_SIZE is the initial size of hash table VARS. */
978
979 static void
dataflow_set_init(dataflow_set * set,int vars_size)980 dataflow_set_init (dataflow_set *set, int vars_size)
981 {
982 init_attrs_list_set (set->regs);
983 set->vars = htab_create (vars_size, variable_htab_hash, variable_htab_eq,
984 variable_htab_free);
985 set->stack_adjust = 0;
986 }
987
988 /* Delete the contents of dataflow set SET. */
989
990 static void
dataflow_set_clear(dataflow_set * set)991 dataflow_set_clear (dataflow_set *set)
992 {
993 int i;
994
995 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
996 attrs_list_clear (&set->regs[i]);
997
998 vars_clear (set->vars);
999 }
1000
1001 /* Copy the contents of dataflow set SRC to DST. */
1002
1003 static void
dataflow_set_copy(dataflow_set * dst,dataflow_set * src)1004 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
1005 {
1006 int i;
1007
1008 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1009 attrs_list_copy (&dst->regs[i], src->regs[i]);
1010
1011 vars_copy (dst->vars, src->vars);
1012 dst->stack_adjust = src->stack_adjust;
1013 }
1014
1015 /* Information for merging lists of locations for a given offset of variable.
1016 */
1017 struct variable_union_info
1018 {
1019 /* Node of the location chain. */
1020 location_chain lc;
1021
1022 /* The sum of positions in the input chains. */
1023 int pos;
1024
1025 /* The position in the chains of SRC and DST dataflow sets. */
1026 int pos_src;
1027 int pos_dst;
1028 };
1029
1030 /* Compare function for qsort, order the structures by POS element. */
1031
1032 static int
variable_union_info_cmp_pos(const void * n1,const void * n2)1033 variable_union_info_cmp_pos (const void *n1, const void *n2)
1034 {
1035 const struct variable_union_info *i1 = n1;
1036 const struct variable_union_info *i2 = n2;
1037
1038 if (i1->pos != i2->pos)
1039 return i1->pos - i2->pos;
1040
1041 return (i1->pos_dst - i2->pos_dst);
1042 }
1043
1044 /* Compute union of location parts of variable *SLOT and the same variable
1045 from hash table DATA. Compute "sorted" union of the location chains
1046 for common offsets, i.e. the locations of a variable part are sorted by
1047 a priority where the priority is the sum of the positions in the 2 chains
1048 (if a location is only in one list the position in the second list is
1049 defined to be larger than the length of the chains).
1050 When we are updating the location parts the newest location is in the
1051 beginning of the chain, so when we do the described "sorted" union
1052 we keep the newest locations in the beginning. */
1053
1054 static int
variable_union(void ** slot,void * data)1055 variable_union (void **slot, void *data)
1056 {
1057 variable src, dst, *dstp;
1058 dataflow_set *set = (dataflow_set *) data;
1059 int i, j, k;
1060
1061 src = *(variable *) slot;
1062 dstp = (variable *) htab_find_slot_with_hash (set->vars, src->decl,
1063 VARIABLE_HASH_VAL (src->decl),
1064 INSERT);
1065 if (!*dstp)
1066 {
1067 src->refcount++;
1068
1069 /* If CUR_LOC of some variable part is not the first element of
1070 the location chain we are going to change it so we have to make
1071 a copy of the variable. */
1072 for (k = 0; k < src->n_var_parts; k++)
1073 {
1074 gcc_assert (!src->var_part[k].loc_chain
1075 == !src->var_part[k].cur_loc);
1076 if (src->var_part[k].loc_chain)
1077 {
1078 gcc_assert (src->var_part[k].cur_loc);
1079 if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1080 break;
1081 }
1082 }
1083 if (k < src->n_var_parts)
1084 unshare_variable (set, src);
1085 else
1086 *dstp = src;
1087
1088 /* Continue traversing the hash table. */
1089 return 1;
1090 }
1091 else
1092 dst = *dstp;
1093
1094 gcc_assert (src->n_var_parts);
1095
1096 /* Count the number of location parts, result is K. */
1097 for (i = 0, j = 0, k = 0;
1098 i < src->n_var_parts && j < dst->n_var_parts; k++)
1099 {
1100 if (src->var_part[i].offset == dst->var_part[j].offset)
1101 {
1102 i++;
1103 j++;
1104 }
1105 else if (src->var_part[i].offset < dst->var_part[j].offset)
1106 i++;
1107 else
1108 j++;
1109 }
1110 k += src->n_var_parts - i;
1111 k += dst->n_var_parts - j;
1112
1113 /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1114 thus there are at most MAX_VAR_PARTS different offsets. */
1115 gcc_assert (k <= MAX_VAR_PARTS);
1116
1117 if (dst->refcount > 1 && dst->n_var_parts != k)
1118 dst = unshare_variable (set, dst);
1119
1120 i = src->n_var_parts - 1;
1121 j = dst->n_var_parts - 1;
1122 dst->n_var_parts = k;
1123
1124 for (k--; k >= 0; k--)
1125 {
1126 location_chain node, node2;
1127
1128 if (i >= 0 && j >= 0
1129 && src->var_part[i].offset == dst->var_part[j].offset)
1130 {
1131 /* Compute the "sorted" union of the chains, i.e. the locations which
1132 are in both chains go first, they are sorted by the sum of
1133 positions in the chains. */
1134 int dst_l, src_l;
1135 int ii, jj, n;
1136 struct variable_union_info *vui;
1137
1138 /* If DST is shared compare the location chains.
1139 If they are different we will modify the chain in DST with
1140 high probability so make a copy of DST. */
1141 if (dst->refcount > 1)
1142 {
1143 for (node = src->var_part[i].loc_chain,
1144 node2 = dst->var_part[j].loc_chain; node && node2;
1145 node = node->next, node2 = node2->next)
1146 {
1147 if (!((REG_P (node2->loc)
1148 && REG_P (node->loc)
1149 && REGNO (node2->loc) == REGNO (node->loc))
1150 || rtx_equal_p (node2->loc, node->loc)))
1151 break;
1152 }
1153 if (node || node2)
1154 dst = unshare_variable (set, dst);
1155 }
1156
1157 src_l = 0;
1158 for (node = src->var_part[i].loc_chain; node; node = node->next)
1159 src_l++;
1160 dst_l = 0;
1161 for (node = dst->var_part[j].loc_chain; node; node = node->next)
1162 dst_l++;
1163 vui = XCNEWVEC (struct variable_union_info, src_l + dst_l);
1164
1165 /* Fill in the locations from DST. */
1166 for (node = dst->var_part[j].loc_chain, jj = 0; node;
1167 node = node->next, jj++)
1168 {
1169 vui[jj].lc = node;
1170 vui[jj].pos_dst = jj;
1171
1172 /* Value larger than a sum of 2 valid positions. */
1173 vui[jj].pos_src = src_l + dst_l;
1174 }
1175
1176 /* Fill in the locations from SRC. */
1177 n = dst_l;
1178 for (node = src->var_part[i].loc_chain, ii = 0; node;
1179 node = node->next, ii++)
1180 {
1181 /* Find location from NODE. */
1182 for (jj = 0; jj < dst_l; jj++)
1183 {
1184 if ((REG_P (vui[jj].lc->loc)
1185 && REG_P (node->loc)
1186 && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
1187 || rtx_equal_p (vui[jj].lc->loc, node->loc))
1188 {
1189 vui[jj].pos_src = ii;
1190 break;
1191 }
1192 }
1193 if (jj >= dst_l) /* The location has not been found. */
1194 {
1195 location_chain new_node;
1196
1197 /* Copy the location from SRC. */
1198 new_node = pool_alloc (loc_chain_pool);
1199 new_node->loc = node->loc;
1200 vui[n].lc = new_node;
1201 vui[n].pos_src = ii;
1202 vui[n].pos_dst = src_l + dst_l;
1203 n++;
1204 }
1205 }
1206
1207 for (ii = 0; ii < src_l + dst_l; ii++)
1208 vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst;
1209
1210 qsort (vui, n, sizeof (struct variable_union_info),
1211 variable_union_info_cmp_pos);
1212
1213 /* Reconnect the nodes in sorted order. */
1214 for (ii = 1; ii < n; ii++)
1215 vui[ii - 1].lc->next = vui[ii].lc;
1216 vui[n - 1].lc->next = NULL;
1217
1218 dst->var_part[k].loc_chain = vui[0].lc;
1219 dst->var_part[k].offset = dst->var_part[j].offset;
1220
1221 free (vui);
1222 i--;
1223 j--;
1224 }
1225 else if ((i >= 0 && j >= 0
1226 && src->var_part[i].offset < dst->var_part[j].offset)
1227 || i < 0)
1228 {
1229 dst->var_part[k] = dst->var_part[j];
1230 j--;
1231 }
1232 else if ((i >= 0 && j >= 0
1233 && src->var_part[i].offset > dst->var_part[j].offset)
1234 || j < 0)
1235 {
1236 location_chain *nextp;
1237
1238 /* Copy the chain from SRC. */
1239 nextp = &dst->var_part[k].loc_chain;
1240 for (node = src->var_part[i].loc_chain; node; node = node->next)
1241 {
1242 location_chain new_lc;
1243
1244 new_lc = pool_alloc (loc_chain_pool);
1245 new_lc->next = NULL;
1246 new_lc->loc = node->loc;
1247
1248 *nextp = new_lc;
1249 nextp = &new_lc->next;
1250 }
1251
1252 dst->var_part[k].offset = src->var_part[i].offset;
1253 i--;
1254 }
1255
1256 /* We are at the basic block boundary when computing union
1257 so set the CUR_LOC to be the first element of the chain. */
1258 if (dst->var_part[k].loc_chain)
1259 dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
1260 else
1261 dst->var_part[k].cur_loc = NULL;
1262 }
1263
1264 /* Continue traversing the hash table. */
1265 return 1;
1266 }
1267
1268 /* Compute union of dataflow sets SRC and DST and store it to DST. */
1269
1270 static void
dataflow_set_union(dataflow_set * dst,dataflow_set * src)1271 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
1272 {
1273 int i;
1274
1275 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1276 attrs_list_union (&dst->regs[i], src->regs[i]);
1277
1278 htab_traverse (src->vars, variable_union, dst);
1279 }
1280
1281 /* Flag whether two dataflow sets being compared contain different data. */
1282 static bool
1283 dataflow_set_different_value;
1284
1285 static bool
variable_part_different_p(variable_part * vp1,variable_part * vp2)1286 variable_part_different_p (variable_part *vp1, variable_part *vp2)
1287 {
1288 location_chain lc1, lc2;
1289
1290 for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
1291 {
1292 for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
1293 {
1294 if (REG_P (lc1->loc) && REG_P (lc2->loc))
1295 {
1296 if (REGNO (lc1->loc) == REGNO (lc2->loc))
1297 break;
1298 }
1299 if (rtx_equal_p (lc1->loc, lc2->loc))
1300 break;
1301 }
1302 if (!lc2)
1303 return true;
1304 }
1305 return false;
1306 }
1307
1308 /* Return true if variables VAR1 and VAR2 are different.
1309 If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
1310 variable part. */
1311
1312 static bool
variable_different_p(variable var1,variable var2,bool compare_current_location)1313 variable_different_p (variable var1, variable var2,
1314 bool compare_current_location)
1315 {
1316 int i;
1317
1318 if (var1 == var2)
1319 return false;
1320
1321 if (var1->n_var_parts != var2->n_var_parts)
1322 return true;
1323
1324 for (i = 0; i < var1->n_var_parts; i++)
1325 {
1326 if (var1->var_part[i].offset != var2->var_part[i].offset)
1327 return true;
1328 if (compare_current_location)
1329 {
1330 if (!((REG_P (var1->var_part[i].cur_loc)
1331 && REG_P (var2->var_part[i].cur_loc)
1332 && (REGNO (var1->var_part[i].cur_loc)
1333 == REGNO (var2->var_part[i].cur_loc)))
1334 || rtx_equal_p (var1->var_part[i].cur_loc,
1335 var2->var_part[i].cur_loc)))
1336 return true;
1337 }
1338 if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
1339 return true;
1340 if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
1341 return true;
1342 }
1343 return false;
1344 }
1345
1346 /* Compare variable *SLOT with the same variable in hash table DATA
1347 and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */
1348
1349 static int
dataflow_set_different_1(void ** slot,void * data)1350 dataflow_set_different_1 (void **slot, void *data)
1351 {
1352 htab_t htab = (htab_t) data;
1353 variable var1, var2;
1354
1355 var1 = *(variable *) slot;
1356 var2 = htab_find_with_hash (htab, var1->decl,
1357 VARIABLE_HASH_VAL (var1->decl));
1358 if (!var2)
1359 {
1360 dataflow_set_different_value = true;
1361
1362 /* Stop traversing the hash table. */
1363 return 0;
1364 }
1365
1366 if (variable_different_p (var1, var2, false))
1367 {
1368 dataflow_set_different_value = true;
1369
1370 /* Stop traversing the hash table. */
1371 return 0;
1372 }
1373
1374 /* Continue traversing the hash table. */
1375 return 1;
1376 }
1377
1378 /* Compare variable *SLOT with the same variable in hash table DATA
1379 and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */
1380
1381 static int
dataflow_set_different_2(void ** slot,void * data)1382 dataflow_set_different_2 (void **slot, void *data)
1383 {
1384 htab_t htab = (htab_t) data;
1385 variable var1, var2;
1386
1387 var1 = *(variable *) slot;
1388 var2 = htab_find_with_hash (htab, var1->decl,
1389 VARIABLE_HASH_VAL (var1->decl));
1390 if (!var2)
1391 {
1392 dataflow_set_different_value = true;
1393
1394 /* Stop traversing the hash table. */
1395 return 0;
1396 }
1397
1398 /* If both variables are defined they have been already checked for
1399 equivalence. */
1400 gcc_assert (!variable_different_p (var1, var2, false));
1401
1402 /* Continue traversing the hash table. */
1403 return 1;
1404 }
1405
1406 /* Return true if dataflow sets OLD_SET and NEW_SET differ. */
1407
1408 static bool
dataflow_set_different(dataflow_set * old_set,dataflow_set * new_set)1409 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
1410 {
1411 dataflow_set_different_value = false;
1412
1413 htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars);
1414 if (!dataflow_set_different_value)
1415 {
1416 /* We have compared the variables which are in both hash tables
1417 so now only check whether there are some variables in NEW_SET->VARS
1418 which are not in OLD_SET->VARS. */
1419 htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars);
1420 }
1421 return dataflow_set_different_value;
1422 }
1423
1424 /* Free the contents of dataflow set SET. */
1425
1426 static void
dataflow_set_destroy(dataflow_set * set)1427 dataflow_set_destroy (dataflow_set *set)
1428 {
1429 int i;
1430
1431 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1432 attrs_list_clear (&set->regs[i]);
1433
1434 htab_delete (set->vars);
1435 set->vars = NULL;
1436 }
1437
1438 /* Return true if RTL X contains a SYMBOL_REF. */
1439
1440 static bool
contains_symbol_ref(rtx x)1441 contains_symbol_ref (rtx x)
1442 {
1443 const char *fmt;
1444 RTX_CODE code;
1445 int i;
1446
1447 if (!x)
1448 return false;
1449
1450 code = GET_CODE (x);
1451 if (code == SYMBOL_REF)
1452 return true;
1453
1454 fmt = GET_RTX_FORMAT (code);
1455 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1456 {
1457 if (fmt[i] == 'e')
1458 {
1459 if (contains_symbol_ref (XEXP (x, i)))
1460 return true;
1461 }
1462 else if (fmt[i] == 'E')
1463 {
1464 int j;
1465 for (j = 0; j < XVECLEN (x, i); j++)
1466 if (contains_symbol_ref (XVECEXP (x, i, j)))
1467 return true;
1468 }
1469 }
1470
1471 return false;
1472 }
1473
1474 /* Shall EXPR be tracked? */
1475
1476 static bool
track_expr_p(tree expr)1477 track_expr_p (tree expr)
1478 {
1479 rtx decl_rtl;
1480 tree realdecl;
1481
1482 /* If EXPR is not a parameter or a variable do not track it. */
1483 if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
1484 return 0;
1485
1486 /* It also must have a name... */
1487 if (!DECL_NAME (expr))
1488 return 0;
1489
1490 /* ... and a RTL assigned to it. */
1491 decl_rtl = DECL_RTL_IF_SET (expr);
1492 if (!decl_rtl)
1493 return 0;
1494
1495 /* If this expression is really a debug alias of some other declaration, we
1496 don't need to track this expression if the ultimate declaration is
1497 ignored. */
1498 realdecl = expr;
1499 if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
1500 {
1501 realdecl = DECL_DEBUG_EXPR (realdecl);
1502 /* ??? We don't yet know how to emit DW_OP_piece for variable
1503 that has been SRA'ed. */
1504 if (!DECL_P (realdecl))
1505 return 0;
1506 }
1507
1508 /* Do not track EXPR if REALDECL it should be ignored for debugging
1509 purposes. */
1510 if (DECL_IGNORED_P (realdecl))
1511 return 0;
1512
1513 /* Do not track global variables until we are able to emit correct location
1514 list for them. */
1515 if (TREE_STATIC (realdecl))
1516 return 0;
1517
1518 /* When the EXPR is a DECL for alias of some variable (see example)
1519 the TREE_STATIC flag is not used. Disable tracking all DECLs whose
1520 DECL_RTL contains SYMBOL_REF.
1521
1522 Example:
1523 extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
1524 char **_dl_argv;
1525 */
1526 if (MEM_P (decl_rtl)
1527 && contains_symbol_ref (XEXP (decl_rtl, 0)))
1528 return 0;
1529
1530 /* If RTX is a memory it should not be very large (because it would be
1531 an array or struct). */
1532 if (MEM_P (decl_rtl))
1533 {
1534 /* Do not track structures and arrays. */
1535 if (GET_MODE (decl_rtl) == BLKmode
1536 || AGGREGATE_TYPE_P (TREE_TYPE (realdecl)))
1537 return 0;
1538 if (MEM_SIZE (decl_rtl)
1539 && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
1540 return 0;
1541 }
1542
1543 return 1;
1544 }
1545
1546 /* Return true if OFFSET is a valid offset for a register or memory
1547 access we want to track. This is used to reject out-of-bounds
1548 accesses that can cause assertions to fail later. Note that we
1549 don't reject negative offsets because they can be generated for
1550 paradoxical subregs on big-endian architectures. */
1551
1552 static inline bool
offset_valid_for_tracked_p(HOST_WIDE_INT offset)1553 offset_valid_for_tracked_p (HOST_WIDE_INT offset)
1554 {
1555 return (-MAX_VAR_PARTS < offset) && (offset < MAX_VAR_PARTS);
1556 }
1557
1558 /* Determine whether a given LOC refers to the same variable part as
1559 EXPR+OFFSET. */
1560
1561 static bool
same_variable_part_p(rtx loc,tree expr,HOST_WIDE_INT offset)1562 same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset)
1563 {
1564 tree expr2;
1565 HOST_WIDE_INT offset2;
1566
1567 if (! DECL_P (expr))
1568 return false;
1569
1570 if (REG_P (loc))
1571 {
1572 expr2 = REG_EXPR (loc);
1573 offset2 = REG_OFFSET (loc);
1574 }
1575 else if (MEM_P (loc))
1576 {
1577 expr2 = MEM_EXPR (loc);
1578 offset2 = INT_MEM_OFFSET (loc);
1579 }
1580 else
1581 return false;
1582
1583 if (! expr2 || ! DECL_P (expr2))
1584 return false;
1585
1586 expr = var_debug_decl (expr);
1587 expr2 = var_debug_decl (expr2);
1588
1589 return (expr == expr2 && offset == offset2);
1590 }
1591
1592
1593 /* Count uses (register and memory references) LOC which will be tracked.
1594 INSN is instruction which the LOC is part of. */
1595
1596 static int
count_uses(rtx * loc,void * insn)1597 count_uses (rtx *loc, void *insn)
1598 {
1599 basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1600
1601 if (REG_P (*loc))
1602 {
1603 gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER);
1604 VTI (bb)->n_mos++;
1605 }
1606 else if (MEM_P (*loc)
1607 && MEM_EXPR (*loc)
1608 && track_expr_p (MEM_EXPR (*loc))
1609 && offset_valid_for_tracked_p (INT_MEM_OFFSET (*loc)))
1610 {
1611 VTI (bb)->n_mos++;
1612 }
1613
1614 return 0;
1615 }
1616
1617 /* Helper function for finding all uses of REG/MEM in X in insn INSN. */
1618
1619 static void
count_uses_1(rtx * x,void * insn)1620 count_uses_1 (rtx *x, void *insn)
1621 {
1622 for_each_rtx (x, count_uses, insn);
1623 }
1624
1625 /* Count stores (register and memory references) LOC which will be tracked.
1626 INSN is instruction which the LOC is part of. */
1627
1628 static void
count_stores(rtx loc,rtx expr ATTRIBUTE_UNUSED,void * insn)1629 count_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn)
1630 {
1631 count_uses (&loc, insn);
1632 }
1633
1634 /* Add uses (register and memory references) LOC which will be tracked
1635 to VTI (bb)->mos. INSN is instruction which the LOC is part of. */
1636
1637 static int
add_uses(rtx * loc,void * insn)1638 add_uses (rtx *loc, void *insn)
1639 {
1640 if (REG_P (*loc))
1641 {
1642 basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1643 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1644
1645 if (REG_EXPR (*loc)
1646 && track_expr_p (REG_EXPR (*loc))
1647 && offset_valid_for_tracked_p (REG_OFFSET (*loc)))
1648 mo->type = MO_USE;
1649 else
1650 mo->type = MO_USE_NO_VAR;
1651 mo->u.loc = *loc;
1652 mo->insn = (rtx) insn;
1653 }
1654 else if (MEM_P (*loc)
1655 && MEM_EXPR (*loc)
1656 && track_expr_p (MEM_EXPR (*loc))
1657 && offset_valid_for_tracked_p (INT_MEM_OFFSET (*loc)))
1658 {
1659 basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1660 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1661
1662 mo->type = MO_USE;
1663 mo->u.loc = *loc;
1664 mo->insn = (rtx) insn;
1665 }
1666
1667 return 0;
1668 }
1669
1670 /* Helper function for finding all uses of REG/MEM in X in insn INSN. */
1671
1672 static void
add_uses_1(rtx * x,void * insn)1673 add_uses_1 (rtx *x, void *insn)
1674 {
1675 for_each_rtx (x, add_uses, insn);
1676 }
1677
1678 /* Add stores (register and memory references) LOC which will be tracked
1679 to VTI (bb)->mos. EXPR is the RTL expression containing the store.
1680 INSN is instruction which the LOC is part of. */
1681
1682 static void
add_stores(rtx loc,rtx expr,void * insn)1683 add_stores (rtx loc, rtx expr, void *insn)
1684 {
1685 if (REG_P (loc))
1686 {
1687 basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1688 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1689
1690 if (GET_CODE (expr) == CLOBBER
1691 || !(REG_EXPR (loc)
1692 && track_expr_p (REG_EXPR (loc))
1693 && offset_valid_for_tracked_p (REG_OFFSET (loc))))
1694 mo->type = MO_CLOBBER;
1695 else if (GET_CODE (expr) == SET
1696 && SET_DEST (expr) == loc
1697 && same_variable_part_p (SET_SRC (expr),
1698 REG_EXPR (loc),
1699 REG_OFFSET (loc)))
1700 mo->type = MO_COPY;
1701 else
1702 mo->type = MO_SET;
1703 mo->u.loc = loc;
1704 mo->insn = NEXT_INSN ((rtx) insn);
1705 }
1706 else if (MEM_P (loc)
1707 && MEM_EXPR (loc)
1708 && track_expr_p (MEM_EXPR (loc))
1709 && offset_valid_for_tracked_p (INT_MEM_OFFSET (loc)))
1710 {
1711 basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1712 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1713
1714 if (GET_CODE (expr) == CLOBBER)
1715 mo->type = MO_CLOBBER;
1716 else if (GET_CODE (expr) == SET
1717 && SET_DEST (expr) == loc
1718 && same_variable_part_p (SET_SRC (expr),
1719 MEM_EXPR (loc),
1720 INT_MEM_OFFSET (loc)))
1721 mo->type = MO_COPY;
1722 else
1723 mo->type = MO_SET;
1724 mo->u.loc = loc;
1725 mo->insn = NEXT_INSN ((rtx) insn);
1726 }
1727 }
1728
1729 /* Compute the changes of variable locations in the basic block BB. */
1730
1731 static bool
compute_bb_dataflow(basic_block bb)1732 compute_bb_dataflow (basic_block bb)
1733 {
1734 int i, n, r;
1735 bool changed;
1736 dataflow_set old_out;
1737 dataflow_set *in = &VTI (bb)->in;
1738 dataflow_set *out = &VTI (bb)->out;
1739
1740 dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
1741 dataflow_set_copy (&old_out, out);
1742 dataflow_set_copy (out, in);
1743
1744 n = VTI (bb)->n_mos;
1745 for (i = 0; i < n; i++)
1746 {
1747 switch (VTI (bb)->mos[i].type)
1748 {
1749 case MO_CALL:
1750 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1751 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
1752 var_regno_delete (out, r);
1753 break;
1754
1755 case MO_USE:
1756 {
1757 rtx loc = VTI (bb)->mos[i].u.loc;
1758
1759 if (GET_CODE (loc) == REG)
1760 var_reg_set (out, loc);
1761 else if (GET_CODE (loc) == MEM)
1762 var_mem_set (out, loc);
1763 }
1764 break;
1765
1766 case MO_SET:
1767 {
1768 rtx loc = VTI (bb)->mos[i].u.loc;
1769
1770 if (REG_P (loc))
1771 var_reg_delete_and_set (out, loc, true);
1772 else if (MEM_P (loc))
1773 var_mem_delete_and_set (out, loc, true);
1774 }
1775 break;
1776
1777 case MO_COPY:
1778 {
1779 rtx loc = VTI (bb)->mos[i].u.loc;
1780
1781 if (REG_P (loc))
1782 var_reg_delete_and_set (out, loc, false);
1783 else if (MEM_P (loc))
1784 var_mem_delete_and_set (out, loc, false);
1785 }
1786 break;
1787
1788 case MO_USE_NO_VAR:
1789 {
1790 rtx loc = VTI (bb)->mos[i].u.loc;
1791
1792 if (REG_P (loc))
1793 var_reg_delete (out, loc, false);
1794 else if (MEM_P (loc))
1795 var_mem_delete (out, loc, false);
1796 }
1797 break;
1798
1799 case MO_CLOBBER:
1800 {
1801 rtx loc = VTI (bb)->mos[i].u.loc;
1802
1803 if (REG_P (loc))
1804 var_reg_delete (out, loc, true);
1805 else if (MEM_P (loc))
1806 var_mem_delete (out, loc, true);
1807 }
1808 break;
1809
1810 case MO_ADJUST:
1811 out->stack_adjust += VTI (bb)->mos[i].u.adjust;
1812 break;
1813 }
1814 }
1815
1816 changed = dataflow_set_different (&old_out, out);
1817 dataflow_set_destroy (&old_out);
1818 return changed;
1819 }
1820
1821 /* Find the locations of variables in the whole function. */
1822
1823 static void
vt_find_locations(void)1824 vt_find_locations (void)
1825 {
1826 fibheap_t worklist, pending, fibheap_swap;
1827 sbitmap visited, in_worklist, in_pending, sbitmap_swap;
1828 basic_block bb;
1829 edge e;
1830 int *bb_order;
1831 int *rc_order;
1832 int i;
1833
1834 /* Compute reverse completion order of depth first search of the CFG
1835 so that the data-flow runs faster. */
1836 rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
1837 bb_order = XNEWVEC (int, last_basic_block);
1838 pre_and_rev_post_order_compute (NULL, rc_order, false);
1839 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1840 bb_order[rc_order[i]] = i;
1841 free (rc_order);
1842
1843 worklist = fibheap_new ();
1844 pending = fibheap_new ();
1845 visited = sbitmap_alloc (last_basic_block);
1846 in_worklist = sbitmap_alloc (last_basic_block);
1847 in_pending = sbitmap_alloc (last_basic_block);
1848 sbitmap_zero (in_worklist);
1849
1850 FOR_EACH_BB (bb)
1851 fibheap_insert (pending, bb_order[bb->index], bb);
1852 sbitmap_ones (in_pending);
1853
1854 while (!fibheap_empty (pending))
1855 {
1856 fibheap_swap = pending;
1857 pending = worklist;
1858 worklist = fibheap_swap;
1859 sbitmap_swap = in_pending;
1860 in_pending = in_worklist;
1861 in_worklist = sbitmap_swap;
1862
1863 sbitmap_zero (visited);
1864
1865 while (!fibheap_empty (worklist))
1866 {
1867 bb = fibheap_extract_min (worklist);
1868 RESET_BIT (in_worklist, bb->index);
1869 if (!TEST_BIT (visited, bb->index))
1870 {
1871 bool changed;
1872 edge_iterator ei;
1873
1874 SET_BIT (visited, bb->index);
1875
1876 /* Calculate the IN set as union of predecessor OUT sets. */
1877 dataflow_set_clear (&VTI (bb)->in);
1878 FOR_EACH_EDGE (e, ei, bb->preds)
1879 {
1880 dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
1881 }
1882
1883 changed = compute_bb_dataflow (bb);
1884 if (changed)
1885 {
1886 FOR_EACH_EDGE (e, ei, bb->succs)
1887 {
1888 if (e->dest == EXIT_BLOCK_PTR)
1889 continue;
1890
1891 if (e->dest == bb)
1892 continue;
1893
1894 if (TEST_BIT (visited, e->dest->index))
1895 {
1896 if (!TEST_BIT (in_pending, e->dest->index))
1897 {
1898 /* Send E->DEST to next round. */
1899 SET_BIT (in_pending, e->dest->index);
1900 fibheap_insert (pending,
1901 bb_order[e->dest->index],
1902 e->dest);
1903 }
1904 }
1905 else if (!TEST_BIT (in_worklist, e->dest->index))
1906 {
1907 /* Add E->DEST to current round. */
1908 SET_BIT (in_worklist, e->dest->index);
1909 fibheap_insert (worklist, bb_order[e->dest->index],
1910 e->dest);
1911 }
1912 }
1913 }
1914 }
1915 }
1916 }
1917
1918 free (bb_order);
1919 fibheap_delete (worklist);
1920 fibheap_delete (pending);
1921 sbitmap_free (visited);
1922 sbitmap_free (in_worklist);
1923 sbitmap_free (in_pending);
1924 }
1925
1926 /* Print the content of the LIST to dump file. */
1927
1928 static void
dump_attrs_list(attrs list)1929 dump_attrs_list (attrs list)
1930 {
1931 for (; list; list = list->next)
1932 {
1933 print_mem_expr (dump_file, list->decl);
1934 fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
1935 }
1936 fprintf (dump_file, "\n");
1937 }
1938
1939 /* Print the information about variable *SLOT to dump file. */
1940
1941 static int
dump_variable(void ** slot,void * data ATTRIBUTE_UNUSED)1942 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1943 {
1944 variable var = *(variable *) slot;
1945 int i;
1946 location_chain node;
1947
1948 fprintf (dump_file, " name: %s\n",
1949 IDENTIFIER_POINTER (DECL_NAME (var->decl)));
1950 for (i = 0; i < var->n_var_parts; i++)
1951 {
1952 fprintf (dump_file, " offset %ld\n",
1953 (long) var->var_part[i].offset);
1954 for (node = var->var_part[i].loc_chain; node; node = node->next)
1955 {
1956 fprintf (dump_file, " ");
1957 print_rtl_single (dump_file, node->loc);
1958 }
1959 }
1960
1961 /* Continue traversing the hash table. */
1962 return 1;
1963 }
1964
1965 /* Print the information about variables from hash table VARS to dump file. */
1966
1967 static void
dump_vars(htab_t vars)1968 dump_vars (htab_t vars)
1969 {
1970 if (htab_elements (vars) > 0)
1971 {
1972 fprintf (dump_file, "Variables:\n");
1973 htab_traverse (vars, dump_variable, NULL);
1974 }
1975 }
1976
1977 /* Print the dataflow set SET to dump file. */
1978
1979 static void
dump_dataflow_set(dataflow_set * set)1980 dump_dataflow_set (dataflow_set *set)
1981 {
1982 int i;
1983
1984 fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
1985 set->stack_adjust);
1986 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1987 {
1988 if (set->regs[i])
1989 {
1990 fprintf (dump_file, "Reg %d:", i);
1991 dump_attrs_list (set->regs[i]);
1992 }
1993 }
1994 dump_vars (set->vars);
1995 fprintf (dump_file, "\n");
1996 }
1997
1998 /* Print the IN and OUT sets for each basic block to dump file. */
1999
2000 static void
dump_dataflow_sets(void)2001 dump_dataflow_sets (void)
2002 {
2003 basic_block bb;
2004
2005 FOR_EACH_BB (bb)
2006 {
2007 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
2008 fprintf (dump_file, "IN:\n");
2009 dump_dataflow_set (&VTI (bb)->in);
2010 fprintf (dump_file, "OUT:\n");
2011 dump_dataflow_set (&VTI (bb)->out);
2012 }
2013 }
2014
2015 /* Add variable VAR to the hash table of changed variables and
2016 if it has no locations delete it from hash table HTAB. */
2017
2018 static void
variable_was_changed(variable var,htab_t htab)2019 variable_was_changed (variable var, htab_t htab)
2020 {
2021 hashval_t hash = VARIABLE_HASH_VAL (var->decl);
2022
2023 if (emit_notes)
2024 {
2025 variable *slot;
2026
2027 slot = (variable *) htab_find_slot_with_hash (changed_variables,
2028 var->decl, hash, INSERT);
2029
2030 if (htab && var->n_var_parts == 0)
2031 {
2032 variable empty_var;
2033 void **old;
2034
2035 empty_var = pool_alloc (var_pool);
2036 empty_var->decl = var->decl;
2037 empty_var->refcount = 1;
2038 empty_var->n_var_parts = 0;
2039 *slot = empty_var;
2040
2041 old = htab_find_slot_with_hash (htab, var->decl, hash,
2042 NO_INSERT);
2043 if (old)
2044 htab_clear_slot (htab, old);
2045 }
2046 else
2047 {
2048 *slot = var;
2049 }
2050 }
2051 else
2052 {
2053 gcc_assert (htab);
2054 if (var->n_var_parts == 0)
2055 {
2056 void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
2057 NO_INSERT);
2058 if (slot)
2059 htab_clear_slot (htab, slot);
2060 }
2061 }
2062 }
2063
2064 /* Look for the index in VAR->var_part corresponding to OFFSET.
2065 Return -1 if not found. If INSERTION_POINT is non-NULL, the
2066 referenced int will be set to the index that the part has or should
2067 have, if it should be inserted. */
2068
2069 static inline int
find_variable_location_part(variable var,HOST_WIDE_INT offset,int * insertion_point)2070 find_variable_location_part (variable var, HOST_WIDE_INT offset,
2071 int *insertion_point)
2072 {
2073 int pos, low, high;
2074
2075 /* Find the location part. */
2076 low = 0;
2077 high = var->n_var_parts;
2078 while (low != high)
2079 {
2080 pos = (low + high) / 2;
2081 if (var->var_part[pos].offset < offset)
2082 low = pos + 1;
2083 else
2084 high = pos;
2085 }
2086 pos = low;
2087
2088 if (insertion_point)
2089 *insertion_point = pos;
2090
2091 if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2092 return pos;
2093
2094 return -1;
2095 }
2096
2097 /* Set the part of variable's location in the dataflow set SET. The variable
2098 part is specified by variable's declaration DECL and offset OFFSET and the
2099 part's location by LOC. */
2100
2101 static void
set_variable_part(dataflow_set * set,rtx loc,tree decl,HOST_WIDE_INT offset)2102 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset)
2103 {
2104 int pos;
2105 location_chain node, next;
2106 location_chain *nextp;
2107 variable var;
2108 void **slot;
2109
2110 slot = htab_find_slot_with_hash (set->vars, decl,
2111 VARIABLE_HASH_VAL (decl), INSERT);
2112 if (!*slot)
2113 {
2114 /* Create new variable information. */
2115 var = pool_alloc (var_pool);
2116 var->decl = decl;
2117 var->refcount = 1;
2118 var->n_var_parts = 1;
2119 var->var_part[0].offset = offset;
2120 var->var_part[0].loc_chain = NULL;
2121 var->var_part[0].cur_loc = NULL;
2122 *slot = var;
2123 pos = 0;
2124 }
2125 else
2126 {
2127 int inspos = 0;
2128
2129 var = (variable) *slot;
2130
2131 pos = find_variable_location_part (var, offset, &inspos);
2132
2133 if (pos >= 0)
2134 {
2135 node = var->var_part[pos].loc_chain;
2136
2137 if (node
2138 && ((REG_P (node->loc) && REG_P (loc)
2139 && REGNO (node->loc) == REGNO (loc))
2140 || rtx_equal_p (node->loc, loc)))
2141 {
2142 /* LOC is in the beginning of the chain so we have nothing
2143 to do. */
2144 return;
2145 }
2146 else
2147 {
2148 /* We have to make a copy of a shared variable. */
2149 if (var->refcount > 1)
2150 var = unshare_variable (set, var);
2151 }
2152 }
2153 else
2154 {
2155 /* We have not found the location part, new one will be created. */
2156
2157 /* We have to make a copy of the shared variable. */
2158 if (var->refcount > 1)
2159 var = unshare_variable (set, var);
2160
2161 /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2162 thus there are at most MAX_VAR_PARTS different offsets. */
2163 gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
2164
2165 /* We have to move the elements of array starting at index
2166 inspos to the next position. */
2167 for (pos = var->n_var_parts; pos > inspos; pos--)
2168 var->var_part[pos] = var->var_part[pos - 1];
2169
2170 var->n_var_parts++;
2171 var->var_part[pos].offset = offset;
2172 var->var_part[pos].loc_chain = NULL;
2173 var->var_part[pos].cur_loc = NULL;
2174 }
2175 }
2176
2177 /* Delete the location from the list. */
2178 nextp = &var->var_part[pos].loc_chain;
2179 for (node = var->var_part[pos].loc_chain; node; node = next)
2180 {
2181 next = node->next;
2182 if ((REG_P (node->loc) && REG_P (loc)
2183 && REGNO (node->loc) == REGNO (loc))
2184 || rtx_equal_p (node->loc, loc))
2185 {
2186 pool_free (loc_chain_pool, node);
2187 *nextp = next;
2188 break;
2189 }
2190 else
2191 nextp = &node->next;
2192 }
2193
2194 /* Add the location to the beginning. */
2195 node = pool_alloc (loc_chain_pool);
2196 node->loc = loc;
2197 node->next = var->var_part[pos].loc_chain;
2198 var->var_part[pos].loc_chain = node;
2199
2200 /* If no location was emitted do so. */
2201 if (var->var_part[pos].cur_loc == NULL)
2202 {
2203 var->var_part[pos].cur_loc = loc;
2204 variable_was_changed (var, set->vars);
2205 }
2206 }
2207
2208 /* Remove all recorded register locations for the given variable part
2209 from dataflow set SET, except for those that are identical to loc.
2210 The variable part is specified by variable's declaration DECL and
2211 offset OFFSET. */
2212
2213 static void
clobber_variable_part(dataflow_set * set,rtx loc,tree decl,HOST_WIDE_INT offset)2214 clobber_variable_part (dataflow_set *set, rtx loc, tree decl,
2215 HOST_WIDE_INT offset)
2216 {
2217 void **slot;
2218
2219 if (! decl || ! DECL_P (decl))
2220 return;
2221
2222 slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2223 NO_INSERT);
2224 if (slot)
2225 {
2226 variable var = (variable) *slot;
2227 int pos = find_variable_location_part (var, offset, NULL);
2228
2229 if (pos >= 0)
2230 {
2231 location_chain node, next;
2232
2233 /* Remove the register locations from the dataflow set. */
2234 next = var->var_part[pos].loc_chain;
2235 for (node = next; node; node = next)
2236 {
2237 next = node->next;
2238 if (node->loc != loc)
2239 {
2240 if (REG_P (node->loc))
2241 {
2242 attrs anode, anext;
2243 attrs *anextp;
2244
2245 /* Remove the variable part from the register's
2246 list, but preserve any other variable parts
2247 that might be regarded as live in that same
2248 register. */
2249 anextp = &set->regs[REGNO (node->loc)];
2250 for (anode = *anextp; anode; anode = anext)
2251 {
2252 anext = anode->next;
2253 if (anode->decl == decl
2254 && anode->offset == offset)
2255 {
2256 pool_free (attrs_pool, anode);
2257 *anextp = anext;
2258 }
2259 }
2260 }
2261
2262 delete_variable_part (set, node->loc, decl, offset);
2263 }
2264 }
2265 }
2266 }
2267 }
2268
2269 /* Delete the part of variable's location from dataflow set SET. The variable
2270 part is specified by variable's declaration DECL and offset OFFSET and the
2271 part's location by LOC. */
2272
2273 static void
delete_variable_part(dataflow_set * set,rtx loc,tree decl,HOST_WIDE_INT offset)2274 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2275 HOST_WIDE_INT offset)
2276 {
2277 void **slot;
2278
2279 slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2280 NO_INSERT);
2281 if (slot)
2282 {
2283 variable var = (variable) *slot;
2284 int pos = find_variable_location_part (var, offset, NULL);
2285
2286 if (pos >= 0)
2287 {
2288 location_chain node, next;
2289 location_chain *nextp;
2290 bool changed;
2291
2292 if (var->refcount > 1)
2293 {
2294 /* If the variable contains the location part we have to
2295 make a copy of the variable. */
2296 for (node = var->var_part[pos].loc_chain; node;
2297 node = node->next)
2298 {
2299 if ((REG_P (node->loc) && REG_P (loc)
2300 && REGNO (node->loc) == REGNO (loc))
2301 || rtx_equal_p (node->loc, loc))
2302 {
2303 var = unshare_variable (set, var);
2304 break;
2305 }
2306 }
2307 }
2308
2309 /* Delete the location part. */
2310 nextp = &var->var_part[pos].loc_chain;
2311 for (node = *nextp; node; node = next)
2312 {
2313 next = node->next;
2314 if ((REG_P (node->loc) && REG_P (loc)
2315 && REGNO (node->loc) == REGNO (loc))
2316 || rtx_equal_p (node->loc, loc))
2317 {
2318 pool_free (loc_chain_pool, node);
2319 *nextp = next;
2320 break;
2321 }
2322 else
2323 nextp = &node->next;
2324 }
2325
2326 /* If we have deleted the location which was last emitted
2327 we have to emit new location so add the variable to set
2328 of changed variables. */
2329 if (var->var_part[pos].cur_loc
2330 && ((REG_P (loc)
2331 && REG_P (var->var_part[pos].cur_loc)
2332 && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2333 || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2334 {
2335 changed = true;
2336 if (var->var_part[pos].loc_chain)
2337 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2338 }
2339 else
2340 changed = false;
2341
2342 if (var->var_part[pos].loc_chain == NULL)
2343 {
2344 var->n_var_parts--;
2345 while (pos < var->n_var_parts)
2346 {
2347 var->var_part[pos] = var->var_part[pos + 1];
2348 pos++;
2349 }
2350 }
2351 if (changed)
2352 variable_was_changed (var, set->vars);
2353 }
2354 }
2355 }
2356
2357 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP. DATA contains
2358 additional parameters: WHERE specifies whether the note shall be emitted
2359 before of after instruction INSN. */
2360
2361 static int
emit_note_insn_var_location(void ** varp,void * data)2362 emit_note_insn_var_location (void **varp, void *data)
2363 {
2364 variable var = *(variable *) varp;
2365 rtx insn = ((emit_note_data *)data)->insn;
2366 enum emit_note_where where = ((emit_note_data *)data)->where;
2367 rtx note;
2368 int i, j, n_var_parts;
2369 bool complete;
2370 HOST_WIDE_INT last_limit;
2371 tree type_size_unit;
2372 HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2373 rtx loc[MAX_VAR_PARTS];
2374
2375 gcc_assert (var->decl);
2376
2377 complete = true;
2378 last_limit = 0;
2379 n_var_parts = 0;
2380 for (i = 0; i < var->n_var_parts; i++)
2381 {
2382 enum machine_mode mode, wider_mode;
2383
2384 if (last_limit < var->var_part[i].offset)
2385 {
2386 complete = false;
2387 break;
2388 }
2389 else if (last_limit > var->var_part[i].offset)
2390 continue;
2391 offsets[n_var_parts] = var->var_part[i].offset;
2392 loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2393 mode = GET_MODE (loc[n_var_parts]);
2394 last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2395
2396 /* Attempt to merge adjacent registers or memory. */
2397 wider_mode = GET_MODE_WIDER_MODE (mode);
2398 for (j = i + 1; j < var->n_var_parts; j++)
2399 if (last_limit <= var->var_part[j].offset)
2400 break;
2401 if (j < var->n_var_parts
2402 && wider_mode != VOIDmode
2403 && GET_CODE (loc[n_var_parts])
2404 == GET_CODE (var->var_part[j].loc_chain->loc)
2405 && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2406 && last_limit == var->var_part[j].offset)
2407 {
2408 rtx new_loc = NULL;
2409 rtx loc2 = var->var_part[j].loc_chain->loc;
2410
2411 if (REG_P (loc[n_var_parts])
2412 && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2413 == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2414 && REGNO (loc[n_var_parts])
2415 + hard_regno_nregs[REGNO (loc[n_var_parts])][mode]
2416 == REGNO (loc2))
2417 {
2418 if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2419 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2420 mode, 0);
2421 else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2422 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2423 if (new_loc)
2424 {
2425 if (!REG_P (new_loc)
2426 || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2427 new_loc = NULL;
2428 else
2429 REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2430 }
2431 }
2432 else if (MEM_P (loc[n_var_parts])
2433 && GET_CODE (XEXP (loc2, 0)) == PLUS
2434 && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2435 && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2436 {
2437 if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2438 && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2439 XEXP (XEXP (loc2, 0), 0))
2440 && INTVAL (XEXP (XEXP (loc2, 0), 1))
2441 == GET_MODE_SIZE (mode))
2442 || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2443 && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2444 == CONST_INT
2445 && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2446 XEXP (XEXP (loc2, 0), 0))
2447 && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2448 + GET_MODE_SIZE (mode)
2449 == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2450 new_loc = adjust_address_nv (loc[n_var_parts],
2451 wider_mode, 0);
2452 }
2453
2454 if (new_loc)
2455 {
2456 loc[n_var_parts] = new_loc;
2457 mode = wider_mode;
2458 last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2459 i = j;
2460 }
2461 }
2462 ++n_var_parts;
2463 }
2464 type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2465 if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2466 complete = false;
2467
2468 if (where == EMIT_NOTE_AFTER_INSN)
2469 note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2470 else
2471 note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2472
2473 if (!complete)
2474 {
2475 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2476 NULL_RTX);
2477 }
2478 else if (n_var_parts == 1)
2479 {
2480 rtx expr_list
2481 = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
2482
2483 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2484 expr_list);
2485 }
2486 else if (n_var_parts)
2487 {
2488 rtx parallel;
2489
2490 for (i = 0; i < n_var_parts; i++)
2491 loc[i]
2492 = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
2493
2494 parallel = gen_rtx_PARALLEL (VOIDmode,
2495 gen_rtvec_v (n_var_parts, loc));
2496 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2497 parallel);
2498 }
2499
2500 htab_clear_slot (changed_variables, varp);
2501
2502 /* When there are no location parts the variable has been already
2503 removed from hash table and a new empty variable was created.
2504 Free the empty variable. */
2505 if (var->n_var_parts == 0)
2506 {
2507 pool_free (var_pool, var);
2508 }
2509
2510 /* Continue traversing the hash table. */
2511 return 1;
2512 }
2513
2514 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2515 CHANGED_VARIABLES and delete this chain. WHERE specifies whether the notes
2516 shall be emitted before of after instruction INSN. */
2517
2518 static void
emit_notes_for_changes(rtx insn,enum emit_note_where where)2519 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2520 {
2521 emit_note_data data;
2522
2523 data.insn = insn;
2524 data.where = where;
2525 htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2526 }
2527
2528 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2529 same variable in hash table DATA or is not there at all. */
2530
2531 static int
emit_notes_for_differences_1(void ** slot,void * data)2532 emit_notes_for_differences_1 (void **slot, void *data)
2533 {
2534 htab_t new_vars = (htab_t) data;
2535 variable old_var, new_var;
2536
2537 old_var = *(variable *) slot;
2538 new_var = htab_find_with_hash (new_vars, old_var->decl,
2539 VARIABLE_HASH_VAL (old_var->decl));
2540
2541 if (!new_var)
2542 {
2543 /* Variable has disappeared. */
2544 variable empty_var;
2545
2546 empty_var = pool_alloc (var_pool);
2547 empty_var->decl = old_var->decl;
2548 empty_var->refcount = 1;
2549 empty_var->n_var_parts = 0;
2550 variable_was_changed (empty_var, NULL);
2551 }
2552 else if (variable_different_p (old_var, new_var, true))
2553 {
2554 variable_was_changed (new_var, NULL);
2555 }
2556
2557 /* Continue traversing the hash table. */
2558 return 1;
2559 }
2560
2561 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2562 table DATA. */
2563
2564 static int
emit_notes_for_differences_2(void ** slot,void * data)2565 emit_notes_for_differences_2 (void **slot, void *data)
2566 {
2567 htab_t old_vars = (htab_t) data;
2568 variable old_var, new_var;
2569
2570 new_var = *(variable *) slot;
2571 old_var = htab_find_with_hash (old_vars, new_var->decl,
2572 VARIABLE_HASH_VAL (new_var->decl));
2573 if (!old_var)
2574 {
2575 /* Variable has appeared. */
2576 variable_was_changed (new_var, NULL);
2577 }
2578
2579 /* Continue traversing the hash table. */
2580 return 1;
2581 }
2582
2583 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2584 NEW_SET. */
2585
2586 static void
emit_notes_for_differences(rtx insn,dataflow_set * old_set,dataflow_set * new_set)2587 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2588 dataflow_set *new_set)
2589 {
2590 htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2591 htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2592 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2593 }
2594
2595 /* Emit the notes for changes of location parts in the basic block BB. */
2596
2597 static void
emit_notes_in_bb(basic_block bb)2598 emit_notes_in_bb (basic_block bb)
2599 {
2600 int i;
2601 dataflow_set set;
2602
2603 dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2604 dataflow_set_copy (&set, &VTI (bb)->in);
2605
2606 for (i = 0; i < VTI (bb)->n_mos; i++)
2607 {
2608 rtx insn = VTI (bb)->mos[i].insn;
2609
2610 switch (VTI (bb)->mos[i].type)
2611 {
2612 case MO_CALL:
2613 {
2614 int r;
2615
2616 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2617 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2618 {
2619 var_regno_delete (&set, r);
2620 }
2621 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2622 }
2623 break;
2624
2625 case MO_USE:
2626 {
2627 rtx loc = VTI (bb)->mos[i].u.loc;
2628
2629 if (GET_CODE (loc) == REG)
2630 var_reg_set (&set, loc);
2631 else
2632 var_mem_set (&set, loc);
2633
2634 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2635 }
2636 break;
2637
2638 case MO_SET:
2639 {
2640 rtx loc = VTI (bb)->mos[i].u.loc;
2641
2642 if (REG_P (loc))
2643 var_reg_delete_and_set (&set, loc, true);
2644 else
2645 var_mem_delete_and_set (&set, loc, true);
2646
2647 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2648 }
2649 break;
2650
2651 case MO_COPY:
2652 {
2653 rtx loc = VTI (bb)->mos[i].u.loc;
2654
2655 if (REG_P (loc))
2656 var_reg_delete_and_set (&set, loc, false);
2657 else
2658 var_mem_delete_and_set (&set, loc, false);
2659
2660 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2661 }
2662 break;
2663
2664 case MO_USE_NO_VAR:
2665 {
2666 rtx loc = VTI (bb)->mos[i].u.loc;
2667
2668 if (REG_P (loc))
2669 var_reg_delete (&set, loc, false);
2670 else
2671 var_mem_delete (&set, loc, false);
2672
2673 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2674 }
2675 break;
2676
2677 case MO_CLOBBER:
2678 {
2679 rtx loc = VTI (bb)->mos[i].u.loc;
2680
2681 if (REG_P (loc))
2682 var_reg_delete (&set, loc, true);
2683 else
2684 var_mem_delete (&set, loc, true);
2685
2686 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2687 }
2688 break;
2689
2690 case MO_ADJUST:
2691 set.stack_adjust += VTI (bb)->mos[i].u.adjust;
2692 break;
2693 }
2694 }
2695 dataflow_set_destroy (&set);
2696 }
2697
2698 /* Emit notes for the whole function. */
2699
2700 static void
vt_emit_notes(void)2701 vt_emit_notes (void)
2702 {
2703 basic_block bb;
2704 dataflow_set *last_out;
2705 dataflow_set empty;
2706
2707 gcc_assert (!htab_elements (changed_variables));
2708
2709 /* Enable emitting notes by functions (mainly by set_variable_part and
2710 delete_variable_part). */
2711 emit_notes = true;
2712
2713 dataflow_set_init (&empty, 7);
2714 last_out = ∅
2715
2716 FOR_EACH_BB (bb)
2717 {
2718 /* Emit the notes for changes of variable locations between two
2719 subsequent basic blocks. */
2720 emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
2721
2722 /* Emit the notes for the changes in the basic block itself. */
2723 emit_notes_in_bb (bb);
2724
2725 last_out = &VTI (bb)->out;
2726 }
2727 dataflow_set_destroy (&empty);
2728 emit_notes = false;
2729 }
2730
2731 /* If there is a declaration and offset associated with register/memory RTL
2732 assign declaration to *DECLP and offset to *OFFSETP, and return true. */
2733
2734 static bool
vt_get_decl_and_offset(rtx rtl,tree * declp,HOST_WIDE_INT * offsetp)2735 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
2736 {
2737 if (REG_P (rtl))
2738 {
2739 if (REG_ATTRS (rtl))
2740 {
2741 *declp = REG_EXPR (rtl);
2742 *offsetp = REG_OFFSET (rtl);
2743 return true;
2744 }
2745 }
2746 else if (MEM_P (rtl))
2747 {
2748 if (MEM_ATTRS (rtl))
2749 {
2750 *declp = MEM_EXPR (rtl);
2751 *offsetp = INT_MEM_OFFSET (rtl);
2752 return true;
2753 }
2754 }
2755 return false;
2756 }
2757
2758 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK. */
2759
2760 static void
vt_add_function_parameters(void)2761 vt_add_function_parameters (void)
2762 {
2763 tree parm;
2764
2765 for (parm = DECL_ARGUMENTS (current_function_decl);
2766 parm; parm = TREE_CHAIN (parm))
2767 {
2768 rtx decl_rtl = DECL_RTL_IF_SET (parm);
2769 rtx incoming = DECL_INCOMING_RTL (parm);
2770 tree decl;
2771 HOST_WIDE_INT offset;
2772 dataflow_set *out;
2773
2774 if (TREE_CODE (parm) != PARM_DECL)
2775 continue;
2776
2777 if (!DECL_NAME (parm))
2778 continue;
2779
2780 if (!decl_rtl || !incoming)
2781 continue;
2782
2783 if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
2784 continue;
2785
2786 if (!vt_get_decl_and_offset (incoming, &decl, &offset))
2787 if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
2788 continue;
2789
2790 if (!decl)
2791 continue;
2792
2793 gcc_assert (parm == decl);
2794
2795 out = &VTI (ENTRY_BLOCK_PTR)->out;
2796
2797 if (REG_P (incoming))
2798 {
2799 gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
2800 attrs_list_insert (&out->regs[REGNO (incoming)],
2801 parm, offset, incoming);
2802 set_variable_part (out, incoming, parm, offset);
2803 }
2804 else if (MEM_P (incoming))
2805 set_variable_part (out, incoming, parm, offset);
2806 }
2807 }
2808
2809 /* Allocate and initialize the data structures for variable tracking
2810 and parse the RTL to get the micro operations. */
2811
2812 static void
vt_initialize(void)2813 vt_initialize (void)
2814 {
2815 basic_block bb;
2816
2817 alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
2818
2819 FOR_EACH_BB (bb)
2820 {
2821 rtx insn;
2822 HOST_WIDE_INT pre, post = 0;
2823
2824 /* Count the number of micro operations. */
2825 VTI (bb)->n_mos = 0;
2826 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2827 insn = NEXT_INSN (insn))
2828 {
2829 if (INSN_P (insn))
2830 {
2831 if (!frame_pointer_needed)
2832 {
2833 insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2834 if (pre)
2835 VTI (bb)->n_mos++;
2836 if (post)
2837 VTI (bb)->n_mos++;
2838 }
2839 note_uses (&PATTERN (insn), count_uses_1, insn);
2840 note_stores (PATTERN (insn), count_stores, insn);
2841 if (CALL_P (insn))
2842 VTI (bb)->n_mos++;
2843 }
2844 }
2845
2846 /* Add the micro-operations to the array. */
2847 VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
2848 VTI (bb)->n_mos = 0;
2849 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2850 insn = NEXT_INSN (insn))
2851 {
2852 if (INSN_P (insn))
2853 {
2854 int n1, n2;
2855
2856 if (!frame_pointer_needed)
2857 {
2858 insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2859 if (pre)
2860 {
2861 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2862
2863 mo->type = MO_ADJUST;
2864 mo->u.adjust = pre;
2865 mo->insn = insn;
2866 }
2867 }
2868
2869 n1 = VTI (bb)->n_mos;
2870 note_uses (&PATTERN (insn), add_uses_1, insn);
2871 n2 = VTI (bb)->n_mos - 1;
2872
2873 /* Order the MO_USEs to be before MO_USE_NO_VARs. */
2874 while (n1 < n2)
2875 {
2876 while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
2877 n1++;
2878 while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
2879 n2--;
2880 if (n1 < n2)
2881 {
2882 micro_operation sw;
2883
2884 sw = VTI (bb)->mos[n1];
2885 VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2886 VTI (bb)->mos[n2] = sw;
2887 }
2888 }
2889
2890 if (CALL_P (insn))
2891 {
2892 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2893
2894 mo->type = MO_CALL;
2895 mo->insn = insn;
2896 }
2897
2898 n1 = VTI (bb)->n_mos;
2899 /* This will record NEXT_INSN (insn), such that we can
2900 insert notes before it without worrying about any
2901 notes that MO_USEs might emit after the insn. */
2902 note_stores (PATTERN (insn), add_stores, insn);
2903 n2 = VTI (bb)->n_mos - 1;
2904
2905 /* Order the MO_CLOBBERs to be before MO_SETs. */
2906 while (n1 < n2)
2907 {
2908 while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
2909 n1++;
2910 while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET
2911 || VTI (bb)->mos[n2].type == MO_COPY))
2912 n2--;
2913 if (n1 < n2)
2914 {
2915 micro_operation sw;
2916
2917 sw = VTI (bb)->mos[n1];
2918 VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2919 VTI (bb)->mos[n2] = sw;
2920 }
2921 }
2922
2923 if (!frame_pointer_needed && post)
2924 {
2925 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2926
2927 mo->type = MO_ADJUST;
2928 mo->u.adjust = post;
2929 mo->insn = insn;
2930 }
2931 }
2932 }
2933 }
2934
2935 /* Init the IN and OUT sets. */
2936 FOR_ALL_BB (bb)
2937 {
2938 VTI (bb)->visited = false;
2939 dataflow_set_init (&VTI (bb)->in, 7);
2940 dataflow_set_init (&VTI (bb)->out, 7);
2941 }
2942
2943 attrs_pool = create_alloc_pool ("attrs_def pool",
2944 sizeof (struct attrs_def), 1024);
2945 var_pool = create_alloc_pool ("variable_def pool",
2946 sizeof (struct variable_def), 64);
2947 loc_chain_pool = create_alloc_pool ("location_chain_def pool",
2948 sizeof (struct location_chain_def),
2949 1024);
2950 changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
2951 NULL);
2952 vt_add_function_parameters ();
2953 }
2954
2955 /* Free the data structures needed for variable tracking. */
2956
2957 static void
vt_finalize(void)2958 vt_finalize (void)
2959 {
2960 basic_block bb;
2961
2962 FOR_EACH_BB (bb)
2963 {
2964 free (VTI (bb)->mos);
2965 }
2966
2967 FOR_ALL_BB (bb)
2968 {
2969 dataflow_set_destroy (&VTI (bb)->in);
2970 dataflow_set_destroy (&VTI (bb)->out);
2971 }
2972 free_aux_for_blocks ();
2973 free_alloc_pool (attrs_pool);
2974 free_alloc_pool (var_pool);
2975 free_alloc_pool (loc_chain_pool);
2976 htab_delete (changed_variables);
2977 }
2978
2979 /* The entry point to variable tracking pass. */
2980
2981 unsigned int
variable_tracking_main(void)2982 variable_tracking_main (void)
2983 {
2984 if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
2985 return 0;
2986
2987 mark_dfs_back_edges ();
2988 vt_initialize ();
2989 if (!frame_pointer_needed)
2990 {
2991 if (!vt_stack_adjustments ())
2992 {
2993 vt_finalize ();
2994 return 0;
2995 }
2996 }
2997
2998 vt_find_locations ();
2999 vt_emit_notes ();
3000
3001 if (dump_file && (dump_flags & TDF_DETAILS))
3002 {
3003 dump_dataflow_sets ();
3004 dump_flow_info (dump_file, dump_flags);
3005 }
3006
3007 vt_finalize ();
3008 return 0;
3009 }
3010
3011 static bool
gate_handle_var_tracking(void)3012 gate_handle_var_tracking (void)
3013 {
3014 return (flag_var_tracking);
3015 }
3016
3017
3018
3019 struct tree_opt_pass pass_variable_tracking =
3020 {
3021 "vartrack", /* name */
3022 gate_handle_var_tracking, /* gate */
3023 variable_tracking_main, /* execute */
3024 NULL, /* sub */
3025 NULL, /* next */
3026 0, /* static_pass_number */
3027 TV_VAR_TRACKING, /* tv_id */
3028 0, /* properties_required */
3029 0, /* properties_provided */
3030 0, /* properties_destroyed */
3031 0, /* todo_flags_start */
3032 TODO_dump_func, /* todo_flags_finish */
3033 'V' /* letter */
3034 };
3035
3036