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