Mercurial > hg > CbC > CbC_gcc

comparison gcc/var-tracking.c @ 0:a06113de4d67

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