OSDN Git Service

bdd3bdee34ef765dcc5f59adf9a8764f478896a3
[pf3gnuchains/gcc-fork.git] / gcc / var-tracking.c
1 /* Variable tracking routines for the GNU compiler.
2    Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009
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 #include "cselib.h"
110 #include "target.h"
111
112 /* Type of micro operation.  */
113 enum micro_operation_type
114 {
115   MO_USE,       /* Use location (REG or MEM).  */
116   MO_USE_NO_VAR,/* Use location which is not associated with a variable
117                    or the variable is not trackable.  */
118   MO_VAL_USE,   /* Use location which is associated with a value.  */
119   MO_VAL_LOC,   /* Use location which appears in a debug insn.  */
120   MO_VAL_SET,   /* Set location associated with a value.  */
121   MO_SET,       /* Set location.  */
122   MO_COPY,      /* Copy the same portion of a variable from one
123                    location to another.  */
124   MO_CLOBBER,   /* Clobber location.  */
125   MO_CALL,      /* Call insn.  */
126   MO_ADJUST     /* Adjust stack pointer.  */
127
128 };
129
130 static const char * const ATTRIBUTE_UNUSED
131 micro_operation_type_name[] = {
132   "MO_USE",
133   "MO_USE_NO_VAR",
134   "MO_VAL_USE",
135   "MO_VAL_LOC",
136   "MO_VAL_SET",
137   "MO_SET",
138   "MO_COPY",
139   "MO_CLOBBER",
140   "MO_CALL",
141   "MO_ADJUST"
142 };
143
144 /* Where shall the note be emitted?  BEFORE or AFTER the instruction.
145    Notes emitted as AFTER_CALL are to take effect during the call,
146    rather than after the call.  */
147 enum emit_note_where
148 {
149   EMIT_NOTE_BEFORE_INSN,
150   EMIT_NOTE_AFTER_INSN,
151   EMIT_NOTE_AFTER_CALL_INSN
152 };
153
154 /* Structure holding information about micro operation.  */
155 typedef struct micro_operation_def
156 {
157   /* Type of micro operation.  */
158   enum micro_operation_type type;
159
160   union {
161     /* Location.  For MO_SET and MO_COPY, this is the SET that
162        performs the assignment, if known, otherwise it is the target
163        of the assignment.  For MO_VAL_USE and MO_VAL_SET, it is a
164        CONCAT of the VALUE and the LOC associated with it.  For
165        MO_VAL_LOC, it is a CONCAT of the VALUE and the VAR_LOCATION
166        associated with it.  */
167     rtx loc;
168
169     /* Stack adjustment.  */
170     HOST_WIDE_INT adjust;
171   } u;
172
173   /* The instruction which the micro operation is in, for MO_USE,
174      MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent
175      instruction or note in the original flow (before any var-tracking
176      notes are inserted, to simplify emission of notes), for MO_SET
177      and MO_CLOBBER.  */
178   rtx insn;
179 } micro_operation;
180
181 /* A declaration of a variable, or an RTL value being handled like a
182    declaration.  */
183 typedef void *decl_or_value;
184
185 /* Structure for passing some other parameters to function
186    emit_note_insn_var_location.  */
187 typedef struct emit_note_data_def
188 {
189   /* The instruction which the note will be emitted before/after.  */
190   rtx insn;
191
192   /* Where the note will be emitted (before/after insn)?  */
193   enum emit_note_where where;
194
195   /* The variables and values active at this point.  */
196   htab_t vars;
197 } emit_note_data;
198
199 /* Description of location of a part of a variable.  The content of a physical
200    register is described by a chain of these structures.
201    The chains are pretty short (usually 1 or 2 elements) and thus
202    chain is the best data structure.  */
203 typedef struct attrs_def
204 {
205   /* Pointer to next member of the list.  */
206   struct attrs_def *next;
207
208   /* The rtx of register.  */
209   rtx loc;
210
211   /* The declaration corresponding to LOC.  */
212   decl_or_value dv;
213
214   /* Offset from start of DECL.  */
215   HOST_WIDE_INT offset;
216 } *attrs;
217
218 /* Structure holding a refcounted hash table.  If refcount > 1,
219    it must be first unshared before modified.  */
220 typedef struct shared_hash_def
221 {
222   /* Reference count.  */
223   int refcount;
224
225   /* Actual hash table.  */
226   htab_t htab;
227 } *shared_hash;
228
229 /* Structure holding the IN or OUT set for a basic block.  */
230 typedef struct dataflow_set_def
231 {
232   /* Adjustment of stack offset.  */
233   HOST_WIDE_INT stack_adjust;
234
235   /* Attributes for registers (lists of attrs).  */
236   attrs regs[FIRST_PSEUDO_REGISTER];
237
238   /* Variable locations.  */
239   shared_hash vars;
240
241   /* Vars that is being traversed.  */
242   shared_hash traversed_vars;
243 } dataflow_set;
244
245 /* The structure (one for each basic block) containing the information
246    needed for variable tracking.  */
247 typedef struct variable_tracking_info_def
248 {
249   /* Number of micro operations stored in the MOS array.  */
250   int n_mos;
251
252   /* The array of micro operations.  */
253   micro_operation *mos;
254
255   /* The IN and OUT set for dataflow analysis.  */
256   dataflow_set in;
257   dataflow_set out;
258
259   /* The permanent-in dataflow set for this block.  This is used to
260      hold values for which we had to compute entry values.  ??? This
261      should probably be dynamically allocated, to avoid using more
262      memory in non-debug builds.  */
263   dataflow_set *permp;
264
265   /* Has the block been visited in DFS?  */
266   bool visited;
267
268   /* Has the block been flooded in VTA?  */
269   bool flooded;
270
271 } *variable_tracking_info;
272
273 /* Structure for chaining the locations.  */
274 typedef struct location_chain_def
275 {
276   /* Next element in the chain.  */
277   struct location_chain_def *next;
278
279   /* The location (REG, MEM or VALUE).  */
280   rtx loc;
281
282   /* The "value" stored in this location.  */
283   rtx set_src;
284
285   /* Initialized? */
286   enum var_init_status init;
287 } *location_chain;
288
289 /* Structure describing one part of variable.  */
290 typedef struct variable_part_def
291 {
292   /* Chain of locations of the part.  */
293   location_chain loc_chain;
294
295   /* Location which was last emitted to location list.  */
296   rtx cur_loc;
297
298   /* The offset in the variable.  */
299   HOST_WIDE_INT offset;
300 } variable_part;
301
302 /* Maximum number of location parts.  */
303 #define MAX_VAR_PARTS 16
304
305 /* Structure describing where the variable is located.  */
306 typedef struct variable_def
307 {
308   /* The declaration of the variable, or an RTL value being handled
309      like a declaration.  */
310   decl_or_value dv;
311
312   /* Reference count.  */
313   int refcount;
314
315   /* Number of variable parts.  */
316   int n_var_parts;
317
318   /* The variable parts.  */
319   variable_part var_part[1];
320 } *variable;
321 typedef const struct variable_def *const_variable;
322
323 /* Structure for chaining backlinks from referenced VALUEs to
324    DVs that are referencing them.  */
325 typedef struct value_chain_def
326 {
327   /* Next value_chain entry.  */
328   struct value_chain_def *next;
329
330   /* The declaration of the variable, or an RTL value
331      being handled like a declaration, whose var_parts[0].loc_chain
332      references the VALUE owning this value_chain.  */
333   decl_or_value dv;
334
335   /* Reference count.  */
336   int refcount;
337 } *value_chain;
338 typedef const struct value_chain_def *const_value_chain;
339
340 /* Hash function for DECL for VARIABLE_HTAB.  */
341 #define VARIABLE_HASH_VAL(decl) (DECL_UID (decl))
342
343 /* Pointer to the BB's information specific to variable tracking pass.  */
344 #define VTI(BB) ((variable_tracking_info) (BB)->aux)
345
346 /* Macro to access MEM_OFFSET as an HOST_WIDE_INT.  Evaluates MEM twice.  */
347 #define INT_MEM_OFFSET(mem) (MEM_OFFSET (mem) ? INTVAL (MEM_OFFSET (mem)) : 0)
348
349 /* Alloc pool for struct attrs_def.  */
350 static alloc_pool attrs_pool;
351
352 /* Alloc pool for struct variable_def with MAX_VAR_PARTS entries.  */
353 static alloc_pool var_pool;
354
355 /* Alloc pool for struct variable_def with a single var_part entry.  */
356 static alloc_pool valvar_pool;
357
358 /* Alloc pool for struct location_chain_def.  */
359 static alloc_pool loc_chain_pool;
360
361 /* Alloc pool for struct shared_hash_def.  */
362 static alloc_pool shared_hash_pool;
363
364 /* Alloc pool for struct value_chain_def.  */
365 static alloc_pool value_chain_pool;
366
367 /* Changed variables, notes will be emitted for them.  */
368 static htab_t changed_variables;
369
370 /* Links from VALUEs to DVs referencing them in their current loc_chains.  */
371 static htab_t value_chains;
372
373 /* Shall notes be emitted?  */
374 static bool emit_notes;
375
376 /* Empty shared hashtable.  */
377 static shared_hash empty_shared_hash;
378
379 /* Scratch register bitmap used by cselib_expand_value_rtx.  */
380 static bitmap scratch_regs = NULL;
381
382 /* Variable used to tell whether cselib_process_insn called our hook.  */
383 static bool cselib_hook_called;
384
385 /* Local function prototypes.  */
386 static void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
387                                           HOST_WIDE_INT *);
388 static void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
389                                                HOST_WIDE_INT *);
390 static void bb_stack_adjust_offset (basic_block);
391 static bool vt_stack_adjustments (void);
392 static rtx adjust_stack_reference (rtx, HOST_WIDE_INT);
393 static hashval_t variable_htab_hash (const void *);
394 static int variable_htab_eq (const void *, const void *);
395 static void variable_htab_free (void *);
396
397 static void init_attrs_list_set (attrs *);
398 static void attrs_list_clear (attrs *);
399 static attrs attrs_list_member (attrs, decl_or_value, HOST_WIDE_INT);
400 static void attrs_list_insert (attrs *, decl_or_value, HOST_WIDE_INT, rtx);
401 static void attrs_list_copy (attrs *, attrs);
402 static void attrs_list_union (attrs *, attrs);
403
404 static void **unshare_variable (dataflow_set *set, void **slot, variable var,
405                                 enum var_init_status);
406 static int vars_copy_1 (void **, void *);
407 static void vars_copy (htab_t, htab_t);
408 static tree var_debug_decl (tree);
409 static void var_reg_set (dataflow_set *, rtx, enum var_init_status, rtx);
410 static void var_reg_delete_and_set (dataflow_set *, rtx, bool, 
411                                     enum var_init_status, rtx);
412 static void var_reg_delete (dataflow_set *, rtx, bool);
413 static void var_regno_delete (dataflow_set *, int);
414 static void var_mem_set (dataflow_set *, rtx, enum var_init_status, rtx);
415 static void var_mem_delete_and_set (dataflow_set *, rtx, bool, 
416                                     enum var_init_status, rtx);
417 static void var_mem_delete (dataflow_set *, rtx, bool);
418
419 static void dataflow_set_init (dataflow_set *);
420 static void dataflow_set_clear (dataflow_set *);
421 static void dataflow_set_copy (dataflow_set *, dataflow_set *);
422 static int variable_union_info_cmp_pos (const void *, const void *);
423 static int variable_union (void **, void *);
424 static int variable_canonicalize (void **, void *);
425 static void dataflow_set_union (dataflow_set *, dataflow_set *);
426 static location_chain find_loc_in_1pdv (rtx, variable, htab_t);
427 static bool canon_value_cmp (rtx, rtx);
428 static int loc_cmp (rtx, rtx);
429 static bool variable_part_different_p (variable_part *, variable_part *);
430 static bool onepart_variable_different_p (variable, variable);
431 static bool variable_different_p (variable, variable, bool);
432 static int dataflow_set_different_1 (void **, void *);
433 static bool dataflow_set_different (dataflow_set *, dataflow_set *);
434 static void dataflow_set_destroy (dataflow_set *);
435
436 static bool contains_symbol_ref (rtx);
437 static bool track_expr_p (tree, bool);
438 static bool same_variable_part_p (rtx, tree, HOST_WIDE_INT);
439 static int count_uses (rtx *, void *);
440 static void count_uses_1 (rtx *, void *);
441 static void count_stores (rtx, const_rtx, void *);
442 static int add_uses (rtx *, void *);
443 static void add_uses_1 (rtx *, void *);
444 static void add_stores (rtx, const_rtx, void *);
445 static bool compute_bb_dataflow (basic_block);
446 static void vt_find_locations (void);
447
448 static void dump_attrs_list (attrs);
449 static int dump_variable_slot (void **, void *);
450 static void dump_variable (variable);
451 static void dump_vars (htab_t);
452 static void dump_dataflow_set (dataflow_set *);
453 static void dump_dataflow_sets (void);
454
455 static void variable_was_changed (variable, dataflow_set *);
456 static void **set_slot_part (dataflow_set *, rtx, void **,
457                              decl_or_value, HOST_WIDE_INT,
458                              enum var_init_status, rtx);
459 static void set_variable_part (dataflow_set *, rtx,
460                                decl_or_value, HOST_WIDE_INT,
461                                enum var_init_status, rtx, enum insert_option);
462 static void **clobber_slot_part (dataflow_set *, rtx,
463                                  void **, HOST_WIDE_INT, rtx);
464 static void clobber_variable_part (dataflow_set *, rtx,
465                                    decl_or_value, HOST_WIDE_INT, rtx);
466 static void **delete_slot_part (dataflow_set *, rtx, void **, HOST_WIDE_INT);
467 static void delete_variable_part (dataflow_set *, rtx,
468                                   decl_or_value, HOST_WIDE_INT);
469 static int emit_note_insn_var_location (void **, void *);
470 static void emit_notes_for_changes (rtx, enum emit_note_where, shared_hash);
471 static int emit_notes_for_differences_1 (void **, void *);
472 static int emit_notes_for_differences_2 (void **, void *);
473 static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
474 static void emit_notes_in_bb (basic_block, dataflow_set *);
475 static void vt_emit_notes (void);
476
477 static bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *);
478 static void vt_add_function_parameters (void);
479 static void vt_initialize (void);
480 static void vt_finalize (void);
481
482 /* Given a SET, calculate the amount of stack adjustment it contains
483    PRE- and POST-modifying stack pointer.
484    This function is similar to stack_adjust_offset.  */
485
486 static void
487 stack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre,
488                               HOST_WIDE_INT *post)
489 {
490   rtx src = SET_SRC (pattern);
491   rtx dest = SET_DEST (pattern);
492   enum rtx_code code;
493
494   if (dest == stack_pointer_rtx)
495     {
496       /* (set (reg sp) (plus (reg sp) (const_int))) */
497       code = GET_CODE (src);
498       if (! (code == PLUS || code == MINUS)
499           || XEXP (src, 0) != stack_pointer_rtx
500           || !CONST_INT_P (XEXP (src, 1)))
501         return;
502
503       if (code == MINUS)
504         *post += INTVAL (XEXP (src, 1));
505       else
506         *post -= INTVAL (XEXP (src, 1));
507     }
508   else if (MEM_P (dest))
509     {
510       /* (set (mem (pre_dec (reg sp))) (foo)) */
511       src = XEXP (dest, 0);
512       code = GET_CODE (src);
513
514       switch (code)
515         {
516         case PRE_MODIFY:
517         case POST_MODIFY:
518           if (XEXP (src, 0) == stack_pointer_rtx)
519             {
520               rtx val = XEXP (XEXP (src, 1), 1);
521               /* We handle only adjustments by constant amount.  */
522               gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS &&
523                           CONST_INT_P (val));
524               
525               if (code == PRE_MODIFY)
526                 *pre -= INTVAL (val);
527               else
528                 *post -= INTVAL (val);
529               break;
530             }
531           return;
532
533         case PRE_DEC:
534           if (XEXP (src, 0) == stack_pointer_rtx)
535             {
536               *pre += GET_MODE_SIZE (GET_MODE (dest));
537               break;
538             }
539           return;
540
541         case POST_DEC:
542           if (XEXP (src, 0) == stack_pointer_rtx)
543             {
544               *post += GET_MODE_SIZE (GET_MODE (dest));
545               break;
546             }
547           return;
548
549         case PRE_INC:
550           if (XEXP (src, 0) == stack_pointer_rtx)
551             {
552               *pre -= GET_MODE_SIZE (GET_MODE (dest));
553               break;
554             }
555           return;
556
557         case POST_INC:
558           if (XEXP (src, 0) == stack_pointer_rtx)
559             {
560               *post -= GET_MODE_SIZE (GET_MODE (dest));
561               break;
562             }
563           return;
564
565         default:
566           return;
567         }
568     }
569 }
570
571 /* Given an INSN, calculate the amount of stack adjustment it contains
572    PRE- and POST-modifying stack pointer.  */
573
574 static void
575 insn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre,
576                                    HOST_WIDE_INT *post)
577 {
578   rtx pattern;
579
580   *pre = 0;
581   *post = 0;
582
583   pattern = PATTERN (insn);
584   if (RTX_FRAME_RELATED_P (insn))
585     {
586       rtx expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
587       if (expr)
588         pattern = XEXP (expr, 0);
589     }
590
591   if (GET_CODE (pattern) == SET)
592     stack_adjust_offset_pre_post (pattern, pre, post);
593   else if (GET_CODE (pattern) == PARALLEL
594            || GET_CODE (pattern) == SEQUENCE)
595     {
596       int i;
597
598       /* There may be stack adjustments inside compound insns.  Search
599          for them.  */
600       for ( i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
601         if (GET_CODE (XVECEXP (pattern, 0, i)) == SET)
602           stack_adjust_offset_pre_post (XVECEXP (pattern, 0, i), pre, post);
603     }
604 }
605
606 /* Compute stack adjustment in basic block BB.  */
607
608 static void
609 bb_stack_adjust_offset (basic_block bb)
610 {
611   HOST_WIDE_INT offset;
612   int i;
613
614   offset = VTI (bb)->in.stack_adjust;
615   for (i = 0; i < VTI (bb)->n_mos; i++)
616     {
617       if (VTI (bb)->mos[i].type == MO_ADJUST)
618         offset += VTI (bb)->mos[i].u.adjust;
619       else if (VTI (bb)->mos[i].type != MO_CALL)
620         {
621           if (MEM_P (VTI (bb)->mos[i].u.loc))
622             {
623               VTI (bb)->mos[i].u.loc
624                 = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset);
625             }
626         }
627     }
628   VTI (bb)->out.stack_adjust = offset;
629 }
630
631 /* Compute stack adjustments for all blocks by traversing DFS tree.
632    Return true when the adjustments on all incoming edges are consistent.
633    Heavily borrowed from pre_and_rev_post_order_compute.  */
634
635 static bool
636 vt_stack_adjustments (void)
637 {
638   edge_iterator *stack;
639   int sp;
640
641   /* Initialize entry block.  */
642   VTI (ENTRY_BLOCK_PTR)->visited = true;
643   VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET;
644
645   /* Allocate stack for back-tracking up CFG.  */
646   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
647   sp = 0;
648
649   /* Push the first edge on to the stack.  */
650   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
651
652   while (sp)
653     {
654       edge_iterator ei;
655       basic_block src;
656       basic_block dest;
657
658       /* Look at the edge on the top of the stack.  */
659       ei = stack[sp - 1];
660       src = ei_edge (ei)->src;
661       dest = ei_edge (ei)->dest;
662
663       /* Check if the edge destination has been visited yet.  */
664       if (!VTI (dest)->visited)
665         {
666           VTI (dest)->visited = true;
667           VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust;
668           bb_stack_adjust_offset (dest);
669
670           if (EDGE_COUNT (dest->succs) > 0)
671             /* Since the DEST node has been visited for the first
672                time, check its successors.  */
673             stack[sp++] = ei_start (dest->succs);
674         }
675       else
676         {
677           /* Check whether the adjustments on the edges are the same.  */
678           if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust)
679             {
680               free (stack);
681               return false;
682             }
683
684           if (! ei_one_before_end_p (ei))
685             /* Go to the next edge.  */
686             ei_next (&stack[sp - 1]);
687           else
688             /* Return to previous level if there are no more edges.  */
689             sp--;
690         }
691     }
692
693   free (stack);
694   return true;
695 }
696
697 /* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative
698    to the argument pointer.  Return the new rtx.  */
699
700 static rtx
701 adjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment)
702 {
703   rtx addr, cfa, tmp;
704
705 #ifdef FRAME_POINTER_CFA_OFFSET
706   adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl);
707   cfa = plus_constant (frame_pointer_rtx, adjustment);
708 #else
709   adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl);
710   cfa = plus_constant (arg_pointer_rtx, adjustment);
711 #endif
712
713   addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa);
714   tmp = simplify_rtx (addr);
715   if (tmp)
716     addr = tmp;
717
718   return replace_equiv_address_nv (mem, addr);
719 }
720
721 /* Return true if a decl_or_value DV is a DECL or NULL.  */
722 static inline bool
723 dv_is_decl_p (decl_or_value dv)
724 {
725   if (!dv)
726     return true;
727
728   /* Make sure relevant codes don't overlap.  */
729   switch ((int)TREE_CODE ((tree)dv))
730     {
731     case (int)VAR_DECL:
732     case (int)PARM_DECL:
733     case (int)RESULT_DECL:
734     case (int)FUNCTION_DECL:
735     case (int)COMPONENT_REF:
736       return true;
737
738     case (int)VALUE:
739       return false;
740
741     default:
742       gcc_unreachable ();
743     }
744 }
745
746 /* Return true if a decl_or_value is a VALUE rtl.  */
747 static inline bool
748 dv_is_value_p (decl_or_value dv)
749 {
750   return dv && !dv_is_decl_p (dv);
751 }
752
753 /* Return the decl in the decl_or_value.  */
754 static inline tree
755 dv_as_decl (decl_or_value dv)
756 {
757   gcc_assert (dv_is_decl_p (dv));
758   return (tree) dv;
759 }
760
761 /* Return the value in the decl_or_value.  */
762 static inline rtx
763 dv_as_value (decl_or_value dv)
764 {
765   gcc_assert (dv_is_value_p (dv));
766   return (rtx)dv;
767 }
768
769 /* Return the opaque pointer in the decl_or_value.  */
770 static inline void *
771 dv_as_opaque (decl_or_value dv)
772 {
773   return dv;
774 }
775
776 /* Return true if a decl_or_value must not have more than one variable
777    part.  */
778 static inline bool
779 dv_onepart_p (decl_or_value dv)
780 {
781   tree decl;
782
783   if (!MAY_HAVE_DEBUG_INSNS)
784     return false;
785
786   if (dv_is_value_p (dv))
787     return true;
788
789   decl = dv_as_decl (dv);
790
791   if (!decl)
792     return true;
793
794   return (target_for_debug_bind (decl) != NULL_TREE);
795 }
796
797 /* Return the variable pool to be used for dv, depending on whether it
798    can have multiple parts or not.  */
799 static inline alloc_pool
800 dv_pool (decl_or_value dv)
801 {
802   return dv_onepart_p (dv) ? valvar_pool : var_pool;
803 }
804
805 /* Build a decl_or_value out of a decl.  */
806 static inline decl_or_value
807 dv_from_decl (tree decl)
808 {
809   decl_or_value dv;
810   dv = decl;
811   gcc_assert (dv_is_decl_p (dv));
812   return dv;
813 }
814
815 /* Build a decl_or_value out of a value.  */
816 static inline decl_or_value
817 dv_from_value (rtx value)
818 {
819   decl_or_value dv;
820   dv = value;
821   gcc_assert (dv_is_value_p (dv));
822   return dv;
823 }
824
825 static inline hashval_t
826 dv_htab_hash (decl_or_value dv)
827 {
828   if (dv_is_value_p (dv))
829     return -(hashval_t)(CSELIB_VAL_PTR (dv_as_value (dv))->value);
830   else
831     return (VARIABLE_HASH_VAL (dv_as_decl (dv)));
832 }
833
834 /* The hash function for variable_htab, computes the hash value
835    from the declaration of variable X.  */
836
837 static hashval_t
838 variable_htab_hash (const void *x)
839 {
840   const_variable const v = (const_variable) x;
841
842   return dv_htab_hash (v->dv);
843 }
844
845 /* Compare the declaration of variable X with declaration Y.  */
846
847 static int
848 variable_htab_eq (const void *x, const void *y)
849 {
850   const_variable const v = (const_variable) x;
851   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
852
853   if (dv_as_opaque (v->dv) == dv_as_opaque (dv))
854     return true;
855
856 #if ENABLE_CHECKING
857   {
858     bool visv, dvisv;
859
860     visv = dv_is_value_p (v->dv);
861     dvisv = dv_is_value_p (dv);
862
863     if (visv != dvisv)
864       return false;
865
866     if (visv)
867       gcc_assert (CSELIB_VAL_PTR (dv_as_value (v->dv))
868                   != CSELIB_VAL_PTR (dv_as_value (dv)));
869     else
870       gcc_assert (VARIABLE_HASH_VAL (dv_as_decl (v->dv))
871                   != VARIABLE_HASH_VAL (dv_as_decl (dv)));
872   }
873 #endif
874
875   return false;
876 }
877
878 /* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
879
880 static void
881 variable_htab_free (void *elem)
882 {
883   int i;
884   variable var = (variable) elem;
885   location_chain node, next;
886
887   gcc_assert (var->refcount > 0);
888
889   var->refcount--;
890   if (var->refcount > 0)
891     return;
892
893   for (i = 0; i < var->n_var_parts; i++)
894     {
895       for (node = var->var_part[i].loc_chain; node; node = next)
896         {
897           next = node->next;
898           pool_free (loc_chain_pool, node);
899         }
900       var->var_part[i].loc_chain = NULL;
901     }
902   pool_free (dv_pool (var->dv), var);
903 }
904
905 /* The hash function for value_chains htab, computes the hash value
906    from the VALUE.  */
907
908 static hashval_t
909 value_chain_htab_hash (const void *x)
910 {
911   const_value_chain const v = (const_value_chain) x;
912
913   return dv_htab_hash (v->dv);
914 }
915
916 /* Compare the VALUE X with VALUE Y.  */
917
918 static int
919 value_chain_htab_eq (const void *x, const void *y)
920 {
921   const_value_chain const v = (const_value_chain) x;
922   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
923
924   return dv_as_opaque (v->dv) == dv_as_opaque (dv);
925 }
926
927 /* Initialize the set (array) SET of attrs to empty lists.  */
928
929 static void
930 init_attrs_list_set (attrs *set)
931 {
932   int i;
933
934   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
935     set[i] = NULL;
936 }
937
938 /* Make the list *LISTP empty.  */
939
940 static void
941 attrs_list_clear (attrs *listp)
942 {
943   attrs list, next;
944
945   for (list = *listp; list; list = next)
946     {
947       next = list->next;
948       pool_free (attrs_pool, list);
949     }
950   *listp = NULL;
951 }
952
953 /* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
954
955 static attrs
956 attrs_list_member (attrs list, decl_or_value dv, HOST_WIDE_INT offset)
957 {
958   for (; list; list = list->next)
959     if (dv_as_opaque (list->dv) == dv_as_opaque (dv) && list->offset == offset)
960       return list;
961   return NULL;
962 }
963
964 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
965
966 static void
967 attrs_list_insert (attrs *listp, decl_or_value dv,
968                    HOST_WIDE_INT offset, rtx loc)
969 {
970   attrs list;
971
972   list = (attrs) pool_alloc (attrs_pool);
973   list->loc = loc;
974   list->dv = dv;
975   list->offset = offset;
976   list->next = *listp;
977   *listp = list;
978 }
979
980 /* Copy all nodes from SRC and create a list *DSTP of the copies.  */
981
982 static void
983 attrs_list_copy (attrs *dstp, attrs src)
984 {
985   attrs n;
986
987   attrs_list_clear (dstp);
988   for (; src; src = src->next)
989     {
990       n = (attrs) pool_alloc (attrs_pool);
991       n->loc = src->loc;
992       n->dv = src->dv;
993       n->offset = src->offset;
994       n->next = *dstp;
995       *dstp = n;
996     }
997 }
998
999 /* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
1000
1001 static void
1002 attrs_list_union (attrs *dstp, attrs src)
1003 {
1004   for (; src; src = src->next)
1005     {
1006       if (!attrs_list_member (*dstp, src->dv, src->offset))
1007         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1008     }
1009 }
1010
1011 /* Combine nodes that are not onepart nodes from SRC and SRC2 into
1012    *DSTP.  */
1013
1014 static void
1015 attrs_list_mpdv_union (attrs *dstp, attrs src, attrs src2)
1016 {
1017   gcc_assert (!*dstp);
1018   for (; src; src = src->next)
1019     {
1020       if (!dv_onepart_p (src->dv))
1021         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1022     }
1023   for (src = src2; src; src = src->next)
1024     {
1025       if (!dv_onepart_p (src->dv)
1026           && !attrs_list_member (*dstp, src->dv, src->offset))
1027         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1028     }
1029 }
1030
1031 /* Shared hashtable support.  */
1032
1033 /* Return true if VARS is shared.  */
1034
1035 static inline bool
1036 shared_hash_shared (shared_hash vars)
1037 {
1038   return vars->refcount > 1;
1039 }
1040
1041 /* Return the hash table for VARS.  */
1042
1043 static inline htab_t
1044 shared_hash_htab (shared_hash vars)
1045 {
1046   return vars->htab;
1047 }
1048
1049 /* Copy variables into a new hash table.  */
1050
1051 static shared_hash
1052 shared_hash_unshare (shared_hash vars)
1053 {
1054   shared_hash new_vars = (shared_hash) pool_alloc (shared_hash_pool);
1055   gcc_assert (vars->refcount > 1);
1056   new_vars->refcount = 1;
1057   new_vars->htab
1058     = htab_create (htab_elements (vars->htab) + 3, variable_htab_hash,
1059                    variable_htab_eq, variable_htab_free);
1060   vars_copy (new_vars->htab, vars->htab);
1061   vars->refcount--;
1062   return new_vars;
1063 }
1064
1065 /* Increment reference counter on VARS and return it.  */
1066
1067 static inline shared_hash
1068 shared_hash_copy (shared_hash vars)
1069 {
1070   vars->refcount++;
1071   return vars;
1072 }
1073
1074 /* Decrement reference counter and destroy hash table if not shared
1075    anymore.  */
1076
1077 static void
1078 shared_hash_destroy (shared_hash vars)
1079 {
1080   gcc_assert (vars->refcount > 0);
1081   if (--vars->refcount == 0)
1082     {
1083       htab_delete (vars->htab);
1084       pool_free (shared_hash_pool, vars);
1085     }
1086 }
1087
1088 /* Unshare *PVARS if shared and return slot for DV.  If INS is
1089    INSERT, insert it if not already present.  */
1090
1091 static inline void **
1092 shared_hash_find_slot_unshare_1 (shared_hash *pvars, decl_or_value dv,
1093                                  hashval_t dvhash, enum insert_option ins)
1094 {
1095   if (shared_hash_shared (*pvars))
1096     *pvars = shared_hash_unshare (*pvars);
1097   return htab_find_slot_with_hash (shared_hash_htab (*pvars), dv, dvhash, ins);
1098 }
1099
1100 static inline void **
1101 shared_hash_find_slot_unshare (shared_hash *pvars, decl_or_value dv,
1102                                enum insert_option ins)
1103 {
1104   return shared_hash_find_slot_unshare_1 (pvars, dv, dv_htab_hash (dv), ins);
1105 }
1106
1107 /* Return slot for DV, if it is already present in the hash table.
1108    If it is not present, insert it only VARS is not shared, otherwise
1109    return NULL.  */
1110
1111 static inline void **
1112 shared_hash_find_slot_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1113 {
1114   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1115                                    shared_hash_shared (vars)
1116                                    ? NO_INSERT : INSERT);
1117 }
1118
1119 static inline void **
1120 shared_hash_find_slot (shared_hash vars, decl_or_value dv)
1121 {
1122   return shared_hash_find_slot_1 (vars, dv, dv_htab_hash (dv));
1123 }
1124
1125 /* Return slot for DV only if it is already present in the hash table.  */
1126
1127 static inline void **
1128 shared_hash_find_slot_noinsert_1 (shared_hash vars, decl_or_value dv,
1129                                   hashval_t dvhash)
1130 {
1131   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1132                                    NO_INSERT);
1133 }
1134
1135 static inline void **
1136 shared_hash_find_slot_noinsert (shared_hash vars, decl_or_value dv)
1137 {
1138   return shared_hash_find_slot_noinsert_1 (vars, dv, dv_htab_hash (dv));
1139 }
1140
1141 /* Return variable for DV or NULL if not already present in the hash
1142    table.  */
1143
1144 static inline variable
1145 shared_hash_find_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1146 {
1147   return (variable) htab_find_with_hash (shared_hash_htab (vars), dv, dvhash);
1148 }
1149
1150 static inline variable
1151 shared_hash_find (shared_hash vars, decl_or_value dv)
1152 {
1153   return shared_hash_find_1 (vars, dv, dv_htab_hash (dv));
1154 }
1155
1156 /* Determine a total order between two distinct pointers.  Compare the
1157    pointers as integral types if size_t is wide enough, otherwise
1158    resort to bitwise memory compare.  The actual order does not
1159    matter, we just need to be consistent, so endianness is
1160    irrelevant.  */
1161
1162 static int
1163 tie_break_pointers (const void *p1, const void *p2)
1164 {
1165   gcc_assert (p1 != p2);
1166
1167   if (sizeof (size_t) >= sizeof (void*))
1168     return (size_t)p1 < (size_t)p2 ? -1 : 1;
1169   else
1170     return memcmp (&p1, &p2, sizeof (p1));
1171 }
1172
1173 /* Return true if TVAL is better than CVAL as a canonival value.  We
1174    choose lowest-numbered VALUEs, using the RTX address as a
1175    tie-breaker.  The idea is to arrange them into a star topology,
1176    such that all of them are at most one step away from the canonical
1177    value, and the canonical value has backlinks to all of them, in
1178    addition to all the actual locations.  We don't enforce this
1179    topology throughout the entire dataflow analysis, though.
1180  */
1181
1182 static inline bool
1183 canon_value_cmp (rtx tval, rtx cval)
1184 {
1185   return !cval
1186     || CSELIB_VAL_PTR (tval)->value < CSELIB_VAL_PTR (cval)->value
1187     || (CSELIB_VAL_PTR (tval)->value == CSELIB_VAL_PTR (cval)->value
1188         && tie_break_pointers (tval, cval) < 0);
1189 }
1190
1191 static bool dst_can_be_shared;
1192
1193 /* Return a copy of a variable VAR and insert it to dataflow set SET.  */
1194
1195 static void **
1196 unshare_variable (dataflow_set *set, void **slot, variable var,
1197                   enum var_init_status initialized)
1198 {
1199   variable new_var;
1200   int i;
1201
1202   new_var = (variable) pool_alloc (dv_pool (var->dv));
1203   new_var->dv = var->dv;
1204   new_var->refcount = 1;
1205   var->refcount--;
1206   new_var->n_var_parts = var->n_var_parts;
1207
1208   if (! flag_var_tracking_uninit)
1209     initialized = VAR_INIT_STATUS_INITIALIZED;
1210
1211   for (i = 0; i < var->n_var_parts; i++)
1212     {
1213       location_chain node;
1214       location_chain *nextp;
1215
1216       new_var->var_part[i].offset = var->var_part[i].offset;
1217       nextp = &new_var->var_part[i].loc_chain;
1218       for (node = var->var_part[i].loc_chain; node; node = node->next)
1219         {
1220           location_chain new_lc;
1221
1222           new_lc = (location_chain) pool_alloc (loc_chain_pool);
1223           new_lc->next = NULL;
1224           if (node->init > initialized)
1225             new_lc->init = node->init;
1226           else
1227             new_lc->init = initialized;
1228           if (node->set_src && !(MEM_P (node->set_src)))
1229             new_lc->set_src = node->set_src;
1230           else
1231             new_lc->set_src = NULL;
1232           new_lc->loc = node->loc;
1233
1234           *nextp = new_lc;
1235           nextp = &new_lc->next;
1236         }
1237
1238       /* We are at the basic block boundary when copying variable description
1239          so set the CUR_LOC to be the first element of the chain.  */
1240       if (new_var->var_part[i].loc_chain)
1241         new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
1242       else
1243         new_var->var_part[i].cur_loc = NULL;
1244     }
1245
1246   dst_can_be_shared = false;
1247   if (shared_hash_shared (set->vars))
1248     slot = shared_hash_find_slot_unshare (&set->vars, var->dv, NO_INSERT);
1249   else if (set->traversed_vars && set->vars != set->traversed_vars)
1250     slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
1251   *slot = new_var;
1252   return slot;
1253 }
1254
1255 /* Add a variable from *SLOT to hash table DATA and increase its reference
1256    count.  */
1257
1258 static int
1259 vars_copy_1 (void **slot, void *data)
1260 {
1261   htab_t dst = (htab_t) data;
1262   variable src;
1263   void **dstp;
1264
1265   src = (variable) *slot;
1266   src->refcount++;
1267
1268   dstp = htab_find_slot_with_hash (dst, src->dv,
1269                                    dv_htab_hash (src->dv),
1270                                    INSERT);
1271   *dstp = src;
1272
1273   /* Continue traversing the hash table.  */
1274   return 1;
1275 }
1276
1277 /* Copy all variables from hash table SRC to hash table DST.  */
1278
1279 static void
1280 vars_copy (htab_t dst, htab_t src)
1281 {
1282   htab_traverse_noresize (src, vars_copy_1, dst);
1283 }
1284
1285 /* Map a decl to its main debug decl.  */
1286
1287 static inline tree
1288 var_debug_decl (tree decl)
1289 {
1290   if (decl && DECL_P (decl)
1291       && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl)
1292       && DECL_P (DECL_DEBUG_EXPR (decl)))
1293     decl = DECL_DEBUG_EXPR (decl);
1294
1295   return decl;
1296 }
1297
1298 /* Set the register LOC to contain DV, OFFSET.  */
1299
1300 static void
1301 var_reg_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1302                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1303                   enum insert_option iopt)
1304 {
1305   attrs node;
1306   bool decl_p = dv_is_decl_p (dv);
1307
1308   if (decl_p)
1309     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1310
1311   for (node = set->regs[REGNO (loc)]; node; node = node->next)
1312     if (dv_as_opaque (node->dv) == dv_as_opaque (dv)
1313         && node->offset == offset)
1314       break;
1315   if (!node)
1316     attrs_list_insert (&set->regs[REGNO (loc)], dv, offset, loc);
1317   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1318 }
1319
1320 /* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
1321
1322 static void
1323 var_reg_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1324              rtx set_src)
1325 {
1326   tree decl = REG_EXPR (loc);
1327   HOST_WIDE_INT offset = REG_OFFSET (loc);
1328
1329   var_reg_decl_set (set, loc, initialized,
1330                     dv_from_decl (decl), offset, set_src, INSERT);
1331 }
1332
1333 static enum var_init_status
1334 get_init_value (dataflow_set *set, rtx loc, decl_or_value dv)
1335 {
1336   variable var;
1337   int i;
1338   enum var_init_status ret_val = VAR_INIT_STATUS_UNKNOWN;
1339
1340   if (! flag_var_tracking_uninit)
1341     return VAR_INIT_STATUS_INITIALIZED;
1342
1343   var = shared_hash_find (set->vars, dv);
1344   if (var)
1345     {
1346       for (i = 0; i < var->n_var_parts && ret_val == VAR_INIT_STATUS_UNKNOWN; i++)
1347         {
1348           location_chain nextp;
1349           for (nextp = var->var_part[i].loc_chain; nextp; nextp = nextp->next)
1350             if (rtx_equal_p (nextp->loc, loc))
1351               {
1352                 ret_val = nextp->init;
1353                 break;
1354               }
1355         }
1356     }
1357
1358   return ret_val;
1359 }
1360
1361 /* Delete current content of register LOC in dataflow set SET and set
1362    the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  If
1363    MODIFY is true, any other live copies of the same variable part are
1364    also deleted from the dataflow set, otherwise the variable part is
1365    assumed to be copied from another location holding the same
1366    part.  */
1367
1368 static void
1369 var_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify, 
1370                         enum var_init_status initialized, rtx set_src)
1371 {
1372   tree decl = REG_EXPR (loc);
1373   HOST_WIDE_INT offset = REG_OFFSET (loc);
1374   attrs node, next;
1375   attrs *nextp;
1376
1377   decl = var_debug_decl (decl);
1378
1379   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1380     initialized = get_init_value (set, loc, dv_from_decl (decl));
1381
1382   nextp = &set->regs[REGNO (loc)];
1383   for (node = *nextp; node; node = next)
1384     {
1385       next = node->next;
1386       if (dv_as_opaque (node->dv) != decl || node->offset != offset)
1387         {
1388           delete_variable_part (set, node->loc, node->dv, node->offset);
1389           pool_free (attrs_pool, node);
1390           *nextp = next;
1391         }
1392       else
1393         {
1394           node->loc = loc;
1395           nextp = &node->next;
1396         }
1397     }
1398   if (modify)
1399     clobber_variable_part (set, loc, dv_from_decl (decl), offset, set_src);
1400   var_reg_set (set, loc, initialized, set_src);
1401 }
1402
1403 /* Delete current content of register LOC in dataflow set SET.  If
1404    CLOBBER is true, also delete any other live copies of the same
1405    variable part.  */
1406
1407 static void
1408 var_reg_delete (dataflow_set *set, rtx loc, bool clobber)
1409 {
1410   attrs *reg = &set->regs[REGNO (loc)];
1411   attrs node, next;
1412
1413   if (clobber)
1414     {
1415       tree decl = REG_EXPR (loc);
1416       HOST_WIDE_INT offset = REG_OFFSET (loc);
1417
1418       decl = var_debug_decl (decl);
1419
1420       clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1421     }
1422
1423   for (node = *reg; node; node = next)
1424     {
1425       next = node->next;
1426       delete_variable_part (set, node->loc, node->dv, node->offset);
1427       pool_free (attrs_pool, node);
1428     }
1429   *reg = NULL;
1430 }
1431
1432 /* Delete content of register with number REGNO in dataflow set SET.  */
1433
1434 static void
1435 var_regno_delete (dataflow_set *set, int regno)
1436 {
1437   attrs *reg = &set->regs[regno];
1438   attrs node, next;
1439
1440   for (node = *reg; node; node = next)
1441     {
1442       next = node->next;
1443       delete_variable_part (set, node->loc, node->dv, node->offset);
1444       pool_free (attrs_pool, node);
1445     }
1446   *reg = NULL;
1447 }
1448
1449 /* Set the location of DV, OFFSET as the MEM LOC.  */
1450
1451 static void
1452 var_mem_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1453                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1454                   enum insert_option iopt)
1455 {
1456   if (dv_is_decl_p (dv))
1457     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1458
1459   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1460 }
1461
1462 /* Set the location part of variable MEM_EXPR (LOC) in dataflow set
1463    SET to LOC.
1464    Adjust the address first if it is stack pointer based.  */
1465
1466 static void
1467 var_mem_set (dataflow_set *set, rtx loc, enum var_init_status initialized, 
1468              rtx set_src)
1469 {
1470   tree decl = MEM_EXPR (loc);
1471   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1472
1473   var_mem_decl_set (set, loc, initialized,
1474                     dv_from_decl (decl), offset, set_src, INSERT);
1475 }
1476
1477 /* Delete and set the location part of variable MEM_EXPR (LOC) in
1478    dataflow set SET to LOC.  If MODIFY is true, any other live copies
1479    of the same variable part are also deleted from the dataflow set,
1480    otherwise the variable part is assumed to be copied from another
1481    location holding the same part.
1482    Adjust the address first if it is stack pointer based.  */
1483
1484 static void
1485 var_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify, 
1486                         enum var_init_status initialized, rtx set_src)
1487 {
1488   tree decl = MEM_EXPR (loc);
1489   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1490
1491   decl = var_debug_decl (decl);
1492
1493   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1494     initialized = get_init_value (set, loc, dv_from_decl (decl));
1495
1496   if (modify)
1497     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, set_src);
1498   var_mem_set (set, loc, initialized, set_src);
1499 }
1500
1501 /* Delete the location part LOC from dataflow set SET.  If CLOBBER is
1502    true, also delete any other live copies of the same variable part.
1503    Adjust the address first if it is stack pointer based.  */
1504
1505 static void
1506 var_mem_delete (dataflow_set *set, rtx loc, bool clobber)
1507 {
1508   tree decl = MEM_EXPR (loc);
1509   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1510
1511   decl = var_debug_decl (decl);
1512   if (clobber)
1513     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1514   delete_variable_part (set, loc, dv_from_decl (decl), offset);
1515 }
1516
1517 /* Map a value to a location it was just stored in.  */
1518
1519 static void
1520 val_store (dataflow_set *set, rtx val, rtx loc, rtx insn)
1521 {
1522   cselib_val *v = CSELIB_VAL_PTR (val);
1523
1524   gcc_assert (cselib_preserved_value_p (v));
1525
1526   if (dump_file)
1527     {
1528       fprintf (dump_file, "%i: ", INSN_UID (insn));
1529       print_inline_rtx (dump_file, val, 0);
1530       fprintf (dump_file, " stored in ");
1531       print_inline_rtx (dump_file, loc, 0);
1532       if (v->locs)
1533         {
1534           struct elt_loc_list *l;
1535           for (l = v->locs; l; l = l->next)
1536             {
1537               fprintf (dump_file, "\n%i: ", INSN_UID (l->setting_insn));
1538               print_inline_rtx (dump_file, l->loc, 0);
1539             }
1540         }
1541       fprintf (dump_file, "\n");
1542     }
1543
1544   if (REG_P (loc))
1545     {
1546       var_regno_delete (set, REGNO (loc));
1547       var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1548                         dv_from_value (val), 0, NULL_RTX, INSERT);
1549     }
1550   else if (MEM_P (loc))
1551     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1552                       dv_from_value (val), 0, NULL_RTX, INSERT);
1553   else
1554     set_variable_part (set, loc, dv_from_value (val), 0,
1555                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1556 }
1557
1558 /* Reset this node, detaching all its equivalences.  Return the slot
1559    in the variable hash table that holds dv, if there is one.  */
1560
1561 static void
1562 val_reset (dataflow_set *set, decl_or_value dv)
1563 {
1564   variable var = shared_hash_find (set->vars, dv) ;
1565   location_chain node;
1566   rtx cval;
1567
1568   if (!var || !var->n_var_parts)
1569     return;
1570
1571   gcc_assert (var->n_var_parts == 1);
1572
1573   cval = NULL;
1574   for (node = var->var_part[0].loc_chain; node; node = node->next)
1575     if (GET_CODE (node->loc) == VALUE
1576         && canon_value_cmp (node->loc, cval))
1577       cval = node->loc;
1578
1579   for (node = var->var_part[0].loc_chain; node; node = node->next)
1580     if (GET_CODE (node->loc) == VALUE && cval != node->loc)
1581       {
1582         /* Redirect the equivalence link to the new canonical
1583            value, or simply remove it if it would point at
1584            itself.  */
1585         if (cval)
1586           set_variable_part (set, cval, dv_from_value (node->loc),
1587                              0, node->init, node->set_src, NO_INSERT);
1588         delete_variable_part (set, dv_as_value (dv),
1589                               dv_from_value (node->loc), 0);
1590       }
1591
1592   if (cval)
1593     {
1594       decl_or_value cdv = dv_from_value (cval);
1595
1596       /* Keep the remaining values connected, accummulating links
1597          in the canonical value.  */
1598       for (node = var->var_part[0].loc_chain; node; node = node->next)
1599         {
1600           if (node->loc == cval)
1601             continue;
1602           else if (GET_CODE (node->loc) == REG)
1603             var_reg_decl_set (set, node->loc, node->init, cdv, 0,
1604                               node->set_src, NO_INSERT);
1605           else if (GET_CODE (node->loc) == MEM)
1606             var_mem_decl_set (set, node->loc, node->init, cdv, 0,
1607                               node->set_src, NO_INSERT);
1608           else
1609             set_variable_part (set, node->loc, cdv, 0,
1610                                node->init, node->set_src, NO_INSERT);
1611         }
1612     }
1613
1614   /* We remove this last, to make sure that the canonical value is not
1615      removed to the point of requiring reinsertion.  */
1616   if (cval)
1617     delete_variable_part (set, dv_as_value (dv), dv_from_value (cval), 0);
1618
1619   clobber_variable_part (set, NULL, dv, 0, NULL);
1620
1621   /* ??? Should we make sure there aren't other available values or
1622      variables whose values involve this one other than by
1623      equivalence?  E.g., at the very least we should reset MEMs, those
1624      shouldn't be too hard to find cselib-looking up the value as an
1625      address, then locating the resulting value in our own hash
1626      table.  */
1627 }
1628
1629 /* Find the values in a given location and map the val to another
1630    value, if it is unique, or add the location as one holding the
1631    value.  */
1632
1633 static void
1634 val_resolve (dataflow_set *set, rtx val, rtx loc, rtx insn)
1635 {
1636   decl_or_value dv = dv_from_value (val);
1637
1638   if (dump_file && (dump_flags & TDF_DETAILS))
1639     {
1640       if (insn)
1641         fprintf (dump_file, "%i: ", INSN_UID (insn));
1642       else
1643         fprintf (dump_file, "head: ");
1644       print_inline_rtx (dump_file, val, 0);
1645       fputs (" is at ", dump_file);
1646       print_inline_rtx (dump_file, loc, 0);
1647       fputc ('\n', dump_file);
1648     }
1649
1650   val_reset (set, dv);
1651
1652   if (REG_P (loc))
1653     {
1654       attrs node, found = NULL;
1655
1656       for (node = set->regs[REGNO (loc)]; node; node = node->next)
1657         if (dv_is_value_p (node->dv)
1658             && GET_MODE (dv_as_value (node->dv)) == GET_MODE (loc))
1659           {
1660             found = node;
1661
1662             /* Map incoming equivalences.  ??? Wouldn't it be nice if
1663              we just started sharing the location lists?  Maybe a
1664              circular list ending at the value itself or some
1665              such.  */
1666             set_variable_part (set, dv_as_value (node->dv),
1667                                dv_from_value (val), node->offset,
1668                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1669             set_variable_part (set, val, node->dv, node->offset,
1670                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1671           }
1672
1673       /* If we didn't find any equivalence, we need to remember that
1674          this value is held in the named register.  */
1675       if (!found)
1676         var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1677                           dv_from_value (val), 0, NULL_RTX, INSERT);
1678     }
1679   else if (MEM_P (loc))
1680     /* ??? Merge equivalent MEMs.  */
1681     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1682                       dv_from_value (val), 0, NULL_RTX, INSERT);
1683   else
1684     /* ??? Merge equivalent expressions.  */
1685     set_variable_part (set, loc, dv_from_value (val), 0,
1686                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1687 }
1688
1689 /* Initialize dataflow set SET to be empty. 
1690    VARS_SIZE is the initial size of hash table VARS.  */
1691
1692 static void
1693 dataflow_set_init (dataflow_set *set)
1694 {
1695   init_attrs_list_set (set->regs);
1696   set->vars = shared_hash_copy (empty_shared_hash);
1697   set->stack_adjust = 0;
1698   set->traversed_vars = NULL;
1699 }
1700
1701 /* Delete the contents of dataflow set SET.  */
1702
1703 static void
1704 dataflow_set_clear (dataflow_set *set)
1705 {
1706   int i;
1707
1708   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1709     attrs_list_clear (&set->regs[i]);
1710
1711   shared_hash_destroy (set->vars);
1712   set->vars = shared_hash_copy (empty_shared_hash);
1713 }
1714
1715 /* Copy the contents of dataflow set SRC to DST.  */
1716
1717 static void
1718 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
1719 {
1720   int i;
1721
1722   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1723     attrs_list_copy (&dst->regs[i], src->regs[i]);
1724
1725   shared_hash_destroy (dst->vars);
1726   dst->vars = shared_hash_copy (src->vars);
1727   dst->stack_adjust = src->stack_adjust;
1728 }
1729
1730 /* Information for merging lists of locations for a given offset of variable.
1731  */
1732 struct variable_union_info
1733 {
1734   /* Node of the location chain.  */
1735   location_chain lc;
1736
1737   /* The sum of positions in the input chains.  */
1738   int pos;
1739
1740   /* The position in the chain of DST dataflow set.  */
1741   int pos_dst;
1742 };
1743
1744 /* Buffer for location list sorting and its allocated size.  */
1745 static struct variable_union_info *vui_vec;
1746 static int vui_allocated;
1747
1748 /* Compare function for qsort, order the structures by POS element.  */
1749
1750 static int
1751 variable_union_info_cmp_pos (const void *n1, const void *n2)
1752 {
1753   const struct variable_union_info *const i1 =
1754     (const struct variable_union_info *) n1;
1755   const struct variable_union_info *const i2 =
1756     ( const struct variable_union_info *) n2;
1757
1758   if (i1->pos != i2->pos)
1759     return i1->pos - i2->pos;
1760   
1761   return (i1->pos_dst - i2->pos_dst);
1762 }
1763
1764 /* Compute union of location parts of variable *SLOT and the same variable
1765    from hash table DATA.  Compute "sorted" union of the location chains
1766    for common offsets, i.e. the locations of a variable part are sorted by
1767    a priority where the priority is the sum of the positions in the 2 chains
1768    (if a location is only in one list the position in the second list is
1769    defined to be larger than the length of the chains).
1770    When we are updating the location parts the newest location is in the
1771    beginning of the chain, so when we do the described "sorted" union
1772    we keep the newest locations in the beginning.  */
1773
1774 static int
1775 variable_union (void **slot, void *data)
1776 {
1777   variable src, dst;
1778   void **dstp;
1779   dataflow_set *set = (dataflow_set *) data;
1780   int i, j, k;
1781
1782   src = (variable) *slot;
1783   dstp = shared_hash_find_slot (set->vars, src->dv);
1784   if (!dstp || !*dstp)
1785     {
1786       src->refcount++;
1787
1788       dst_can_be_shared = false;
1789       if (!dstp)
1790         dstp = shared_hash_find_slot_unshare (&set->vars, src->dv, INSERT);
1791
1792       *dstp = src;
1793
1794       /* If CUR_LOC of some variable part is not the first element of
1795          the location chain we are going to change it so we have to make
1796          a copy of the variable.  */
1797       for (k = 0; k < src->n_var_parts; k++)
1798         {
1799           gcc_assert (!src->var_part[k].loc_chain
1800                       == !src->var_part[k].cur_loc);
1801           if (src->var_part[k].loc_chain)
1802             {
1803               gcc_assert (src->var_part[k].cur_loc);
1804               if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1805                 break;
1806             }
1807         }
1808       if (k < src->n_var_parts)
1809         dstp = unshare_variable (set, dstp, src, VAR_INIT_STATUS_UNKNOWN);
1810
1811       /* Continue traversing the hash table.  */
1812       return 1;
1813     }
1814   else
1815     dst = (variable) *dstp;
1816
1817   gcc_assert (src->n_var_parts);
1818
1819   /* We can combine one-part variables very efficiently, because their
1820      entries are in canonical order.  */
1821   if (dv_onepart_p (src->dv))
1822     {
1823       location_chain *nodep, dnode, snode;
1824
1825       gcc_assert (src->n_var_parts == 1);
1826       gcc_assert (dst->n_var_parts == 1);
1827
1828       snode = src->var_part[0].loc_chain;
1829       gcc_assert (snode);
1830
1831     restart_onepart_unshared:
1832       nodep = &dst->var_part[0].loc_chain;
1833       dnode = *nodep;
1834       gcc_assert (dnode);
1835
1836       while (snode)
1837         {
1838           int r = dnode ? loc_cmp (dnode->loc, snode->loc) : 1;
1839
1840           if (r > 0)
1841             {
1842               location_chain nnode;
1843
1844               if (dst->refcount != 1 || shared_hash_shared (set->vars))
1845                 {
1846                   dstp = unshare_variable (set, dstp, dst,
1847                                            VAR_INIT_STATUS_INITIALIZED);
1848                   dst = (variable)*dstp;
1849                   goto restart_onepart_unshared;
1850                 }
1851
1852               *nodep = nnode = (location_chain) pool_alloc (loc_chain_pool);
1853               nnode->loc = snode->loc;
1854               nnode->init = snode->init;
1855               if (!snode->set_src || MEM_P (snode->set_src))
1856                 nnode->set_src = NULL;
1857               else
1858                 nnode->set_src = snode->set_src;
1859               nnode->next = dnode;
1860               dnode = nnode;
1861             }
1862 #ifdef ENABLE_CHECKING
1863           else if (r == 0)
1864             gcc_assert (rtx_equal_p (dnode->loc, snode->loc));
1865 #endif
1866
1867           if (r >= 0)
1868             snode = snode->next;
1869
1870           nodep = &dnode->next;
1871           dnode = *nodep;
1872         }
1873
1874       dst->var_part[0].cur_loc = dst->var_part[0].loc_chain->loc;
1875
1876       return 1;
1877     }
1878
1879   /* Count the number of location parts, result is K.  */
1880   for (i = 0, j = 0, k = 0;
1881        i < src->n_var_parts && j < dst->n_var_parts; k++)
1882     {
1883       if (src->var_part[i].offset == dst->var_part[j].offset)
1884         {
1885           i++;
1886           j++;
1887         }
1888       else if (src->var_part[i].offset < dst->var_part[j].offset)
1889         i++;
1890       else
1891         j++;
1892     }
1893   k += src->n_var_parts - i;
1894   k += dst->n_var_parts - j;
1895
1896   /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1897      thus there are at most MAX_VAR_PARTS different offsets.  */
1898   gcc_assert (dv_onepart_p (dst->dv) ? k == 1 : k <= MAX_VAR_PARTS);
1899
1900   if ((dst->refcount > 1 || shared_hash_shared (set->vars))
1901       && dst->n_var_parts != k)
1902     {
1903       dstp = unshare_variable (set, dstp, dst, VAR_INIT_STATUS_UNKNOWN);
1904       dst = (variable)*dstp;
1905     }
1906
1907   i = src->n_var_parts - 1;
1908   j = dst->n_var_parts - 1;
1909   dst->n_var_parts = k;
1910
1911   for (k--; k >= 0; k--)
1912     {
1913       location_chain node, node2;
1914
1915       if (i >= 0 && j >= 0
1916           && src->var_part[i].offset == dst->var_part[j].offset)
1917         {
1918           /* Compute the "sorted" union of the chains, i.e. the locations which
1919              are in both chains go first, they are sorted by the sum of
1920              positions in the chains.  */
1921           int dst_l, src_l;
1922           int ii, jj, n;
1923           struct variable_union_info *vui;
1924
1925           /* If DST is shared compare the location chains.
1926              If they are different we will modify the chain in DST with
1927              high probability so make a copy of DST.  */
1928           if (dst->refcount > 1 || shared_hash_shared (set->vars))
1929             {
1930               for (node = src->var_part[i].loc_chain,
1931                    node2 = dst->var_part[j].loc_chain; node && node2;
1932                    node = node->next, node2 = node2->next)
1933                 {
1934                   if (!((REG_P (node2->loc)
1935                          && REG_P (node->loc)
1936                          && REGNO (node2->loc) == REGNO (node->loc))
1937                         || rtx_equal_p (node2->loc, node->loc)))
1938                     {
1939                       if (node2->init < node->init)
1940                         node2->init = node->init;
1941                       break;
1942                     }
1943                 }
1944               if (node || node2)
1945                 {
1946                   dstp = unshare_variable (set, dstp, dst,
1947                                            VAR_INIT_STATUS_UNKNOWN);
1948                   dst = (variable)*dstp;
1949                 }
1950             }
1951
1952           src_l = 0;
1953           for (node = src->var_part[i].loc_chain; node; node = node->next)
1954             src_l++;
1955           dst_l = 0;
1956           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1957             dst_l++;
1958
1959           if (dst_l == 1)
1960             {
1961               /* The most common case, much simpler, no qsort is needed.  */
1962               location_chain dstnode = dst->var_part[j].loc_chain;
1963               dst->var_part[k].loc_chain = dstnode;
1964               dst->var_part[k].offset = dst->var_part[j].offset;
1965               node2 = dstnode;
1966               for (node = src->var_part[i].loc_chain; node; node = node->next)
1967                 if (!((REG_P (dstnode->loc)
1968                        && REG_P (node->loc)
1969                        && REGNO (dstnode->loc) == REGNO (node->loc))
1970                       || rtx_equal_p (dstnode->loc, node->loc)))
1971                   {
1972                     location_chain new_node;
1973
1974                     /* Copy the location from SRC.  */
1975                     new_node = (location_chain) pool_alloc (loc_chain_pool);
1976                     new_node->loc = node->loc;
1977                     new_node->init = node->init;
1978                     if (!node->set_src || MEM_P (node->set_src))
1979                       new_node->set_src = NULL;
1980                     else
1981                       new_node->set_src = node->set_src;
1982                     node2->next = new_node;
1983                     node2 = new_node;
1984                   }
1985               node2->next = NULL;
1986             }
1987           else
1988             {
1989               if (src_l + dst_l > vui_allocated)
1990                 {
1991                   vui_allocated = MAX (vui_allocated * 2, src_l + dst_l);
1992                   vui_vec = XRESIZEVEC (struct variable_union_info, vui_vec,
1993                                         vui_allocated);
1994                 }
1995               vui = vui_vec;
1996
1997               /* Fill in the locations from DST.  */
1998               for (node = dst->var_part[j].loc_chain, jj = 0; node;
1999                    node = node->next, jj++)
2000                 {
2001                   vui[jj].lc = node;
2002                   vui[jj].pos_dst = jj;
2003
2004                   /* Pos plus value larger than a sum of 2 valid positions.  */
2005                   vui[jj].pos = jj + src_l + dst_l;
2006                 }
2007
2008               /* Fill in the locations from SRC.  */
2009               n = dst_l;
2010               for (node = src->var_part[i].loc_chain, ii = 0; node;
2011                    node = node->next, ii++)
2012                 {
2013                   /* Find location from NODE.  */
2014                   for (jj = 0; jj < dst_l; jj++)
2015                     {
2016                       if ((REG_P (vui[jj].lc->loc)
2017                            && REG_P (node->loc)
2018                            && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
2019                           || rtx_equal_p (vui[jj].lc->loc, node->loc))
2020                         {
2021                           vui[jj].pos = jj + ii;
2022                           break;
2023                         }
2024                     }
2025                   if (jj >= dst_l)      /* The location has not been found.  */
2026                     {
2027                       location_chain new_node;
2028
2029                       /* Copy the location from SRC.  */
2030                       new_node = (location_chain) pool_alloc (loc_chain_pool);
2031                       new_node->loc = node->loc;
2032                       new_node->init = node->init;
2033                       if (!node->set_src || MEM_P (node->set_src))
2034                         new_node->set_src = NULL;
2035                       else
2036                         new_node->set_src = node->set_src;
2037                       vui[n].lc = new_node;
2038                       vui[n].pos_dst = src_l + dst_l;
2039                       vui[n].pos = ii + src_l + dst_l;
2040                       n++;
2041                     }
2042                 }
2043
2044               if (dst_l == 2)
2045                 {
2046                   /* Special case still very common case.  For dst_l == 2
2047                      all entries dst_l ... n-1 are sorted, with for i >= dst_l
2048                      vui[i].pos == i + src_l + dst_l.  */
2049                   if (vui[0].pos > vui[1].pos)
2050                     {
2051                       /* Order should be 1, 0, 2... */
2052                       dst->var_part[k].loc_chain = vui[1].lc;
2053                       vui[1].lc->next = vui[0].lc;
2054                       if (n >= 3)
2055                         {
2056                           vui[0].lc->next = vui[2].lc;
2057                           vui[n - 1].lc->next = NULL;
2058                         }
2059                       else
2060                         vui[0].lc->next = NULL;
2061                       ii = 3;
2062                     }
2063                   else
2064                     {
2065                       dst->var_part[k].loc_chain = vui[0].lc;
2066                       if (n >= 3 && vui[2].pos < vui[1].pos)
2067                         {
2068                           /* Order should be 0, 2, 1, 3... */
2069                           vui[0].lc->next = vui[2].lc;
2070                           vui[2].lc->next = vui[1].lc;
2071                           if (n >= 4)
2072                             {
2073                               vui[1].lc->next = vui[3].lc;
2074                               vui[n - 1].lc->next = NULL;
2075                             }
2076                           else
2077                             vui[1].lc->next = NULL;
2078                           ii = 4;
2079                         }
2080                       else
2081                         {
2082                           /* Order should be 0, 1, 2... */
2083                           ii = 1;
2084                           vui[n - 1].lc->next = NULL;
2085                         }
2086                     }
2087                   for (; ii < n; ii++)
2088                     vui[ii - 1].lc->next = vui[ii].lc;
2089                 }
2090               else
2091                 {
2092                   qsort (vui, n, sizeof (struct variable_union_info),
2093                          variable_union_info_cmp_pos);
2094
2095                   /* Reconnect the nodes in sorted order.  */
2096                   for (ii = 1; ii < n; ii++)
2097                     vui[ii - 1].lc->next = vui[ii].lc;
2098                   vui[n - 1].lc->next = NULL;
2099                   dst->var_part[k].loc_chain = vui[0].lc;
2100                 }
2101
2102               dst->var_part[k].offset = dst->var_part[j].offset;
2103             }
2104           i--;
2105           j--;
2106         }
2107       else if ((i >= 0 && j >= 0
2108                 && src->var_part[i].offset < dst->var_part[j].offset)
2109                || i < 0)
2110         {
2111           dst->var_part[k] = dst->var_part[j];
2112           j--;
2113         }
2114       else if ((i >= 0 && j >= 0
2115                 && src->var_part[i].offset > dst->var_part[j].offset)
2116                || j < 0)
2117         {
2118           location_chain *nextp;
2119
2120           /* Copy the chain from SRC.  */
2121           nextp = &dst->var_part[k].loc_chain;
2122           for (node = src->var_part[i].loc_chain; node; node = node->next)
2123             {
2124               location_chain new_lc;
2125
2126               new_lc = (location_chain) pool_alloc (loc_chain_pool);
2127               new_lc->next = NULL;
2128               new_lc->init = node->init;
2129               if (!node->set_src || MEM_P (node->set_src))
2130                 new_lc->set_src = NULL;
2131               else
2132                 new_lc->set_src = node->set_src;
2133               new_lc->loc = node->loc;
2134
2135               *nextp = new_lc;
2136               nextp = &new_lc->next;
2137             }
2138
2139           dst->var_part[k].offset = src->var_part[i].offset;
2140           i--;
2141         }
2142
2143       /* We are at the basic block boundary when computing union
2144          so set the CUR_LOC to be the first element of the chain.  */
2145       if (dst->var_part[k].loc_chain)
2146         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
2147       else
2148         dst->var_part[k].cur_loc = NULL;
2149     }
2150
2151   if (flag_var_tracking_uninit)
2152     for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++)
2153       {
2154         location_chain node, node2;
2155         for (node = src->var_part[i].loc_chain; node; node = node->next)
2156           for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next)
2157             if (rtx_equal_p (node->loc, node2->loc))
2158               {
2159                 if (node->init > node2->init)
2160                   node2->init = node->init;
2161               }
2162       }
2163
2164   /* Continue traversing the hash table.  */
2165   return 1;
2166 }
2167
2168 /* Like variable_union, but only used when doing dataflow_set_union
2169    into an empty hashtab.  To allow sharing, dst is initially shared
2170    with src (so all variables are "copied" from src to dst hashtab),
2171    so only unshare_variable for variables that need canonicalization
2172    are needed.  */
2173
2174 static int
2175 variable_canonicalize (void **slot, void *data)
2176 {
2177   variable src;
2178   dataflow_set *set = (dataflow_set *) data;
2179   int k;
2180
2181   src = *(variable *) slot;
2182
2183   /* If CUR_LOC of some variable part is not the first element of
2184      the location chain we are going to change it so we have to make
2185      a copy of the variable.  */
2186   for (k = 0; k < src->n_var_parts; k++)
2187     {
2188       gcc_assert (!src->var_part[k].loc_chain == !src->var_part[k].cur_loc);
2189       if (src->var_part[k].loc_chain)
2190         {
2191           gcc_assert (src->var_part[k].cur_loc);
2192           if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
2193             break;
2194         }
2195     }
2196   if (k < src->n_var_parts)
2197     slot = unshare_variable (set, slot, src, VAR_INIT_STATUS_UNKNOWN);
2198   return 1;
2199 }
2200
2201 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
2202
2203 static void
2204 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
2205 {
2206   int i;
2207
2208   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2209     attrs_list_union (&dst->regs[i], src->regs[i]);
2210
2211   if (dst->vars == empty_shared_hash)
2212     {
2213       shared_hash_destroy (dst->vars);
2214       dst->vars = shared_hash_copy (src->vars);
2215       dst->traversed_vars = dst->vars;
2216       htab_traverse (shared_hash_htab (dst->vars), variable_canonicalize, dst);
2217       dst->traversed_vars = NULL;
2218     }
2219   else
2220     htab_traverse (shared_hash_htab (src->vars), variable_union, dst);
2221 }
2222
2223 /* Whether the value is currently being expanded.  */
2224 #define VALUE_RECURSED_INTO(x) \
2225   (RTL_FLAG_CHECK1 ("VALUE_RECURSED_INTO", (x), VALUE)->used)
2226 /* Whether the value is in changed_variables hash table.  */
2227 #define VALUE_CHANGED(x) \
2228   (RTL_FLAG_CHECK1 ("VALUE_CHANGED", (x), VALUE)->frame_related)
2229 /* Whether the decl is in changed_variables hash table.  */
2230 #define DECL_CHANGED(x) TREE_VISITED (x)
2231
2232 /* Record that DV has been added into resp. removed from changed_variables
2233    hashtable.  */
2234
2235 static inline void
2236 set_dv_changed (decl_or_value dv, bool newv)
2237 {
2238   if (dv_is_value_p (dv))
2239     VALUE_CHANGED (dv_as_value (dv)) = newv;
2240   else
2241     DECL_CHANGED (dv_as_decl (dv)) = newv;
2242 }
2243
2244 /* Return true if DV is present in changed_variables hash table.  */
2245
2246 static inline bool
2247 dv_changed_p (decl_or_value dv)
2248 {
2249   return (dv_is_value_p (dv)
2250           ? VALUE_CHANGED (dv_as_value (dv))
2251           : DECL_CHANGED (dv_as_decl (dv)));
2252 }
2253
2254 /* Return a location list node whose loc is rtx_equal to LOC, in the
2255    location list of a one-part variable or value VAR, or in that of
2256    any values recursively mentioned in the location lists.  */
2257
2258 static location_chain
2259 find_loc_in_1pdv (rtx loc, variable var, htab_t vars)
2260 {
2261   location_chain node;
2262
2263   if (!var)
2264     return NULL;
2265
2266   gcc_assert (dv_onepart_p (var->dv));
2267
2268   if (!var->n_var_parts)
2269     return NULL;
2270
2271   gcc_assert (var->var_part[0].offset == 0);
2272
2273   for (node = var->var_part[0].loc_chain; node; node = node->next)
2274     if (rtx_equal_p (loc, node->loc))
2275       return node;
2276     else if (GET_CODE (node->loc) == VALUE
2277              && !VALUE_RECURSED_INTO (node->loc))
2278       {
2279         decl_or_value dv = dv_from_value (node->loc);
2280         variable var = (variable)
2281                        htab_find_with_hash (vars, dv, dv_htab_hash (dv));
2282
2283         if (var)
2284           {
2285             location_chain where;
2286             VALUE_RECURSED_INTO (node->loc) = true;
2287             if ((where = find_loc_in_1pdv (loc, var, vars)))
2288               {
2289                 VALUE_RECURSED_INTO (node->loc) = false;
2290                 return where;
2291               }
2292             VALUE_RECURSED_INTO (node->loc) = false;
2293           }
2294       }
2295
2296   return NULL;
2297 }
2298
2299 /* Hash table iteration argument passed to variable_merge.  */
2300 struct dfset_merge
2301 {
2302   /* The set in which the merge is to be inserted.  */
2303   dataflow_set *dst;
2304   /* The set that we're iterating in.  */
2305   dataflow_set *cur;
2306   /* The set that may contain the other dv we are to merge with.  */
2307   dataflow_set *src;
2308   /* Number of onepart dvs in src.  */
2309   int src_onepart_cnt;
2310 };
2311
2312 /* Insert LOC in *DNODE, if it's not there yet.  The list must be in
2313    loc_cmp order, and it is maintained as such.  */
2314
2315 static void
2316 insert_into_intersection (location_chain *nodep, rtx loc,
2317                           enum var_init_status status)
2318 {
2319   location_chain node;
2320   int r;
2321
2322   for (node = *nodep; node; nodep = &node->next, node = *nodep)
2323     if ((r = loc_cmp (node->loc, loc)) == 0)
2324       {
2325         node->init = MIN (node->init, status);
2326         return;
2327       }
2328     else if (r > 0)
2329       break;
2330
2331   node = (location_chain) pool_alloc (loc_chain_pool);
2332
2333   node->loc = loc;
2334   node->set_src = NULL;
2335   node->init = status;
2336   node->next = *nodep;
2337   *nodep = node;
2338 }
2339
2340 /* Insert in DEST the intersection the locations present in both
2341    S1NODE and S2VAR, directly or indirectly.  S1NODE is from a
2342    variable in DSM->cur, whereas S2VAR is from DSM->src.  dvar is in
2343    DSM->dst.  */
2344
2345 static void
2346 intersect_loc_chains (rtx val, location_chain *dest, struct dfset_merge *dsm,
2347                       location_chain s1node, variable s2var)
2348 {
2349   dataflow_set *s1set = dsm->cur;
2350   dataflow_set *s2set = dsm->src;
2351   location_chain found;
2352
2353   for (; s1node; s1node = s1node->next)
2354     {
2355       if (s1node->loc == val)
2356         continue;
2357
2358       if ((found = find_loc_in_1pdv (s1node->loc, s2var,
2359                                      shared_hash_htab (s2set->vars))))
2360         {
2361           insert_into_intersection (dest, s1node->loc,
2362                                     MIN (s1node->init, found->init));
2363           continue;
2364         }
2365
2366       if (GET_CODE (s1node->loc) == VALUE
2367           && !VALUE_RECURSED_INTO (s1node->loc))
2368         {
2369           decl_or_value dv = dv_from_value (s1node->loc);
2370           variable svar = shared_hash_find (s1set->vars, dv);
2371           if (svar)
2372             {
2373               if (svar->n_var_parts == 1)
2374                 {
2375                   VALUE_RECURSED_INTO (s1node->loc) = true;
2376                   intersect_loc_chains (val, dest, dsm,
2377                                         svar->var_part[0].loc_chain,
2378                                         s2var);
2379                   VALUE_RECURSED_INTO (s1node->loc) = false;
2380                 }
2381             }
2382         }
2383
2384       /* ??? if the location is equivalent to any location in src,
2385          searched recursively
2386
2387            add to dst the values needed to represent the equivalence
2388
2389      telling whether locations S is equivalent to another dv's
2390      location list:
2391
2392        for each location D in the list
2393
2394          if S and D satisfy rtx_equal_p, then it is present
2395
2396          else if D is a value, recurse without cycles
2397
2398          else if S and D have the same CODE and MODE
2399
2400            for each operand oS and the corresponding oD
2401
2402              if oS and oD are not equivalent, then S an D are not equivalent
2403
2404              else if they are RTX vectors
2405
2406                if any vector oS element is not equivalent to its respective oD,
2407                then S and D are not equivalent
2408
2409    */
2410
2411
2412     }
2413 }
2414
2415 /* Return -1 if X should be before Y in a location list for a 1-part
2416    variable, 1 if Y should be before X, and 0 if they're equivalent
2417    and should not appear in the list.  */
2418
2419 static int
2420 loc_cmp (rtx x, rtx y)
2421 {
2422   int i, j, r;
2423   RTX_CODE code = GET_CODE (x);
2424   const char *fmt;
2425
2426   if (x == y)
2427     return 0;
2428
2429   if (REG_P (x))
2430     {
2431       if (!REG_P (y))
2432         return -1;
2433       gcc_assert (GET_MODE (x) == GET_MODE (y));
2434       if (REGNO (x) == REGNO (y))
2435         return 0;
2436       else if (REGNO (x) < REGNO (y))
2437         return -1;
2438       else
2439         return 1;
2440     }
2441
2442   if (REG_P (y))
2443     return 1;
2444
2445   if (MEM_P (x))
2446     {
2447       if (!MEM_P (y))
2448         return -1;
2449       gcc_assert (GET_MODE (x) == GET_MODE (y));
2450       return loc_cmp (XEXP (x, 0), XEXP (y, 0));
2451     }
2452
2453   if (MEM_P (y))
2454     return 1;
2455
2456   if (GET_CODE (x) == VALUE)
2457     {
2458       if (GET_CODE (y) != VALUE)
2459         return -1;
2460       gcc_assert (GET_MODE (x) == GET_MODE (y));
2461       if (canon_value_cmp (x, y))
2462         return -1;
2463       else
2464         return 1;
2465     }
2466
2467   if (GET_CODE (y) == VALUE)
2468     return 1;
2469
2470   if (GET_CODE (x) == GET_CODE (y))
2471     /* Compare operands below.  */;
2472   else if (GET_CODE (x) < GET_CODE (y))
2473     return -1;
2474   else
2475     return 1;
2476
2477   gcc_assert (GET_MODE (x) == GET_MODE (y));
2478
2479   fmt = GET_RTX_FORMAT (code);
2480   for (i = 0; i < GET_RTX_LENGTH (code); i++)
2481     switch (fmt[i])
2482       {
2483       case 'w':
2484         if (XWINT (x, i) == XWINT (y, i))
2485           break;
2486         else if (XWINT (x, i) < XWINT (y, i))
2487           return -1;
2488         else
2489           return 1;
2490
2491       case 'n':
2492       case 'i':
2493         if (XINT (x, i) == XINT (y, i))
2494           break;
2495         else if (XINT (x, i) < XINT (y, i))
2496           return -1;
2497         else
2498           return 1;
2499
2500       case 'V':
2501       case 'E':
2502         /* Compare the vector length first.  */
2503         if (XVECLEN (x, i) == XVECLEN (y, i))
2504           /* Compare the vectors elements.  */;
2505         else if (XVECLEN (x, i) < XVECLEN (y, i))
2506           return -1;
2507         else
2508           return 1;
2509
2510         for (j = 0; j < XVECLEN (x, i); j++)
2511           if ((r = loc_cmp (XVECEXP (x, i, j),
2512                             XVECEXP (y, i, j))))
2513             return r;
2514         break;
2515
2516       case 'e':
2517         if ((r = loc_cmp (XEXP (x, i), XEXP (y, i))))
2518           return r;
2519         break;
2520
2521       case 'S':
2522       case 's':
2523         if (XSTR (x, i) == XSTR (y, i))
2524           break;
2525         if (!XSTR (x, i))
2526           return -1;
2527         if (!XSTR (y, i))
2528           return 1;
2529         if ((r = strcmp (XSTR (x, i), XSTR (y, i))) == 0)
2530           break;
2531         else if (r < 0)
2532           return -1;
2533         else
2534           return 1;
2535
2536       case 'u':
2537         /* These are just backpointers, so they don't matter.  */
2538         break;
2539
2540       case '0':
2541       case 't':
2542         break;
2543
2544         /* It is believed that rtx's at this level will never
2545            contain anything but integers and other rtx's,
2546            except for within LABEL_REFs and SYMBOL_REFs.  */
2547       default:
2548         gcc_unreachable ();
2549       }
2550
2551   return 0;
2552 }
2553
2554 /* If decl or value DVP refers to VALUE from *LOC, add backlinks
2555    from VALUE to DVP.  */
2556
2557 static int
2558 add_value_chain (rtx *loc, void *dvp)
2559 {
2560   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2561     {
2562       decl_or_value dv = (decl_or_value) dvp;
2563       decl_or_value ldv = dv_from_value (*loc);
2564       value_chain vc, nvc;
2565       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2566                                               dv_htab_hash (ldv), INSERT);
2567       if (!*slot)
2568         {
2569           vc = (value_chain) pool_alloc (value_chain_pool);
2570           vc->dv = ldv;
2571           vc->next = NULL;
2572           vc->refcount = 0;
2573           *slot = (void *) vc;
2574         }
2575       else
2576         {
2577           for (vc = ((value_chain) *slot)->next; vc; vc = vc->next)
2578             if (dv_as_opaque (vc->dv) == dv_as_opaque (dv))
2579               break;
2580           if (vc)
2581             {
2582               vc->refcount++;
2583               return 0;
2584             }
2585         }
2586       vc = (value_chain) *slot;
2587       nvc = (value_chain) pool_alloc (value_chain_pool);
2588       nvc->dv = dv;
2589       nvc->next = vc->next;
2590       nvc->refcount = 1;
2591       vc->next = nvc;
2592     }
2593   return 0;
2594 }
2595
2596 /* If decl or value DVP refers to VALUEs from within LOC, add backlinks
2597    from those VALUEs to DVP.  */
2598
2599 static void
2600 add_value_chains (decl_or_value dv, rtx loc)
2601 {
2602   if (GET_CODE (loc) == VALUE)
2603     {
2604       add_value_chain (&loc, dv_as_opaque (dv));
2605       return;
2606     }
2607   if (REG_P (loc))
2608     return;
2609   if (MEM_P (loc))
2610     loc = XEXP (loc, 0);
2611   for_each_rtx (&loc, add_value_chain, dv_as_opaque (dv));
2612 }
2613
2614 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, add backlinks from those
2615    VALUEs to DV.  */
2616
2617 static void
2618 add_cselib_value_chains (decl_or_value dv)
2619 {
2620   struct elt_loc_list *l;
2621
2622   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2623     for_each_rtx (&l->loc, add_value_chain, dv_as_opaque (dv));
2624 }
2625
2626 /* If decl or value DVP refers to VALUE from *LOC, remove backlinks
2627    from VALUE to DVP.  */
2628
2629 static int
2630 remove_value_chain (rtx *loc, void *dvp)
2631 {
2632   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2633     {
2634       decl_or_value dv = (decl_or_value) dvp;
2635       decl_or_value ldv = dv_from_value (*loc);
2636       value_chain vc, dvc = NULL;
2637       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2638                                               dv_htab_hash (ldv), NO_INSERT);
2639       for (vc = (value_chain) *slot; vc->next; vc = vc->next)
2640         if (dv_as_opaque (vc->next->dv) == dv_as_opaque (dv))
2641           {
2642             dvc = vc->next;
2643             gcc_assert (dvc->refcount > 0);
2644             if (--dvc->refcount == 0)
2645               {
2646                 vc->next = dvc->next;
2647                 pool_free (value_chain_pool, dvc);
2648                 if (vc->next == NULL && vc == (value_chain) *slot)
2649                   {
2650                     pool_free (value_chain_pool, vc);
2651                     htab_clear_slot (value_chains, slot);
2652                   }
2653               }
2654             return 0;
2655           }
2656       gcc_unreachable ();
2657     }
2658   return 0;
2659 }
2660
2661 /* If decl or value DVP refers to VALUEs from within LOC, remove backlinks
2662    from those VALUEs to DVP.  */
2663
2664 static void
2665 remove_value_chains (decl_or_value dv, rtx loc)
2666 {
2667   if (GET_CODE (loc) == VALUE)
2668     {
2669       remove_value_chain (&loc, dv_as_opaque (dv));
2670       return;
2671     }
2672   if (REG_P (loc))
2673     return;
2674   if (MEM_P (loc))
2675     loc = XEXP (loc, 0);
2676   for_each_rtx (&loc, remove_value_chain, dv_as_opaque (dv));
2677 }
2678
2679 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, remove backlinks from those
2680    VALUEs to DV.  */
2681
2682 static void
2683 remove_cselib_value_chains (decl_or_value dv)
2684 {
2685   struct elt_loc_list *l;
2686
2687   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2688     for_each_rtx (&l->loc, remove_value_chain, dv_as_opaque (dv));
2689 }
2690
2691 #if ENABLE_CHECKING
2692 /* Check the order of entries in one-part variables.   */
2693
2694 static int
2695 canonicalize_loc_order_check (void **slot, void *data ATTRIBUTE_UNUSED)
2696 {
2697   variable var = (variable) *slot;
2698   decl_or_value dv = var->dv;
2699   location_chain node, next;
2700
2701   if (!dv_onepart_p (dv))
2702     return 1;
2703
2704   gcc_assert (var->n_var_parts == 1);
2705   node = var->var_part[0].loc_chain;
2706   gcc_assert (node);
2707
2708   while ((next = node->next))
2709     {
2710       gcc_assert (loc_cmp (node->loc, next->loc) < 0);
2711       node = next;
2712     }
2713
2714   return 1;
2715 }
2716 #endif
2717
2718 /* Mark with VALUE_RECURSED_INTO values that have neighbors that are
2719    more likely to be chosen as canonical for an equivalence set.
2720    Ensure less likely values can reach more likely neighbors, making
2721    the connections bidirectional.  */
2722
2723 static int
2724 canonicalize_values_mark (void **slot, void *data)
2725 {
2726   dataflow_set *set = (dataflow_set *)data;
2727   variable var = (variable) *slot;
2728   decl_or_value dv = var->dv;
2729   rtx val;
2730   location_chain node;
2731
2732   if (!dv_is_value_p (dv))
2733     return 1;
2734
2735   gcc_assert (var->n_var_parts == 1);
2736
2737   val = dv_as_value (dv);
2738
2739   for (node = var->var_part[0].loc_chain; node; node = node->next)
2740     if (GET_CODE (node->loc) == VALUE)
2741       {
2742         if (canon_value_cmp (node->loc, val))
2743           VALUE_RECURSED_INTO (val) = true;
2744         else
2745           {
2746             decl_or_value odv = dv_from_value (node->loc);
2747             void **oslot = shared_hash_find_slot_noinsert (set->vars, odv);
2748
2749             oslot = set_slot_part (set, val, oslot, odv, 0,
2750                                    node->init, NULL_RTX);
2751
2752             VALUE_RECURSED_INTO (node->loc) = true;
2753           }
2754       }
2755
2756   return 1;
2757 }
2758
2759 /* Remove redundant entries from equivalence lists in onepart
2760    variables, canonicalizing equivalence sets into star shapes.  */
2761
2762 static int
2763 canonicalize_values_star (void **slot, void *data)
2764 {
2765   dataflow_set *set = (dataflow_set *)data;
2766   variable var = (variable) *slot;
2767   decl_or_value dv = var->dv;
2768   location_chain node;
2769   decl_or_value cdv;
2770   rtx val, cval;
2771   void **cslot;
2772   bool has_value;
2773   bool has_marks;
2774
2775   if (!dv_onepart_p (dv))
2776     return 1;
2777
2778   gcc_assert (var->n_var_parts == 1);
2779
2780   if (dv_is_value_p (dv))
2781     {
2782       cval = dv_as_value (dv);
2783       if (!VALUE_RECURSED_INTO (cval))
2784         return 1;
2785       VALUE_RECURSED_INTO (cval) = false;
2786     }
2787   else
2788     cval = NULL_RTX;
2789
2790  restart:
2791   val = cval;
2792   has_value = false;
2793   has_marks = false;
2794
2795   gcc_assert (var->n_var_parts == 1);
2796
2797   for (node = var->var_part[0].loc_chain; node; node = node->next)
2798     if (GET_CODE (node->loc) == VALUE)
2799       {
2800         has_value = true;
2801         if (VALUE_RECURSED_INTO (node->loc))
2802           has_marks = true;
2803         if (canon_value_cmp (node->loc, cval))
2804           cval = node->loc;
2805       }
2806
2807   if (!has_value)
2808     return 1;
2809
2810   if (cval == val)
2811     {
2812       if (!has_marks || dv_is_decl_p (dv))
2813         return 1;
2814
2815       /* Keep it marked so that we revisit it, either after visiting a
2816          child node, or after visiting a new parent that might be
2817          found out.  */
2818       VALUE_RECURSED_INTO (val) = true;
2819
2820       for (node = var->var_part[0].loc_chain; node; node = node->next)
2821         if (GET_CODE (node->loc) == VALUE
2822             && VALUE_RECURSED_INTO (node->loc))
2823           {
2824             cval = node->loc;
2825           restart_with_cval:
2826             VALUE_RECURSED_INTO (cval) = false;
2827             dv = dv_from_value (cval);
2828             slot = shared_hash_find_slot_noinsert (set->vars, dv);
2829             if (!slot)
2830               {
2831                 gcc_assert (dv_is_decl_p (var->dv));
2832                 /* The canonical value was reset and dropped.
2833                    Remove it.  */
2834                 clobber_variable_part (set, NULL, var->dv, 0, NULL);
2835                 return 1;
2836               }
2837             var = (variable)*slot;
2838             gcc_assert (dv_is_value_p (var->dv));
2839             if (var->n_var_parts == 0)
2840               return 1;
2841             gcc_assert (var->n_var_parts == 1);
2842             goto restart;
2843           }
2844
2845       VALUE_RECURSED_INTO (val) = false;
2846
2847       return 1;
2848     }
2849
2850   /* Push values to the canonical one.  */
2851   cdv = dv_from_value (cval);
2852   cslot = shared_hash_find_slot_noinsert (set->vars, cdv);
2853
2854   for (node = var->var_part[0].loc_chain; node; node = node->next)
2855     if (node->loc != cval)
2856       {
2857         cslot = set_slot_part (set, node->loc, cslot, cdv, 0,
2858                                node->init, NULL_RTX);
2859         if (GET_CODE (node->loc) == VALUE)
2860           {
2861             decl_or_value ndv = dv_from_value (node->loc);
2862
2863             set_variable_part (set, cval, ndv, 0, node->init, NULL_RTX,
2864                                NO_INSERT);
2865
2866             if (canon_value_cmp (node->loc, val))
2867               {
2868                 /* If it could have been a local minimum, it's not any more,
2869                    since it's now neighbor to cval, so it may have to push
2870                    to it.  Conversely, if it wouldn't have prevailed over
2871                    val, then whatever mark it has is fine: if it was to
2872                    push, it will now push to a more canonical node, but if
2873                    it wasn't, then it has already pushed any values it might
2874                    have to.  */
2875                 VALUE_RECURSED_INTO (node->loc) = true;
2876                 /* Make sure we visit node->loc by ensuring we cval is
2877                    visited too.  */
2878                 VALUE_RECURSED_INTO (cval) = true;
2879               }
2880             else if (!VALUE_RECURSED_INTO (node->loc))
2881               /* If we have no need to "recurse" into this node, it's
2882                  already "canonicalized", so drop the link to the old
2883                  parent.  */
2884               clobber_variable_part (set, cval, ndv, 0, NULL);
2885           }
2886         else if (GET_CODE (node->loc) == REG)
2887           {
2888             attrs list = set->regs[REGNO (node->loc)], *listp;
2889
2890             /* Change an existing attribute referring to dv so that it
2891                refers to cdv, removing any duplicate this might
2892                introduce, and checking that no previous duplicates
2893                existed, all in a single pass.  */
2894
2895             while (list)
2896               {
2897                 if (list->offset == 0
2898                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2899                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2900                   break;
2901
2902                 list = list->next;
2903               }
2904
2905             gcc_assert (list);
2906             if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2907               {
2908                 list->dv = cdv;
2909                 for (listp = &list->next; (list = *listp); listp = &list->next)
2910                   {
2911                     if (list->offset)
2912                       continue;
2913
2914                     if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2915                       {
2916                         *listp = list->next;
2917                         pool_free (attrs_pool, list);
2918                         list = *listp;
2919                         break;
2920                       }
2921
2922                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (dv));
2923                   }
2924               }
2925             else if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2926               {
2927                 for (listp = &list->next; (list = *listp); listp = &list->next)
2928                   {
2929                     if (list->offset)
2930                       continue;
2931
2932                     if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2933                       {
2934                         *listp = list->next;
2935                         pool_free (attrs_pool, list);
2936                         list = *listp;
2937                         break;
2938                       }
2939
2940                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (cdv));
2941                   }
2942               }
2943             else
2944               gcc_unreachable ();
2945
2946 #if ENABLE_CHECKING
2947             while (list)
2948               {
2949                 if (list->offset == 0
2950                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2951                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2952                   gcc_unreachable ();
2953
2954                 list = list->next;
2955               }
2956 #endif
2957           }
2958       }
2959
2960   if (val)
2961     cslot = set_slot_part (set, val, cslot, cdv, 0,
2962                            VAR_INIT_STATUS_INITIALIZED, NULL_RTX);
2963
2964   slot = clobber_slot_part (set, cval, slot, 0, NULL);
2965
2966   /* Variable may have been unshared.  */
2967   var = (variable)*slot;
2968   gcc_assert (var->n_var_parts && var->var_part[0].loc_chain->loc == cval
2969               && var->var_part[0].loc_chain->next == NULL);
2970
2971   if (VALUE_RECURSED_INTO (cval))
2972     goto restart_with_cval;
2973
2974   return 1;
2975 }
2976
2977 /* Combine variable or value in *S1SLOT (in DSM->cur) with the
2978    corresponding entry in DSM->src.  Multi-part variables are combined
2979    with variable_union, whereas onepart dvs are combined with
2980    intersection.  */
2981
2982 static int
2983 variable_merge_over_cur (void **s1slot, void *data)
2984 {
2985   struct dfset_merge *dsm = (struct dfset_merge *)data;
2986   dataflow_set *dst = dsm->dst;
2987   void **dstslot;
2988   variable s1var = (variable) *s1slot;
2989   variable s2var, dvar = NULL;
2990   decl_or_value dv = s1var->dv;
2991   bool onepart = dv_onepart_p (dv);
2992   rtx val;
2993   hashval_t dvhash;
2994   location_chain node, *nodep;
2995
2996   /* If the incoming onepart variable has an empty location list, then
2997      the intersection will be just as empty.  For other variables,
2998      it's always union.  */
2999   gcc_assert (s1var->n_var_parts);
3000   gcc_assert (s1var->var_part[0].loc_chain);
3001
3002   if (!onepart)
3003     return variable_union (s1slot, dst);
3004
3005   gcc_assert (s1var->n_var_parts == 1);
3006   gcc_assert (s1var->var_part[0].offset == 0);
3007
3008   dvhash = dv_htab_hash (dv);
3009   if (dv_is_value_p (dv))
3010     val = dv_as_value (dv);
3011   else
3012     val = NULL;
3013
3014   s2var = shared_hash_find_1 (dsm->src->vars, dv, dvhash);
3015   if (!s2var)
3016     {
3017       dst_can_be_shared = false;
3018       return 1;
3019     }
3020
3021   dsm->src_onepart_cnt--;
3022   gcc_assert (s2var->var_part[0].loc_chain);
3023   gcc_assert (s2var->n_var_parts == 1);
3024   gcc_assert (s2var->var_part[0].offset == 0);
3025
3026   dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3027   if (dstslot)
3028     {
3029       dvar = (variable)*dstslot;
3030       gcc_assert (dvar->refcount == 1);
3031       gcc_assert (dvar->n_var_parts == 1);
3032       gcc_assert (dvar->var_part[0].offset == 0);
3033       nodep = &dvar->var_part[0].loc_chain;
3034     }
3035   else
3036     {
3037       nodep = &node;
3038       node = NULL;
3039     }
3040
3041   if (!dstslot && !onepart_variable_different_p (s1var, s2var))
3042     {
3043       dstslot = shared_hash_find_slot_unshare_1 (&dst->vars, dv,
3044                                                  dvhash, INSERT);
3045       *dstslot = dvar = s2var;
3046       dvar->refcount++;
3047     }
3048   else
3049     {
3050       dst_can_be_shared = false;
3051
3052       intersect_loc_chains (val, nodep, dsm,
3053                             s1var->var_part[0].loc_chain, s2var);
3054
3055       if (!dstslot)
3056         {
3057           if (node)
3058             {
3059               dvar = (variable) pool_alloc (dv_pool (dv));
3060               dvar->dv = dv;
3061               dvar->refcount = 1;
3062               dvar->n_var_parts = 1;
3063               dvar->var_part[0].offset = 0;
3064               dvar->var_part[0].loc_chain = node;
3065               dvar->var_part[0].cur_loc = node->loc;
3066
3067               dstslot
3068                 = shared_hash_find_slot_unshare_1 (&dst->vars, dv, dvhash,
3069                                                    INSERT);
3070               gcc_assert (!*dstslot);
3071               *dstslot = dvar;
3072             }
3073           else
3074             return 1;
3075         }
3076     }
3077
3078   nodep = &dvar->var_part[0].loc_chain;
3079   while ((node = *nodep))
3080     {
3081       location_chain *nextp = &node->next;
3082
3083       if (GET_CODE (node->loc) == REG)
3084         {
3085           attrs list;
3086
3087           for (list = dst->regs[REGNO (node->loc)]; list; list = list->next)
3088             if (GET_MODE (node->loc) == GET_MODE (list->loc)
3089                 && dv_is_value_p (list->dv))
3090               break;
3091
3092           if (!list)
3093             attrs_list_insert (&dst->regs[REGNO (node->loc)],
3094                                dv, 0, node->loc);
3095           /* If this value became canonical for another value that had
3096              this register, we want to leave it alone.  */
3097           else if (dv_as_value (list->dv) != val)
3098             {
3099               dstslot = set_slot_part (dst, dv_as_value (list->dv),
3100                                        dstslot, dv, 0,
3101                                        node->init, NULL_RTX);
3102               dstslot = delete_slot_part (dst, node->loc, dstslot, 0);
3103
3104               /* Since nextp points into the removed node, we can't
3105                  use it.  The pointer to the next node moved to nodep.
3106                  However, if the variable we're walking is unshared
3107                  during our walk, we'll keep walking the location list
3108                  of the previously-shared variable, in which case the
3109                  node won't have been removed, and we'll want to skip
3110                  it.  That's why we test *nodep here.  */
3111               if (*nodep != node)
3112                 nextp = nodep;
3113             }
3114         }
3115       else
3116         /* Canonicalization puts registers first, so we don't have to
3117            walk it all.  */
3118         break;
3119       nodep = nextp;
3120     }
3121
3122   if (dvar != (variable)*dstslot)
3123     dvar = (variable)*dstslot;
3124   nodep = &dvar->var_part[0].loc_chain;
3125
3126   if (val)
3127     {
3128       /* Mark all referenced nodes for canonicalization, and make sure
3129          we have mutual equivalence links.  */
3130       VALUE_RECURSED_INTO (val) = true;
3131       for (node = *nodep; node; node = node->next)
3132         if (GET_CODE (node->loc) == VALUE)
3133           {
3134             VALUE_RECURSED_INTO (node->loc) = true;
3135             set_variable_part (dst, val, dv_from_value (node->loc), 0,
3136                                node->init, NULL, INSERT);
3137           }
3138
3139       dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3140       gcc_assert (*dstslot == dvar);
3141       canonicalize_values_star (dstslot, dst);
3142 #ifdef ENABLE_CHECKING
3143       gcc_assert (dstslot
3144                   == shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash));
3145 #endif
3146       dvar = (variable)*dstslot;
3147     }
3148   else
3149     {
3150       bool has_value = false, has_other = false;
3151
3152       /* If we have one value and anything else, we're going to
3153          canonicalize this, so make sure all values have an entry in
3154          the table and are marked for canonicalization.  */
3155       for (node = *nodep; node; node = node->next)
3156         {
3157           if (GET_CODE (node->loc) == VALUE)
3158             {
3159               /* If this was marked during register canonicalization,
3160                  we know we have to canonicalize values.  */
3161               if (has_value)
3162                 has_other = true;
3163               has_value = true;
3164               if (has_other)
3165                 break;
3166             }
3167           else
3168             {
3169               has_other = true;
3170               if (has_value)
3171                 break;
3172             }
3173         }
3174
3175       if (has_value && has_other)
3176         {
3177           for (node = *nodep; node; node = node->next)
3178             {
3179               if (GET_CODE (node->loc) == VALUE)
3180                 {
3181                   decl_or_value dv = dv_from_value (node->loc);
3182                   void **slot = NULL;
3183
3184                   if (shared_hash_shared (dst->vars))
3185                     slot = shared_hash_find_slot_noinsert (dst->vars, dv);
3186                   if (!slot)
3187                     slot = shared_hash_find_slot_unshare (&dst->vars, dv,
3188                                                           INSERT);
3189                   if (!*slot)
3190                     {
3191                       variable var = (variable) pool_alloc (dv_pool (dv));
3192                       var->dv = dv;
3193                       var->refcount = 1;
3194                       var->n_var_parts = 1;
3195                       var->var_part[0].offset = 0;
3196                       var->var_part[0].loc_chain = NULL;
3197                       var->var_part[0].cur_loc = NULL;
3198                       *slot = var;
3199                     }
3200
3201                   VALUE_RECURSED_INTO (node->loc) = true;
3202                 }
3203             }
3204
3205           dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3206           gcc_assert (*dstslot == dvar);
3207           canonicalize_values_star (dstslot, dst);
3208 #ifdef ENABLE_CHECKING
3209           gcc_assert (dstslot
3210                       == shared_hash_find_slot_noinsert_1 (dst->vars,
3211                                                            dv, dvhash));
3212 #endif
3213           dvar = (variable)*dstslot;
3214         }
3215     }
3216
3217   if (!onepart_variable_different_p (dvar, s2var))
3218     {
3219       variable_htab_free (dvar);
3220       *dstslot = dvar = s2var;
3221       dvar->refcount++;
3222     }
3223   else if (s2var != s1var && !onepart_variable_different_p (dvar, s1var))
3224     {
3225       variable_htab_free (dvar);
3226       *dstslot = dvar = s1var;
3227       dvar->refcount++;
3228       dst_can_be_shared = false;
3229     }
3230   else
3231     {
3232       if (dvar->refcount == 1)
3233         dvar->var_part[0].cur_loc = dvar->var_part[0].loc_chain->loc;
3234       dst_can_be_shared = false;
3235     }
3236
3237   return 1;
3238 }
3239
3240 /* Combine variable in *S1SLOT (in DSM->src) with the corresponding
3241    entry in DSM->src.  Only multi-part variables are combined, using
3242    variable_union.  onepart dvs were already combined with
3243    intersection in variable_merge_over_cur().  */
3244
3245 static int
3246 variable_merge_over_src (void **s2slot, void *data)
3247 {
3248   struct dfset_merge *dsm = (struct dfset_merge *)data;
3249   dataflow_set *dst = dsm->dst;
3250   variable s2var = (variable) *s2slot;
3251   decl_or_value dv = s2var->dv;
3252   bool onepart = dv_onepart_p (dv);
3253
3254   if (!onepart)
3255     {
3256       void **dstp = shared_hash_find_slot (dst->vars, dv);
3257       *dstp = s2var;
3258       s2var->refcount++;
3259       return variable_canonicalize (dstp, dst);
3260     }
3261
3262   dsm->src_onepart_cnt++;
3263   return 1;
3264 }
3265
3266 /* Combine dataflow set information from SRC into DST, using PDST
3267    to carry over information across passes.  */
3268
3269 static void
3270 dataflow_set_merge (dataflow_set *dst, dataflow_set *src)
3271 {
3272   dataflow_set src2 = *dst;
3273   struct dfset_merge dsm;
3274   int i;
3275   size_t src_elems, dst_elems;
3276
3277   src_elems = htab_elements (shared_hash_htab (src->vars));
3278   dst_elems = htab_elements (shared_hash_htab (src2.vars));
3279   dataflow_set_init (dst);
3280   dst->stack_adjust = src2.stack_adjust;
3281   shared_hash_destroy (dst->vars);
3282   dst->vars = (shared_hash) pool_alloc (shared_hash_pool);
3283   dst->vars->refcount = 1;
3284   dst->vars->htab
3285     = htab_create (MAX (src_elems, dst_elems), variable_htab_hash,
3286                    variable_htab_eq, variable_htab_free);
3287
3288   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3289     attrs_list_mpdv_union (&dst->regs[i], src->regs[i], src2.regs[i]);
3290
3291   dsm.dst = dst;
3292   dsm.src = &src2;
3293   dsm.cur = src;
3294   dsm.src_onepart_cnt = 0;
3295
3296   htab_traverse (shared_hash_htab (dsm.src->vars), variable_merge_over_src,
3297                  &dsm);
3298   htab_traverse (shared_hash_htab (dsm.cur->vars), variable_merge_over_cur,
3299                  &dsm);
3300
3301   if (dsm.src_onepart_cnt)
3302     dst_can_be_shared = false;
3303
3304   dataflow_set_destroy (&src2);
3305 }
3306
3307 /* Mark register equivalences.  */
3308
3309 static void
3310 dataflow_set_equiv_regs (dataflow_set *set)
3311 {
3312   int i;
3313   attrs list, *listp;
3314
3315   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3316     {
3317       rtx canon[NUM_MACHINE_MODES];
3318
3319       memset (canon, 0, sizeof (canon));
3320
3321       for (list = set->regs[i]; list; list = list->next)
3322         if (list->offset == 0 && dv_is_value_p (list->dv))
3323           {
3324             rtx val = dv_as_value (list->dv);
3325             rtx *cvalp = &canon[(int)GET_MODE (val)];
3326             rtx cval = *cvalp;
3327
3328             if (canon_value_cmp (val, cval))
3329               *cvalp = val;
3330           }
3331
3332       for (list = set->regs[i]; list; list = list->next)
3333         if (list->offset == 0 && dv_onepart_p (list->dv))
3334           {
3335             rtx cval = canon[(int)GET_MODE (list->loc)];
3336
3337             if (!cval)
3338               continue;
3339
3340             if (dv_is_value_p (list->dv))
3341               {
3342                 rtx val = dv_as_value (list->dv);
3343
3344                 if (val == cval)
3345                   continue;
3346
3347                 VALUE_RECURSED_INTO (val) = true;
3348                 set_variable_part (set, val, dv_from_value (cval), 0,
3349                                    VAR_INIT_STATUS_INITIALIZED,
3350                                    NULL, NO_INSERT);
3351               }
3352
3353             VALUE_RECURSED_INTO (cval) = true;
3354             set_variable_part (set, cval, list->dv, 0,
3355                                VAR_INIT_STATUS_INITIALIZED, NULL, NO_INSERT);
3356           }
3357
3358       for (listp = &set->regs[i]; (list = *listp);
3359            listp = list ? &list->next : listp)
3360         if (list->offset == 0 && dv_onepart_p (list->dv))
3361           {
3362             rtx cval = canon[(int)GET_MODE (list->loc)];
3363             void **slot;
3364
3365             if (!cval)
3366               continue;
3367
3368             if (dv_is_value_p (list->dv))
3369               {
3370                 rtx val = dv_as_value (list->dv);
3371                 if (!VALUE_RECURSED_INTO (val))
3372                   continue;
3373               }
3374
3375             slot = shared_hash_find_slot_noinsert (set->vars, list->dv);
3376             canonicalize_values_star (slot, set);
3377             if (*listp != list)
3378               list = NULL;
3379           }
3380     }
3381 }
3382
3383 /* Remove any redundant values in the location list of VAR, which must
3384    be unshared and 1-part.  */
3385
3386 static void
3387 remove_duplicate_values (variable var)
3388 {
3389   location_chain node, *nodep;
3390
3391   gcc_assert (dv_onepart_p (var->dv));
3392   gcc_assert (var->n_var_parts == 1);
3393   gcc_assert (var->refcount == 1);
3394
3395   for (nodep = &var->var_part[0].loc_chain; (node = *nodep); )
3396     {
3397       if (GET_CODE (node->loc) == VALUE)
3398         {
3399           if (VALUE_RECURSED_INTO (node->loc))
3400             {
3401               /* Remove duplicate value node.  */
3402               *nodep = node->next;
3403               pool_free (loc_chain_pool, node);
3404               continue;
3405             }
3406           else
3407             VALUE_RECURSED_INTO (node->loc) = true;
3408         }
3409       nodep = &node->next;
3410     }
3411
3412   for (node = var->var_part[0].loc_chain; node; node = node->next)
3413     if (GET_CODE (node->loc) == VALUE)
3414       {
3415         gcc_assert (VALUE_RECURSED_INTO (node->loc));
3416         VALUE_RECURSED_INTO (node->loc) = false;
3417       }
3418 }
3419
3420
3421 /* Hash table iteration argument passed to variable_post_merge.  */
3422 struct dfset_post_merge
3423 {
3424   /* The new input set for the current block.  */
3425   dataflow_set *set;
3426   /* Pointer to the permanent input set for the current block, or
3427      NULL.  */
3428   dataflow_set **permp;
3429 };
3430
3431 /* Create values for incoming expressions associated with one-part
3432    variables that don't have value numbers for them.  */
3433
3434 static int
3435 variable_post_merge_new_vals (void **slot, void *info)
3436 {
3437   struct dfset_post_merge *dfpm = (struct dfset_post_merge *)info;
3438   dataflow_set *set = dfpm->set;
3439   variable var = (variable)*slot;
3440   location_chain node;
3441
3442   if (!dv_onepart_p (var->dv) || !var->n_var_parts)
3443     return 1;
3444
3445   gcc_assert (var->n_var_parts == 1);
3446
3447   if (dv_is_decl_p (var->dv))
3448     {
3449       bool check_dupes = false;
3450
3451     restart:
3452       for (node = var->var_part[0].loc_chain; node; node = node->next)
3453         {
3454           if (GET_CODE (node->loc) == VALUE)
3455             gcc_assert (!VALUE_RECURSED_INTO (node->loc));
3456           else if (GET_CODE (node->loc) == REG)
3457             {
3458               attrs att, *attp, *curp = NULL;
3459
3460               if (var->refcount != 1)
3461                 {
3462                   slot = unshare_variable (set, slot, var,
3463                                            VAR_INIT_STATUS_INITIALIZED);
3464                   var = (variable)*slot;
3465                   goto restart;
3466                 }
3467
3468               for (attp = &set->regs[REGNO (node->loc)]; (att = *attp);
3469                    attp = &att->next)
3470                 if (att->offset == 0
3471                     && GET_MODE (att->loc) == GET_MODE (node->loc))
3472                   {
3473                     if (dv_is_value_p (att->dv))
3474                       {
3475                         rtx cval = dv_as_value (att->dv);
3476                         node->loc = cval;
3477                         check_dupes = true;
3478                         break;
3479                       }
3480                     else if (dv_as_opaque (att->dv) == dv_as_opaque (var->dv))
3481                       curp = attp;
3482                   }
3483
3484               if (!curp)
3485                 {
3486                   curp = attp;
3487                   while (*curp)
3488                     if ((*curp)->offset == 0
3489                         && GET_MODE ((*curp)->loc) == GET_MODE (node->loc)
3490                         && dv_as_opaque ((*curp)->dv) == dv_as_opaque (var->dv))
3491                       break;
3492                     else
3493                       curp = &(*curp)->next;
3494                   gcc_assert (*curp);
3495                 }
3496
3497               if (!att)
3498                 {
3499                   decl_or_value cdv;
3500                   rtx cval;
3501
3502                   if (!*dfpm->permp)
3503                     {
3504                       *dfpm->permp = XNEW (dataflow_set);
3505                       dataflow_set_init (*dfpm->permp);
3506                     }
3507
3508                   for (att = (*dfpm->permp)->regs[REGNO (node->loc)];
3509                        att; att = att->next)
3510                     if (GET_MODE (att->loc) == GET_MODE (node->loc))
3511                       {
3512                         gcc_assert (att->offset == 0);
3513                         gcc_assert (dv_is_value_p (att->dv));
3514                         val_reset (set, att->dv);
3515                         break;
3516                       }
3517
3518                   if (att)
3519                     {
3520                       cdv = att->dv;
3521                       cval = dv_as_value (cdv);
3522                     }
3523                   else
3524                     {
3525                       /* Create a unique value to hold this register,
3526                          that ought to be found and reused in
3527                          subsequent rounds.  */
3528                       cselib_val *v;
3529                       gcc_assert (!cselib_lookup (node->loc,
3530                                                   GET_MODE (node->loc), 0));
3531                       v = cselib_lookup (node->loc, GET_MODE (node->loc), 1);
3532                       cselib_preserve_value (v);
3533                       cselib_invalidate_rtx (node->loc);
3534                       cval = v->val_rtx;
3535                       cdv = dv_from_value (cval);
3536                       if (dump_file)
3537                         fprintf (dump_file,
3538                                  "Created new value %i for reg %i\n",
3539                                  v->value, REGNO (node->loc));
3540                     }
3541
3542                   var_reg_decl_set (*dfpm->permp, node->loc,
3543                                     VAR_INIT_STATUS_INITIALIZED,
3544                                     cdv, 0, NULL, INSERT);
3545
3546                   node->loc = cval;
3547                   check_dupes = true;
3548                 }
3549
3550               /* Remove attribute referring to the decl, which now
3551                  uses the value for the register, already existing or
3552                  to be added when we bring perm in.  */
3553               att = *curp;
3554               *curp = att->next;
3555               pool_free (attrs_pool, att);
3556             }
3557         }
3558
3559       if (check_dupes)
3560         remove_duplicate_values (var);
3561     }
3562
3563   return 1;
3564 }
3565
3566 /* Reset values in the permanent set that are not associated with the
3567    chosen expression.  */
3568
3569 static int
3570 variable_post_merge_perm_vals (void **pslot, void *info)
3571 {
3572   struct dfset_post_merge *dfpm = (struct dfset_post_merge *)info;
3573   dataflow_set *set = dfpm->set;
3574   variable pvar = (variable)*pslot, var;
3575   location_chain pnode;
3576   decl_or_value dv;
3577   attrs att;
3578
3579   gcc_assert (dv_is_value_p (pvar->dv));
3580   gcc_assert (pvar->n_var_parts == 1);
3581   pnode = pvar->var_part[0].loc_chain;
3582   gcc_assert (pnode);
3583   gcc_assert (!pnode->next);
3584   gcc_assert (REG_P (pnode->loc));
3585
3586   dv = pvar->dv;
3587
3588   var = shared_hash_find (set->vars, dv);
3589   if (var)
3590     {
3591       if (find_loc_in_1pdv (pnode->loc, var, shared_hash_htab (set->vars)))
3592         return 1;
3593       val_reset (set, dv);
3594     }
3595
3596   for (att = set->regs[REGNO (pnode->loc)]; att; att = att->next)
3597     if (att->offset == 0
3598         && GET_MODE (att->loc) == GET_MODE (pnode->loc)
3599         && dv_is_value_p (att->dv))
3600       break;
3601
3602   /* If there is a value associated with this register already, create
3603      an equivalence.  */
3604   if (att && dv_as_value (att->dv) != dv_as_value (dv))
3605     {
3606       rtx cval = dv_as_value (att->dv);
3607       set_variable_part (set, cval, dv, 0, pnode->init, NULL, INSERT);
3608       set_variable_part (set, dv_as_value (dv), att->dv, 0, pnode->init,
3609                          NULL, INSERT);
3610     }
3611   else if (!att)
3612     {
3613       attrs_list_insert (&set->regs[REGNO (pnode->loc)],
3614                          dv, 0, pnode->loc);
3615       variable_union (pslot, set);
3616     }
3617
3618   return 1;
3619 }
3620
3621 /* Just checking stuff and registering register attributes for
3622    now.  */
3623
3624 static void
3625 dataflow_post_merge_adjust (dataflow_set *set, dataflow_set **permp)
3626 {
3627   struct dfset_post_merge dfpm;
3628
3629   dfpm.set = set;
3630   dfpm.permp = permp;
3631
3632   htab_traverse (shared_hash_htab (set->vars), variable_post_merge_new_vals,
3633                  &dfpm);
3634   if (*permp)
3635     htab_traverse (shared_hash_htab ((*permp)->vars),
3636                    variable_post_merge_perm_vals, &dfpm);
3637   htab_traverse (shared_hash_htab (set->vars), canonicalize_values_star, set);
3638 }
3639
3640 /* Return a node whose loc is a MEM that refers to EXPR in the
3641    location list of a one-part variable or value VAR, or in that of
3642    any values recursively mentioned in the location lists.  */
3643
3644 static location_chain
3645 find_mem_expr_in_1pdv (tree expr, rtx val, htab_t vars)
3646 {
3647   location_chain node;
3648   decl_or_value dv;
3649   variable var;
3650   location_chain where = NULL;
3651
3652   if (!val)
3653     return NULL;
3654
3655   gcc_assert (GET_CODE (val) == VALUE);
3656
3657   gcc_assert (!VALUE_RECURSED_INTO (val));
3658
3659   dv = dv_from_value (val);
3660   var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
3661
3662   if (!var)
3663     return NULL;
3664
3665   gcc_assert (dv_onepart_p (var->dv));
3666
3667   if (!var->n_var_parts)
3668     return NULL;
3669
3670   gcc_assert (var->var_part[0].offset == 0);
3671
3672   VALUE_RECURSED_INTO (val) = true;
3673
3674   for (node = var->var_part[0].loc_chain; node; node = node->next)
3675     if (MEM_P (node->loc) && MEM_EXPR (node->loc) == expr
3676         && MEM_OFFSET (node->loc) == 0)
3677       {
3678         where = node;
3679         break;
3680       }
3681     else if (GET_CODE (node->loc) == VALUE
3682              && !VALUE_RECURSED_INTO (node->loc)
3683              && (where = find_mem_expr_in_1pdv (expr, node->loc, vars)))
3684       break;
3685
3686   VALUE_RECURSED_INTO (val) = false;
3687
3688   return where;
3689 }
3690
3691 /* Remove all MEMs from the location list of a hash table entry for a
3692    one-part variable, except those whose MEM attributes map back to
3693    the variable itself, directly or within a VALUE.
3694
3695    ??? We could also preserve MEMs that reference stack slots that are
3696    annotated as not addressable.  This is arguably even more reliable
3697    than the current heuristic.  */
3698
3699 static int
3700 dataflow_set_preserve_mem_locs (void **slot, void *data)
3701 {
3702   dataflow_set *set = (dataflow_set *) data;
3703   variable var = (variable) *slot;
3704
3705   if (dv_is_decl_p (var->dv) && dv_onepart_p (var->dv))
3706     {
3707       tree decl = dv_as_decl (var->dv);
3708       location_chain loc, *locp;
3709
3710       if (!var->n_var_parts)
3711         return 1;
3712
3713       gcc_assert (var->n_var_parts == 1);
3714
3715       if (var->refcount > 1 || shared_hash_shared (set->vars))
3716         {
3717           for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
3718             {
3719               /* We want to remove a MEM that doesn't refer to DECL.  */
3720               if (GET_CODE (loc->loc) == MEM
3721                   && (MEM_EXPR (loc->loc) != decl
3722                       || MEM_OFFSET (loc->loc)))
3723                 break;
3724               /* We want to move here a MEM that does refer to DECL.  */
3725               else if (GET_CODE (loc->loc) == VALUE
3726                        && find_mem_expr_in_1pdv (decl, loc->loc,
3727                                                  shared_hash_htab (set->vars)))
3728               break;
3729             }
3730
3731           if (!loc)
3732             return 1;
3733
3734           slot = unshare_variable (set, slot, var, VAR_INIT_STATUS_UNKNOWN);
3735           var = (variable)*slot;
3736           gcc_assert (var->n_var_parts == 1);
3737         }
3738
3739       for (locp = &var->var_part[0].loc_chain, loc = *locp;
3740            loc; loc = *locp)
3741         {
3742           rtx old_loc = loc->loc;
3743           if (GET_CODE (old_loc) == VALUE)
3744             {
3745               location_chain mem_node
3746                 = find_mem_expr_in_1pdv (decl, loc->loc,
3747                                          shared_hash_htab (set->vars));
3748
3749               /* ??? This picks up only one out of multiple MEMs that
3750                  refer to the same variable.  Do we ever need to be
3751                  concerned about dealing with more than one, or, given
3752                  that they should all map to the same variable
3753                  location, their addresses will have been merged and
3754                  they will be regarded as equivalent?  */
3755               if (mem_node)
3756                 {
3757                   loc->loc = mem_node->loc;
3758                   loc->set_src = mem_node->set_src;
3759                   loc->init = MIN (loc->init, mem_node->init);
3760                 }
3761             }
3762
3763           if (GET_CODE (loc->loc) != MEM
3764               || (MEM_EXPR (loc->loc) == decl
3765                   && MEM_OFFSET (loc->loc) == 0))
3766             {
3767               if (old_loc != loc->loc && emit_notes)
3768                 {
3769                   add_value_chains (var->dv, loc->loc);
3770                   remove_value_chains (var->dv, old_loc);
3771                 }
3772               locp = &loc->next;
3773               continue;
3774             }
3775
3776           if (emit_notes)
3777             remove_value_chains (var->dv, old_loc);
3778           *locp = loc->next;
3779           pool_free (loc_chain_pool, loc);
3780         }
3781
3782       if (!var->var_part[0].loc_chain)
3783         {
3784           var->n_var_parts--;
3785           if (emit_notes && dv_is_value_p (var->dv))
3786             remove_cselib_value_chains (var->dv);
3787           variable_was_changed (var, set);
3788         }
3789     }
3790
3791   return 1;
3792 }
3793
3794 /* Remove all MEMs from the location list of a hash table entry for a
3795    value.  */
3796
3797 static int
3798 dataflow_set_remove_mem_locs (void **slot, void *data)
3799 {
3800   dataflow_set *set = (dataflow_set *) data;
3801   variable var = (variable) *slot;
3802
3803   if (dv_is_value_p (var->dv))
3804     {
3805       location_chain loc, *locp;
3806       bool changed = false;
3807
3808       gcc_assert (var->n_var_parts == 1);
3809
3810       if (var->refcount > 1 || shared_hash_shared (set->vars))
3811         {
3812           for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
3813             if (GET_CODE (loc->loc) == MEM)
3814               break;
3815
3816           if (!loc)
3817             return 1;
3818
3819           slot = unshare_variable (set, slot, var, VAR_INIT_STATUS_UNKNOWN);
3820           var = (variable)*slot;
3821           gcc_assert (var->n_var_parts == 1);
3822         }
3823
3824       for (locp = &var->var_part[0].loc_chain, loc = *locp;
3825            loc; loc = *locp)
3826         {
3827           if (GET_CODE (loc->loc) != MEM)
3828             {
3829               locp = &loc->next;
3830               continue;
3831             }
3832
3833           if (emit_notes)
3834             remove_value_chains (var->dv, loc->loc);
3835           *locp = loc->next;
3836           /* If we have deleted the location which was last emitted
3837              we have to emit new location so add the variable to set
3838              of changed variables.  */
3839           if (var->var_part[0].cur_loc
3840               && rtx_equal_p (loc->loc, var->var_part[0].cur_loc))
3841             changed = true;
3842           pool_free (loc_chain_pool, loc);
3843         }
3844
3845       if (!var->var_part[0].loc_chain)
3846         {
3847           var->n_var_parts--;
3848           if (emit_notes && dv_is_value_p (var->dv))
3849             remove_cselib_value_chains (var->dv);
3850           gcc_assert (changed);
3851         }
3852       if (changed)
3853         {
3854           if (var->n_var_parts && var->var_part[0].loc_chain)
3855             var->var_part[0].cur_loc = var->var_part[0].loc_chain->loc;
3856           variable_was_changed (var, set);
3857         }
3858     }
3859
3860   return 1;
3861 }
3862
3863 /* Remove all variable-location information about call-clobbered
3864    registers, as well as associations between MEMs and VALUEs.  */
3865
3866 static void
3867 dataflow_set_clear_at_call (dataflow_set *set)
3868 {
3869   int r;
3870
3871   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
3872     if (TEST_HARD_REG_BIT (call_used_reg_set, r))
3873       var_regno_delete (set, r);
3874
3875   if (MAY_HAVE_DEBUG_INSNS)
3876     {
3877       set->traversed_vars = set->vars;
3878       htab_traverse (shared_hash_htab (set->vars),
3879                      dataflow_set_preserve_mem_locs, set);
3880       set->traversed_vars = set->vars;
3881       htab_traverse (shared_hash_htab (set->vars), dataflow_set_remove_mem_locs,
3882                      set);
3883       set->traversed_vars = NULL;
3884     }
3885 }
3886
3887 /* Flag whether two dataflow sets being compared contain different data.  */
3888 static bool
3889 dataflow_set_different_value;
3890
3891 static bool
3892 variable_part_different_p (variable_part *vp1, variable_part *vp2)
3893 {
3894   location_chain lc1, lc2;
3895
3896   for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
3897     {
3898       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
3899         {
3900           if (REG_P (lc1->loc) && REG_P (lc2->loc))
3901             {
3902               if (REGNO (lc1->loc) == REGNO (lc2->loc))
3903                 break;
3904             }
3905           if (rtx_equal_p (lc1->loc, lc2->loc))
3906             break;
3907         }
3908       if (!lc2)
3909         return true;
3910     }
3911   return false;
3912 }
3913
3914 /* Return true if one-part variables VAR1 and VAR2 are different.
3915    They must be in canonical order.  */
3916
3917 static bool
3918 onepart_variable_different_p (variable var1, variable var2)
3919 {
3920   location_chain lc1, lc2;
3921
3922   if (var1 == var2)
3923     return false;
3924
3925   gcc_assert (var1->n_var_parts == 1);
3926   gcc_assert (var2->n_var_parts == 1);
3927
3928   lc1 = var1->var_part[0].loc_chain;
3929   lc2 = var2->var_part[0].loc_chain;
3930
3931   gcc_assert (lc1);
3932   gcc_assert (lc2);
3933
3934   while (lc1 && lc2)
3935     {
3936       if (loc_cmp (lc1->loc, lc2->loc))
3937         return true;
3938       lc1 = lc1->next;
3939       lc2 = lc2->next;
3940     }
3941
3942   return lc1 != lc2;
3943 }
3944
3945 /* Return true if variables VAR1 and VAR2 are different.
3946    If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
3947    variable part.  */
3948
3949 static bool
3950 variable_different_p (variable var1, variable var2,
3951                       bool compare_current_location)
3952 {
3953   int i;
3954
3955   if (var1 == var2)
3956     return false;
3957
3958   if (var1->n_var_parts != var2->n_var_parts)
3959     return true;
3960
3961   for (i = 0; i < var1->n_var_parts; i++)
3962     {
3963       if (var1->var_part[i].offset != var2->var_part[i].offset)
3964         return true;
3965       if (compare_current_location)
3966         {
3967           if (!((REG_P (var1->var_part[i].cur_loc)
3968                  && REG_P (var2->var_part[i].cur_loc)
3969                  && (REGNO (var1->var_part[i].cur_loc)
3970                      == REGNO (var2->var_part[i].cur_loc)))
3971                 || rtx_equal_p (var1->var_part[i].cur_loc,
3972                                 var2->var_part[i].cur_loc)))
3973             return true;
3974         }
3975       /* One-part values have locations in a canonical order.  */
3976       if (i == 0 && var1->var_part[i].offset == 0 && dv_onepart_p (var1->dv))
3977         {
3978           gcc_assert (var1->n_var_parts == 1);
3979           gcc_assert (dv_as_opaque (var1->dv) == dv_as_opaque (var2->dv));
3980           return onepart_variable_different_p (var1, var2);
3981         }
3982       if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
3983         return true;
3984       if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
3985         return true;
3986     }
3987   return false;
3988 }
3989
3990 /* Compare variable *SLOT with the same variable in hash table DATA
3991    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
3992
3993 static int
3994 dataflow_set_different_1 (void **slot, void *data)
3995 {
3996   htab_t htab = (htab_t) data;
3997   variable var1, var2;
3998
3999   var1 = (variable) *slot;
4000   var2 = (variable) htab_find_with_hash (htab, var1->dv,
4001                                          dv_htab_hash (var1->dv));
4002   if (!var2)
4003     {
4004       dataflow_set_different_value = true;
4005
4006       if (dump_file && (dump_flags & TDF_DETAILS))
4007         {
4008           fprintf (dump_file, "dataflow difference found: removal of:\n");
4009           dump_variable (var1);
4010         }
4011
4012       /* Stop traversing the hash table.  */
4013       return 0;
4014     }
4015
4016   if (variable_different_p (var1, var2, false))
4017     {
4018       dataflow_set_different_value = true;
4019
4020       if (dump_file && (dump_flags & TDF_DETAILS))
4021         {
4022           fprintf (dump_file, "dataflow difference found: old and new follow:\n");
4023           dump_variable (var1);
4024           dump_variable (var2);
4025         }
4026
4027       /* Stop traversing the hash table.  */
4028       return 0;
4029     }
4030
4031   /* Continue traversing the hash table.  */
4032   return 1;
4033 }
4034
4035 /* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
4036
4037 static bool
4038 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
4039 {
4040   if (old_set->vars == new_set->vars)
4041     return false;
4042
4043   if (htab_elements (shared_hash_htab (old_set->vars))
4044       != htab_elements (shared_hash_htab (new_set->vars)))
4045     return true;
4046
4047   dataflow_set_different_value = false;
4048
4049   htab_traverse (shared_hash_htab (old_set->vars), dataflow_set_different_1,
4050                  shared_hash_htab (new_set->vars));
4051   /* No need to traverse the second hashtab, if both have the same number
4052      of elements and the second one had all entries found in the first one,
4053      then it can't have any extra entries.  */
4054   return dataflow_set_different_value;
4055 }
4056
4057 /* Free the contents of dataflow set SET.  */
4058
4059 static void
4060 dataflow_set_destroy (dataflow_set *set)
4061 {
4062   int i;
4063
4064   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4065     attrs_list_clear (&set->regs[i]);
4066
4067   shared_hash_destroy (set->vars);
4068   set->vars = NULL;
4069 }
4070
4071 /* Return true if RTL X contains a SYMBOL_REF.  */
4072
4073 static bool
4074 contains_symbol_ref (rtx x)
4075 {
4076   const char *fmt;
4077   RTX_CODE code;
4078   int i;
4079
4080   if (!x)
4081     return false;
4082
4083   code = GET_CODE (x);
4084   if (code == SYMBOL_REF)
4085     return true;
4086
4087   fmt = GET_RTX_FORMAT (code);
4088   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4089     {
4090       if (fmt[i] == 'e')
4091         {
4092           if (contains_symbol_ref (XEXP (x, i)))
4093             return true;
4094         }
4095       else if (fmt[i] == 'E')
4096         {
4097           int j;
4098           for (j = 0; j < XVECLEN (x, i); j++)
4099             if (contains_symbol_ref (XVECEXP (x, i, j)))
4100               return true;
4101         }
4102     }
4103
4104   return false;
4105 }
4106
4107 /* Shall EXPR be tracked?  */
4108
4109 static bool
4110 track_expr_p (tree expr, bool need_rtl)
4111 {
4112   rtx decl_rtl;
4113   tree realdecl;
4114
4115   /* If EXPR is not a parameter or a variable do not track it.  */
4116   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
4117     return 0;
4118
4119   /* It also must have a name...  */
4120   if (!DECL_NAME (expr))
4121     return 0;
4122
4123   /* ... and a RTL assigned to it.  */
4124   decl_rtl = DECL_RTL_IF_SET (expr);
4125   if (!decl_rtl && need_rtl)
4126     return 0;
4127   
4128   /* If this expression is really a debug alias of some other declaration, we 
4129      don't need to track this expression if the ultimate declaration is
4130      ignored.  */
4131   realdecl = expr;
4132   if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
4133     {
4134       realdecl = DECL_DEBUG_EXPR (realdecl);
4135       /* ??? We don't yet know how to emit DW_OP_piece for variable
4136          that has been SRA'ed.  */
4137       if (!DECL_P (realdecl))
4138         return 0;
4139     }
4140
4141   /* Do not track EXPR if REALDECL it should be ignored for debugging
4142      purposes.  */ 
4143   if (DECL_IGNORED_P (realdecl))
4144     return 0;
4145
4146   /* Do not track global variables until we are able to emit correct location
4147      list for them.  */
4148   if (TREE_STATIC (realdecl))
4149     return 0;
4150
4151   /* When the EXPR is a DECL for alias of some variable (see example)
4152      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
4153      DECL_RTL contains SYMBOL_REF.
4154
4155      Example:
4156      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
4157      char **_dl_argv;
4158   */
4159   if (decl_rtl&nb