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