OSDN Git Service

gcc/ChangeLog:
[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)DEBUG_EXPR_DECL:
736     case (int)COMPONENT_REF:
737       return true;
738
739     case (int)VALUE:
740       return false;
741
742     default:
743       gcc_unreachable ();
744     }
745 }
746
747 /* Return true if a decl_or_value is a VALUE rtl.  */
748 static inline bool
749 dv_is_value_p (decl_or_value dv)
750 {
751   return dv && !dv_is_decl_p (dv);
752 }
753
754 /* Return the decl in the decl_or_value.  */
755 static inline tree
756 dv_as_decl (decl_or_value dv)
757 {
758   gcc_assert (dv_is_decl_p (dv));
759   return (tree) dv;
760 }
761
762 /* Return the value in the decl_or_value.  */
763 static inline rtx
764 dv_as_value (decl_or_value dv)
765 {
766   gcc_assert (dv_is_value_p (dv));
767   return (rtx)dv;
768 }
769
770 /* Return the opaque pointer in the decl_or_value.  */
771 static inline void *
772 dv_as_opaque (decl_or_value dv)
773 {
774   return dv;
775 }
776
777 /* Return true if a decl_or_value must not have more than one variable
778    part.  */
779 static inline bool
780 dv_onepart_p (decl_or_value dv)
781 {
782   tree decl;
783
784   if (!MAY_HAVE_DEBUG_INSNS)
785     return false;
786
787   if (dv_is_value_p (dv))
788     return true;
789
790   decl = dv_as_decl (dv);
791
792   if (!decl)
793     return true;
794
795   return (target_for_debug_bind (decl) != NULL_TREE);
796 }
797
798 /* Return the variable pool to be used for dv, depending on whether it
799    can have multiple parts or not.  */
800 static inline alloc_pool
801 dv_pool (decl_or_value dv)
802 {
803   return dv_onepart_p (dv) ? valvar_pool : var_pool;
804 }
805
806 /* Build a decl_or_value out of a decl.  */
807 static inline decl_or_value
808 dv_from_decl (tree decl)
809 {
810   decl_or_value dv;
811   dv = decl;
812   gcc_assert (dv_is_decl_p (dv));
813   return dv;
814 }
815
816 /* Build a decl_or_value out of a value.  */
817 static inline decl_or_value
818 dv_from_value (rtx value)
819 {
820   decl_or_value dv;
821   dv = value;
822   gcc_assert (dv_is_value_p (dv));
823   return dv;
824 }
825
826 static inline hashval_t
827 dv_htab_hash (decl_or_value dv)
828 {
829   if (dv_is_value_p (dv))
830     return -(hashval_t)(CSELIB_VAL_PTR (dv_as_value (dv))->value);
831   else
832     return (VARIABLE_HASH_VAL (dv_as_decl (dv)));
833 }
834
835 /* The hash function for variable_htab, computes the hash value
836    from the declaration of variable X.  */
837
838 static hashval_t
839 variable_htab_hash (const void *x)
840 {
841   const_variable const v = (const_variable) x;
842
843   return dv_htab_hash (v->dv);
844 }
845
846 /* Compare the declaration of variable X with declaration Y.  */
847
848 static int
849 variable_htab_eq (const void *x, const void *y)
850 {
851   const_variable const v = (const_variable) x;
852   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
853
854   if (dv_as_opaque (v->dv) == dv_as_opaque (dv))
855     return true;
856
857 #if ENABLE_CHECKING
858   {
859     bool visv, dvisv;
860
861     visv = dv_is_value_p (v->dv);
862     dvisv = dv_is_value_p (dv);
863
864     if (visv != dvisv)
865       return false;
866
867     if (visv)
868       gcc_assert (CSELIB_VAL_PTR (dv_as_value (v->dv))
869                   != CSELIB_VAL_PTR (dv_as_value (dv)));
870     else
871       gcc_assert (VARIABLE_HASH_VAL (dv_as_decl (v->dv))
872                   != VARIABLE_HASH_VAL (dv_as_decl (dv)));
873   }
874 #endif
875
876   return false;
877 }
878
879 /* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
880
881 static void
882 variable_htab_free (void *elem)
883 {
884   int i;
885   variable var = (variable) elem;
886   location_chain node, next;
887
888   gcc_assert (var->refcount > 0);
889
890   var->refcount--;
891   if (var->refcount > 0)
892     return;
893
894   for (i = 0; i < var->n_var_parts; i++)
895     {
896       for (node = var->var_part[i].loc_chain; node; node = next)
897         {
898           next = node->next;
899           pool_free (loc_chain_pool, node);
900         }
901       var->var_part[i].loc_chain = NULL;
902     }
903   pool_free (dv_pool (var->dv), var);
904 }
905
906 /* The hash function for value_chains htab, computes the hash value
907    from the VALUE.  */
908
909 static hashval_t
910 value_chain_htab_hash (const void *x)
911 {
912   const_value_chain const v = (const_value_chain) x;
913
914   return dv_htab_hash (v->dv);
915 }
916
917 /* Compare the VALUE X with VALUE Y.  */
918
919 static int
920 value_chain_htab_eq (const void *x, const void *y)
921 {
922   const_value_chain const v = (const_value_chain) x;
923   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
924
925   return dv_as_opaque (v->dv) == dv_as_opaque (dv);
926 }
927
928 /* Initialize the set (array) SET of attrs to empty lists.  */
929
930 static void
931 init_attrs_list_set (attrs *set)
932 {
933   int i;
934
935   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
936     set[i] = NULL;
937 }
938
939 /* Make the list *LISTP empty.  */
940
941 static void
942 attrs_list_clear (attrs *listp)
943 {
944   attrs list, next;
945
946   for (list = *listp; list; list = next)
947     {
948       next = list->next;
949       pool_free (attrs_pool, list);
950     }
951   *listp = NULL;
952 }
953
954 /* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
955
956 static attrs
957 attrs_list_member (attrs list, decl_or_value dv, HOST_WIDE_INT offset)
958 {
959   for (; list; list = list->next)
960     if (dv_as_opaque (list->dv) == dv_as_opaque (dv) && list->offset == offset)
961       return list;
962   return NULL;
963 }
964
965 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
966
967 static void
968 attrs_list_insert (attrs *listp, decl_or_value dv,
969                    HOST_WIDE_INT offset, rtx loc)
970 {
971   attrs list;
972
973   list = (attrs) pool_alloc (attrs_pool);
974   list->loc = loc;
975   list->dv = dv;
976   list->offset = offset;
977   list->next = *listp;
978   *listp = list;
979 }
980
981 /* Copy all nodes from SRC and create a list *DSTP of the copies.  */
982
983 static void
984 attrs_list_copy (attrs *dstp, attrs src)
985 {
986   attrs n;
987
988   attrs_list_clear (dstp);
989   for (; src; src = src->next)
990     {
991       n = (attrs) pool_alloc (attrs_pool);
992       n->loc = src->loc;
993       n->dv = src->dv;
994       n->offset = src->offset;
995       n->next = *dstp;
996       *dstp = n;
997     }
998 }
999
1000 /* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
1001
1002 static void
1003 attrs_list_union (attrs *dstp, attrs src)
1004 {
1005   for (; src; src = src->next)
1006     {
1007       if (!attrs_list_member (*dstp, src->dv, src->offset))
1008         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1009     }
1010 }
1011
1012 /* Combine nodes that are not onepart nodes from SRC and SRC2 into
1013    *DSTP.  */
1014
1015 static void
1016 attrs_list_mpdv_union (attrs *dstp, attrs src, attrs src2)
1017 {
1018   gcc_assert (!*dstp);
1019   for (; src; src = src->next)
1020     {
1021       if (!dv_onepart_p (src->dv))
1022         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1023     }
1024   for (src = src2; src; src = src->next)
1025     {
1026       if (!dv_onepart_p (src->dv)
1027           && !attrs_list_member (*dstp, src->dv, src->offset))
1028         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1029     }
1030 }
1031
1032 /* Shared hashtable support.  */
1033
1034 /* Return true if VARS is shared.  */
1035
1036 static inline bool
1037 shared_hash_shared (shared_hash vars)
1038 {
1039   return vars->refcount > 1;
1040 }
1041
1042 /* Return the hash table for VARS.  */
1043
1044 static inline htab_t
1045 shared_hash_htab (shared_hash vars)
1046 {
1047   return vars->htab;
1048 }
1049
1050 /* Copy variables into a new hash table.  */
1051
1052 static shared_hash
1053 shared_hash_unshare (shared_hash vars)
1054 {
1055   shared_hash new_vars = (shared_hash) pool_alloc (shared_hash_pool);
1056   gcc_assert (vars->refcount > 1);
1057   new_vars->refcount = 1;
1058   new_vars->htab
1059     = htab_create (htab_elements (vars->htab) + 3, variable_htab_hash,
1060                    variable_htab_eq, variable_htab_free);
1061   vars_copy (new_vars->htab, vars->htab);
1062   vars->refcount--;
1063   return new_vars;
1064 }
1065
1066 /* Increment reference counter on VARS and return it.  */
1067
1068 static inline shared_hash
1069 shared_hash_copy (shared_hash vars)
1070 {
1071   vars->refcount++;
1072   return vars;
1073 }
1074
1075 /* Decrement reference counter and destroy hash table if not shared
1076    anymore.  */
1077
1078 static void
1079 shared_hash_destroy (shared_hash vars)
1080 {
1081   gcc_assert (vars->refcount > 0);
1082   if (--vars->refcount == 0)
1083     {
1084       htab_delete (vars->htab);
1085       pool_free (shared_hash_pool, vars);
1086     }
1087 }
1088
1089 /* Unshare *PVARS if shared and return slot for DV.  If INS is
1090    INSERT, insert it if not already present.  */
1091
1092 static inline void **
1093 shared_hash_find_slot_unshare_1 (shared_hash *pvars, decl_or_value dv,
1094                                  hashval_t dvhash, enum insert_option ins)
1095 {
1096   if (shared_hash_shared (*pvars))
1097     *pvars = shared_hash_unshare (*pvars);
1098   return htab_find_slot_with_hash (shared_hash_htab (*pvars), dv, dvhash, ins);
1099 }
1100
1101 static inline void **
1102 shared_hash_find_slot_unshare (shared_hash *pvars, decl_or_value dv,
1103                                enum insert_option ins)
1104 {
1105   return shared_hash_find_slot_unshare_1 (pvars, dv, dv_htab_hash (dv), ins);
1106 }
1107
1108 /* Return slot for DV, if it is already present in the hash table.
1109    If it is not present, insert it only VARS is not shared, otherwise
1110    return NULL.  */
1111
1112 static inline void **
1113 shared_hash_find_slot_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1114 {
1115   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1116                                    shared_hash_shared (vars)
1117                                    ? NO_INSERT : INSERT);
1118 }
1119
1120 static inline void **
1121 shared_hash_find_slot (shared_hash vars, decl_or_value dv)
1122 {
1123   return shared_hash_find_slot_1 (vars, dv, dv_htab_hash (dv));
1124 }
1125
1126 /* Return slot for DV only if it is already present in the hash table.  */
1127
1128 static inline void **
1129 shared_hash_find_slot_noinsert_1 (shared_hash vars, decl_or_value dv,
1130                                   hashval_t dvhash)
1131 {
1132   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1133                                    NO_INSERT);
1134 }
1135
1136 static inline void **
1137 shared_hash_find_slot_noinsert (shared_hash vars, decl_or_value dv)
1138 {
1139   return shared_hash_find_slot_noinsert_1 (vars, dv, dv_htab_hash (dv));
1140 }
1141
1142 /* Return variable for DV or NULL if not already present in the hash
1143    table.  */
1144
1145 static inline variable
1146 shared_hash_find_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1147 {
1148   return (variable) htab_find_with_hash (shared_hash_htab (vars), dv, dvhash);
1149 }
1150
1151 static inline variable
1152 shared_hash_find (shared_hash vars, decl_or_value dv)
1153 {
1154   return shared_hash_find_1 (vars, dv, dv_htab_hash (dv));
1155 }
1156
1157 /* Determine a total order between two distinct pointers.  Compare the
1158    pointers as integral types if size_t is wide enough, otherwise
1159    resort to bitwise memory compare.  The actual order does not
1160    matter, we just need to be consistent, so endianness is
1161    irrelevant.  */
1162
1163 static int
1164 tie_break_pointers (const void *p1, const void *p2)
1165 {
1166   gcc_assert (p1 != p2);
1167
1168   if (sizeof (size_t) >= sizeof (void*))
1169     return (size_t)p1 < (size_t)p2 ? -1 : 1;
1170   else
1171     return memcmp (&p1, &p2, sizeof (p1));
1172 }
1173
1174 /* Return true if TVAL is better than CVAL as a canonival value.  We
1175    choose lowest-numbered VALUEs, using the RTX address as a
1176    tie-breaker.  The idea is to arrange them into a star topology,
1177    such that all of them are at most one step away from the canonical
1178    value, and the canonical value has backlinks to all of them, in
1179    addition to all the actual locations.  We don't enforce this
1180    topology throughout the entire dataflow analysis, though.
1181  */
1182
1183 static inline bool
1184 canon_value_cmp (rtx tval, rtx cval)
1185 {
1186   return !cval
1187     || CSELIB_VAL_PTR (tval)->value < CSELIB_VAL_PTR (cval)->value
1188     || (CSELIB_VAL_PTR (tval)->value == CSELIB_VAL_PTR (cval)->value
1189         && tie_break_pointers (tval, cval) < 0);
1190 }
1191
1192 static bool dst_can_be_shared;
1193
1194 /* Return a copy of a variable VAR and insert it to dataflow set SET.  */
1195
1196 static void **
1197 unshare_variable (dataflow_set *set, void **slot, variable var,
1198                   enum var_init_status initialized)
1199 {
1200   variable new_var;
1201   int i;
1202
1203   new_var = (variable) pool_alloc (dv_pool (var->dv));
1204   new_var->dv = var->dv;
1205   new_var->refcount = 1;
1206   var->refcount--;
1207   new_var->n_var_parts = var->n_var_parts;
1208
1209   if (! flag_var_tracking_uninit)
1210     initialized = VAR_INIT_STATUS_INITIALIZED;
1211
1212   for (i = 0; i < var->n_var_parts; i++)
1213     {
1214       location_chain node;
1215       location_chain *nextp;
1216
1217       new_var->var_part[i].offset = var->var_part[i].offset;
1218       nextp = &new_var->var_part[i].loc_chain;
1219       for (node = var->var_part[i].loc_chain; node; node = node->next)
1220         {
1221           location_chain new_lc;
1222
1223           new_lc = (location_chain) pool_alloc (loc_chain_pool);
1224           new_lc->next = NULL;
1225           if (node->init > initialized)
1226             new_lc->init = node->init;
1227           else
1228             new_lc->init = initialized;
1229           if (node->set_src && !(MEM_P (node->set_src)))
1230             new_lc->set_src = node->set_src;
1231           else
1232             new_lc->set_src = NULL;
1233           new_lc->loc = node->loc;
1234
1235           *nextp = new_lc;
1236           nextp = &new_lc->next;
1237         }
1238
1239       /* We are at the basic block boundary when copying variable description
1240          so set the CUR_LOC to be the first element of the chain.  */
1241       if (new_var->var_part[i].loc_chain)
1242         new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
1243       else
1244         new_var->var_part[i].cur_loc = NULL;
1245     }
1246
1247   dst_can_be_shared = false;
1248   if (shared_hash_shared (set->vars))
1249     slot = shared_hash_find_slot_unshare (&set->vars, var->dv, NO_INSERT);
1250   else if (set->traversed_vars && set->vars != set->traversed_vars)
1251     slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
1252   *slot = new_var;
1253   return slot;
1254 }
1255
1256 /* Add a variable from *SLOT to hash table DATA and increase its reference
1257    count.  */
1258
1259 static int
1260 vars_copy_1 (void **slot, void *data)
1261 {
1262   htab_t dst = (htab_t) data;
1263   variable src;
1264   void **dstp;
1265
1266   src = (variable) *slot;
1267   src->refcount++;
1268
1269   dstp = htab_find_slot_with_hash (dst, src->dv,
1270                                    dv_htab_hash (src->dv),
1271                                    INSERT);
1272   *dstp = src;
1273
1274   /* Continue traversing the hash table.  */
1275   return 1;
1276 }
1277
1278 /* Copy all variables from hash table SRC to hash table DST.  */
1279
1280 static void
1281 vars_copy (htab_t dst, htab_t src)
1282 {
1283   htab_traverse_noresize (src, vars_copy_1, dst);
1284 }
1285
1286 /* Map a decl to its main debug decl.  */
1287
1288 static inline tree
1289 var_debug_decl (tree decl)
1290 {
1291   if (decl && DECL_P (decl)
1292       && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl)
1293       && DECL_P (DECL_DEBUG_EXPR (decl)))
1294     decl = DECL_DEBUG_EXPR (decl);
1295
1296   return decl;
1297 }
1298
1299 /* Set the register LOC to contain DV, OFFSET.  */
1300
1301 static void
1302 var_reg_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1303                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1304                   enum insert_option iopt)
1305 {
1306   attrs node;
1307   bool decl_p = dv_is_decl_p (dv);
1308
1309   if (decl_p)
1310     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1311
1312   for (node = set->regs[REGNO (loc)]; node; node = node->next)
1313     if (dv_as_opaque (node->dv) == dv_as_opaque (dv)
1314         && node->offset == offset)
1315       break;
1316   if (!node)
1317     attrs_list_insert (&set->regs[REGNO (loc)], dv, offset, loc);
1318   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1319 }
1320
1321 /* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
1322
1323 static void
1324 var_reg_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1325              rtx set_src)
1326 {
1327   tree decl = REG_EXPR (loc);
1328   HOST_WIDE_INT offset = REG_OFFSET (loc);
1329
1330   var_reg_decl_set (set, loc, initialized,
1331                     dv_from_decl (decl), offset, set_src, INSERT);
1332 }
1333
1334 static enum var_init_status
1335 get_init_value (dataflow_set *set, rtx loc, decl_or_value dv)
1336 {
1337   variable var;
1338   int i;
1339   enum var_init_status ret_val = VAR_INIT_STATUS_UNKNOWN;
1340
1341   if (! flag_var_tracking_uninit)
1342     return VAR_INIT_STATUS_INITIALIZED;
1343
1344   var = shared_hash_find (set->vars, dv);
1345   if (var)
1346     {
1347       for (i = 0; i < var->n_var_parts && ret_val == VAR_INIT_STATUS_UNKNOWN; i++)
1348         {
1349           location_chain nextp;
1350           for (nextp = var->var_part[i].loc_chain; nextp; nextp = nextp->next)
1351             if (rtx_equal_p (nextp->loc, loc))
1352               {
1353                 ret_val = nextp->init;
1354                 break;
1355               }
1356         }
1357     }
1358
1359   return ret_val;
1360 }
1361
1362 /* Delete current content of register LOC in dataflow set SET and set
1363    the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  If
1364    MODIFY is true, any other live copies of the same variable part are
1365    also deleted from the dataflow set, otherwise the variable part is
1366    assumed to be copied from another location holding the same
1367    part.  */
1368
1369 static void
1370 var_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify, 
1371                         enum var_init_status initialized, rtx set_src)
1372 {
1373   tree decl = REG_EXPR (loc);
1374   HOST_WIDE_INT offset = REG_OFFSET (loc);
1375   attrs node, next;
1376   attrs *nextp;
1377
1378   decl = var_debug_decl (decl);
1379
1380   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1381     initialized = get_init_value (set, loc, dv_from_decl (decl));
1382
1383   nextp = &set->regs[REGNO (loc)];
1384   for (node = *nextp; node; node = next)
1385     {
1386       next = node->next;
1387       if (dv_as_opaque (node->dv) != decl || node->offset != offset)
1388         {
1389           delete_variable_part (set, node->loc, node->dv, node->offset);
1390           pool_free (attrs_pool, node);
1391           *nextp = next;
1392         }
1393       else
1394         {
1395           node->loc = loc;
1396           nextp = &node->next;
1397         }
1398     }
1399   if (modify)
1400     clobber_variable_part (set, loc, dv_from_decl (decl), offset, set_src);
1401   var_reg_set (set, loc, initialized, set_src);
1402 }
1403
1404 /* Delete current content of register LOC in dataflow set SET.  If
1405    CLOBBER is true, also delete any other live copies of the same
1406    variable part.  */
1407
1408 static void
1409 var_reg_delete (dataflow_set *set, rtx loc, bool clobber)
1410 {
1411   attrs *reg = &set->regs[REGNO (loc)];
1412   attrs node, next;
1413
1414   if (clobber)
1415     {
1416       tree decl = REG_EXPR (loc);
1417       HOST_WIDE_INT offset = REG_OFFSET (loc);
1418
1419       decl = var_debug_decl (decl);
1420
1421       clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1422     }
1423
1424   for (node = *reg; node; node = next)
1425     {
1426       next = node->next;
1427       delete_variable_part (set, node->loc, node->dv, node->offset);
1428       pool_free (attrs_pool, node);
1429     }
1430   *reg = NULL;
1431 }
1432
1433 /* Delete content of register with number REGNO in dataflow set SET.  */
1434
1435 static void
1436 var_regno_delete (dataflow_set *set, int regno)
1437 {
1438   attrs *reg = &set->regs[regno];
1439   attrs node, next;
1440
1441   for (node = *reg; node; node = next)
1442     {
1443       next = node->next;
1444       delete_variable_part (set, node->loc, node->dv, node->offset);
1445       pool_free (attrs_pool, node);
1446     }
1447   *reg = NULL;
1448 }
1449
1450 /* Set the location of DV, OFFSET as the MEM LOC.  */
1451
1452 static void
1453 var_mem_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1454                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1455                   enum insert_option iopt)
1456 {
1457   if (dv_is_decl_p (dv))
1458     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1459
1460   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1461 }
1462
1463 /* Set the location part of variable MEM_EXPR (LOC) in dataflow set
1464    SET to LOC.
1465    Adjust the address first if it is stack pointer based.  */
1466
1467 static void
1468 var_mem_set (dataflow_set *set, rtx loc, enum var_init_status initialized, 
1469              rtx set_src)
1470 {
1471   tree decl = MEM_EXPR (loc);
1472   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1473
1474   var_mem_decl_set (set, loc, initialized,
1475                     dv_from_decl (decl), offset, set_src, INSERT);
1476 }
1477
1478 /* Delete and set the location part of variable MEM_EXPR (LOC) in
1479    dataflow set SET to LOC.  If MODIFY is true, any other live copies
1480    of the same variable part are also deleted from the dataflow set,
1481    otherwise the variable part is assumed to be copied from another
1482    location holding the same part.
1483    Adjust the address first if it is stack pointer based.  */
1484
1485 static void
1486 var_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify, 
1487                         enum var_init_status initialized, rtx set_src)
1488 {
1489   tree decl = MEM_EXPR (loc);
1490   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1491
1492   decl = var_debug_decl (decl);
1493
1494   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1495     initialized = get_init_value (set, loc, dv_from_decl (decl));
1496
1497   if (modify)
1498     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, set_src);
1499   var_mem_set (set, loc, initialized, set_src);
1500 }
1501
1502 /* Delete the location part LOC from dataflow set SET.  If CLOBBER is
1503    true, also delete any other live copies of the same variable part.
1504    Adjust the address first if it is stack pointer based.  */
1505
1506 static void
1507 var_mem_delete (dataflow_set *set, rtx loc, bool clobber)
1508 {
1509   tree decl = MEM_EXPR (loc);
1510   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1511
1512   decl = var_debug_decl (decl);
1513   if (clobber)
1514     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1515   delete_variable_part (set, loc, dv_from_decl (decl), offset);
1516 }
1517
1518 /* Map a value to a location it was just stored in.  */
1519
1520 static void
1521 val_store (dataflow_set *set, rtx val, rtx loc, rtx insn)
1522 {
1523   cselib_val *v = CSELIB_VAL_PTR (val);
1524
1525   gcc_assert (cselib_preserved_value_p (v));
1526
1527   if (dump_file)
1528     {
1529       fprintf (dump_file, "%i: ", INSN_UID (insn));
1530       print_inline_rtx (dump_file, val, 0);
1531       fprintf (dump_file, " stored in ");
1532       print_inline_rtx (dump_file, loc, 0);
1533       if (v->locs)
1534         {
1535           struct elt_loc_list *l;
1536           for (l = v->locs; l; l = l->next)
1537             {
1538               fprintf (dump_file, "\n%i: ", INSN_UID (l->setting_insn));
1539               print_inline_rtx (dump_file, l->loc, 0);
1540             }
1541         }
1542       fprintf (dump_file, "\n");
1543     }
1544
1545   if (REG_P (loc))
1546     {
1547       var_regno_delete (set, REGNO (loc));
1548       var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1549                         dv_from_value (val), 0, NULL_RTX, INSERT);
1550     }
1551   else if (MEM_P (loc))
1552     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1553                       dv_from_value (val), 0, NULL_RTX, INSERT);
1554   else
1555     set_variable_part (set, loc, dv_from_value (val), 0,
1556                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1557 }
1558
1559 /* Reset this node, detaching all its equivalences.  Return the slot
1560    in the variable hash table that holds dv, if there is one.  */
1561
1562 static void
1563 val_reset (dataflow_set *set, decl_or_value dv)
1564 {
1565   variable var = shared_hash_find (set->vars, dv) ;
1566   location_chain node;
1567   rtx cval;
1568
1569   if (!var || !var->n_var_parts)
1570     return;
1571
1572   gcc_assert (var->n_var_parts == 1);
1573
1574   cval = NULL;
1575   for (node = var->var_part[0].loc_chain; node; node = node->next)
1576     if (GET_CODE (node->loc) == VALUE
1577         && canon_value_cmp (node->loc, cval))
1578       cval = node->loc;
1579
1580   for (node = var->var_part[0].loc_chain; node; node = node->next)
1581     if (GET_CODE (node->loc) == VALUE && cval != node->loc)
1582       {
1583         /* Redirect the equivalence link to the new canonical
1584            value, or simply remove it if it would point at
1585            itself.  */
1586         if (cval)
1587           set_variable_part (set, cval, dv_from_value (node->loc),
1588                              0, node->init, node->set_src, NO_INSERT);
1589         delete_variable_part (set, dv_as_value (dv),
1590                               dv_from_value (node->loc), 0);
1591       }
1592
1593   if (cval)
1594     {
1595       decl_or_value cdv = dv_from_value (cval);
1596
1597       /* Keep the remaining values connected, accummulating links
1598          in the canonical value.  */
1599       for (node = var->var_part[0].loc_chain; node; node = node->next)
1600         {
1601           if (node->loc == cval)
1602             continue;
1603           else if (GET_CODE (node->loc) == REG)
1604             var_reg_decl_set (set, node->loc, node->init, cdv, 0,
1605                               node->set_src, NO_INSERT);
1606           else if (GET_CODE (node->loc) == MEM)
1607             var_mem_decl_set (set, node->loc, node->init, cdv, 0,
1608                               node->set_src, NO_INSERT);
1609           else
1610             set_variable_part (set, node->loc, cdv, 0,
1611                                node->init, node->set_src, NO_INSERT);
1612         }
1613     }
1614
1615   /* We remove this last, to make sure that the canonical value is not
1616      removed to the point of requiring reinsertion.  */
1617   if (cval)
1618     delete_variable_part (set, dv_as_value (dv), dv_from_value (cval), 0);
1619
1620   clobber_variable_part (set, NULL, dv, 0, NULL);
1621
1622   /* ??? Should we make sure there aren't other available values or
1623      variables whose values involve this one other than by
1624      equivalence?  E.g., at the very least we should reset MEMs, those
1625      shouldn't be too hard to find cselib-looking up the value as an
1626      address, then locating the resulting value in our own hash
1627      table.  */
1628 }
1629
1630 /* Find the values in a given location and map the val to another
1631    value, if it is unique, or add the location as one holding the
1632    value.  */
1633
1634 static void
1635 val_resolve (dataflow_set *set, rtx val, rtx loc, rtx insn)
1636 {
1637   decl_or_value dv = dv_from_value (val);
1638
1639   if (dump_file && (dump_flags & TDF_DETAILS))
1640     {
1641       if (insn)
1642         fprintf (dump_file, "%i: ", INSN_UID (insn));
1643       else
1644         fprintf (dump_file, "head: ");
1645       print_inline_rtx (dump_file, val, 0);
1646       fputs (" is at ", dump_file);
1647       print_inline_rtx (dump_file, loc, 0);
1648       fputc ('\n', dump_file);
1649     }
1650
1651   val_reset (set, dv);
1652
1653   if (REG_P (loc))
1654     {
1655       attrs node, found = NULL;
1656
1657       for (node = set->regs[REGNO (loc)]; node; node = node->next)
1658         if (dv_is_value_p (node->dv)
1659             && GET_MODE (dv_as_value (node->dv)) == GET_MODE (loc))
1660           {
1661             found = node;
1662
1663             /* Map incoming equivalences.  ??? Wouldn't it be nice if
1664              we just started sharing the location lists?  Maybe a
1665              circular list ending at the value itself or some
1666              such.  */
1667             set_variable_part (set, dv_as_value (node->dv),
1668                                dv_from_value (val), node->offset,
1669                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1670             set_variable_part (set, val, node->dv, node->offset,
1671                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1672           }
1673
1674       /* If we didn't find any equivalence, we need to remember that
1675          this value is held in the named register.  */
1676       if (!found)
1677         var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1678                           dv_from_value (val), 0, NULL_RTX, INSERT);
1679     }
1680   else if (MEM_P (loc))
1681     /* ??? Merge equivalent MEMs.  */
1682     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1683                       dv_from_value (val), 0, NULL_RTX, INSERT);
1684   else
1685     /* ??? Merge equivalent expressions.  */
1686     set_variable_part (set, loc, dv_from_value (val), 0,
1687                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1688 }
1689
1690 /* Initialize dataflow set SET to be empty. 
1691    VARS_SIZE is the initial size of hash table VARS.  */
1692
1693 static void
1694 dataflow_set_init (dataflow_set *set)
1695 {
1696   init_attrs_list_set (set->regs);
1697   set->vars = shared_hash_copy (empty_shared_hash);
1698   set->stack_adjust = 0;
1699   set->traversed_vars = NULL;
1700 }
1701
1702 /* Delete the contents of dataflow set SET.  */
1703
1704 static void
1705 dataflow_set_clear (dataflow_set *set)
1706 {
1707   int i;
1708
1709   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1710     attrs_list_clear (&set->regs[i]);
1711
1712   shared_hash_destroy (set->vars);
1713   set->vars = shared_hash_copy (empty_shared_hash);
1714 }
1715
1716 /* Copy the contents of dataflow set SRC to DST.  */
1717
1718 static void
1719 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
1720 {
1721   int i;
1722
1723   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1724     attrs_list_copy (&dst->regs[i], src->regs[i]);
1725
1726   shared_hash_destroy (dst->vars);
1727   dst->vars = shared_hash_copy (src->vars);
1728   dst->stack_adjust = src->stack_adjust;
1729 }
1730
1731 /* Information for merging lists of locations for a given offset of variable.
1732  */
1733 struct variable_union_info
1734 {
1735   /* Node of the location chain.  */
1736   location_chain lc;
1737
1738   /* The sum of positions in the input chains.  */
1739   int pos;
1740
1741   /* The position in the chain of DST dataflow set.  */
1742   int pos_dst;
1743 };
1744
1745 /* Buffer for location list sorting and its allocated size.  */
1746 static struct variable_union_info *vui_vec;
1747 static int vui_allocated;
1748
1749 /* Compare function for qsort, order the structures by POS element.  */
1750
1751 static int
1752 variable_union_info_cmp_pos (const void *n1, const void *n2)
1753 {
1754   const struct variable_union_info *const i1 =
1755     (const struct variable_union_info *) n1;
1756   const struct variable_union_info *const i2 =
1757     ( const struct variable_union_info *) n2;
1758
1759   if (i1->pos != i2->pos)
1760     return i1->pos - i2->pos;
1761   
1762   return (i1->pos_dst - i2->pos_dst);
1763 }
1764
1765 /* Compute union of location parts of variable *SLOT and the same variable
1766    from hash table DATA.  Compute "sorted" union of the location chains
1767    for common offsets, i.e. the locations of a variable part are sorted by
1768    a priority where the priority is the sum of the positions in the 2 chains
1769    (if a location is only in one list the position in the second list is
1770    defined to be larger than the length of the chains).
1771    When we are updating the location parts the newest location is in the
1772    beginning of the chain, so when we do the described "sorted" union
1773    we keep the newest locations in the beginning.  */
1774
1775 static int
1776 variable_union (void **slot, void *data)
1777 {
1778   variable src, dst;
1779   void **dstp;
1780   dataflow_set *set = (dataflow_set *) data;
1781   int i, j, k;
1782
1783   src = (variable) *slot;
1784   dstp = shared_hash_find_slot (set->vars, src->dv);
1785   if (!dstp || !*dstp)
1786     {
1787       src->refcount++;
1788
1789       dst_can_be_shared = false;
1790       if (!dstp)
1791         dstp = shared_hash_find_slot_unshare (&set->vars, src->dv, INSERT);
1792
1793       *dstp = src;
1794
1795       /* If CUR_LOC of some variable part is not the first element of
1796          the location chain we are going to change it so we have to make
1797          a copy of the variable.  */
1798       for (k = 0; k < src->n_var_parts; k++)
1799         {
1800           gcc_assert (!src->var_part[k].loc_chain
1801                       == !src->var_part[k].cur_loc);
1802           if (src->var_part[k].loc_chain)
1803             {
1804               gcc_assert (src->var_part[k].cur_loc);
1805               if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1806                 break;
1807             }
1808         }
1809       if (k < src->n_var_parts)
1810         dstp = unshare_variable (set, dstp, src, VAR_INIT_STATUS_UNKNOWN);
1811
1812       /* Continue traversing the hash table.  */
1813       return 1;
1814     }
1815   else
1816     dst = (variable) *dstp;
1817
1818   gcc_assert (src->n_var_parts);
1819
1820   /* We can combine one-part variables very efficiently, because their
1821      entries are in canonical order.  */
1822   if (dv_onepart_p (src->dv))
1823     {
1824       location_chain *nodep, dnode, snode;
1825
1826       gcc_assert (src->n_var_parts == 1);
1827       gcc_assert (dst->n_var_parts == 1);
1828
1829       snode = src->var_part[0].loc_chain;
1830       gcc_assert (snode);
1831
1832     restart_onepart_unshared:
1833       nodep = &dst->var_part[0].loc_chain;
1834       dnode = *nodep;
1835       gcc_assert (dnode);
1836
1837       while (snode)
1838         {
1839           int r = dnode ? loc_cmp (dnode->loc, snode->loc) : 1;
1840
1841           if (r > 0)
1842             {
1843               location_chain nnode;
1844
1845               if (dst->refcount != 1 || shared_hash_shared (set->vars))
1846                 {
1847                   dstp = unshare_variable (set, dstp, dst,
1848                                            VAR_INIT_STATUS_INITIALIZED);
1849                   dst = (variable)*dstp;
1850                   goto restart_onepart_unshared;
1851                 }
1852
1853               *nodep = nnode = (location_chain) pool_alloc (loc_chain_pool);
1854               nnode->loc = snode->loc;
1855               nnode->init = snode->init;
1856               if (!snode->set_src || MEM_P (snode->set_src))
1857                 nnode->set_src = NULL;
1858               else
1859                 nnode->set_src = snode->set_src;
1860               nnode->next = dnode;
1861               dnode = nnode;
1862             }
1863 #ifdef ENABLE_CHECKING
1864           else if (r == 0)
1865             gcc_assert (rtx_equal_p (dnode->loc, snode->loc));
1866 #endif
1867
1868           if (r >= 0)
1869             snode = snode->next;
1870
1871           nodep = &dnode->next;
1872           dnode = *nodep;
1873         }
1874
1875       dst->var_part[0].cur_loc = dst->var_part[0].loc_chain->loc;
1876
1877       return 1;
1878     }
1879
1880   /* Count the number of location parts, result is K.  */
1881   for (i = 0, j = 0, k = 0;
1882        i < src->n_var_parts && j < dst->n_var_parts; k++)
1883     {
1884       if (src->var_part[i].offset == dst->var_part[j].offset)
1885         {
1886           i++;
1887           j++;
1888         }
1889       else if (src->var_part[i].offset < dst->var_part[j].offset)
1890         i++;
1891       else
1892         j++;
1893     }
1894   k += src->n_var_parts - i;
1895   k += dst->n_var_parts - j;
1896
1897   /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1898      thus there are at most MAX_VAR_PARTS different offsets.  */
1899   gcc_assert (dv_onepart_p (dst->dv) ? k == 1 : k <= MAX_VAR_PARTS);
1900
1901   if ((dst->refcount > 1 || shared_hash_shared (set->vars))
1902       && dst->n_var_parts != k)
1903     {
1904       dstp = unshare_variable (set, dstp, dst, VAR_INIT_STATUS_UNKNOWN);
1905       dst = (variable)*dstp;
1906     }
1907
1908   i = src->n_var_parts - 1;
1909   j = dst->n_var_parts - 1;
1910   dst->n_var_parts = k;
1911
1912   for (k--; k >= 0; k--)
1913     {
1914       location_chain node, node2;
1915
1916       if (i >= 0 && j >= 0
1917           && src->var_part[i].offset == dst->var_part[j].offset)
1918         {
1919           /* Compute the "sorted" union of the chains, i.e. the locations which
1920              are in both chains go first, they are sorted by the sum of
1921              positions in the chains.  */
1922           int dst_l, src_l;
1923           int ii, jj, n;
1924           struct variable_union_info *vui;
1925
1926           /* If DST is shared compare the location chains.
1927              If they are different we will modify the chain in DST with
1928              high probability so make a copy of DST.  */
1929           if (dst->refcount > 1 || shared_hash_shared (set->vars))
1930             {
1931               for (node = src->var_part[i].loc_chain,
1932                    node2 = dst->var_part[j].loc_chain; node && node2;
1933                    node = node->next, node2 = node2->next)
1934                 {
1935                   if (!((REG_P (node2->loc)
1936                          && REG_P (node->loc)
1937                          && REGNO (node2->loc) == REGNO (node->loc))
1938                         || rtx_equal_p (node2->loc, node->loc)))
1939                     {
1940                       if (node2->init < node->init)
1941                         node2->init = node->init;
1942                       break;
1943                     }
1944                 }
1945               if (node || node2)
1946                 {
1947                   dstp = unshare_variable (set, dstp, dst,
1948                                            VAR_INIT_STATUS_UNKNOWN);
1949                   dst = (variable)*dstp;
1950                 }
1951             }
1952
1953           src_l = 0;
1954           for (node = src->var_part[i].loc_chain; node; node = node->next)
1955             src_l++;
1956           dst_l = 0;
1957           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1958             dst_l++;
1959
1960           if (dst_l == 1)
1961             {
1962               /* The most common case, much simpler, no qsort is needed.  */
1963               location_chain dstnode = dst->var_part[j].loc_chain;
1964               dst->var_part[k].loc_chain = dstnode;
1965               dst->var_part[k].offset = dst->var_part[j].offset;
1966               node2 = dstnode;
1967               for (node = src->var_part[i].loc_chain; node; node = node->next)
1968                 if (!((REG_P (dstnode->loc)
1969                        && REG_P (node->loc)
1970                        && REGNO (dstnode->loc) == REGNO (node->loc))
1971                       || rtx_equal_p (dstnode->loc, node->loc)))
1972                   {
1973                     location_chain new_node;
1974
1975                     /* Copy the location from SRC.  */
1976                     new_node = (location_chain) pool_alloc (loc_chain_pool);
1977                     new_node->loc = node->loc;
1978                     new_node->init = node->init;
1979                     if (!node->set_src || MEM_P (node->set_src))
1980                       new_node->set_src = NULL;
1981                     else
1982                       new_node->set_src = node->set_src;
1983                     node2->next = new_node;
1984                     node2 = new_node;
1985                   }
1986               node2->next = NULL;
1987             }
1988           else
1989             {
1990               if (src_l + dst_l > vui_allocated)
1991                 {
1992                   vui_allocated = MAX (vui_allocated * 2, src_l + dst_l);
1993                   vui_vec = XRESIZEVEC (struct variable_union_info, vui_vec,
1994                                         vui_allocated);
1995                 }
1996               vui = vui_vec;
1997
1998               /* Fill in the locations from DST.  */
1999               for (node = dst->var_part[j].loc_chain, jj = 0; node;
2000                    node = node->next, jj++)
2001                 {
2002                   vui[jj].lc = node;
2003                   vui[jj].pos_dst = jj;
2004
2005                   /* Pos plus value larger than a sum of 2 valid positions.  */
2006                   vui[jj].pos = jj + src_l + dst_l;
2007                 }
2008
2009               /* Fill in the locations from SRC.  */
2010               n = dst_l;
2011               for (node = src->var_part[i].loc_chain, ii = 0; node;
2012                    node = node->next, ii++)
2013                 {
2014                   /* Find location from NODE.  */
2015                   for (jj = 0; jj < dst_l; jj++)
2016                     {
2017                       if ((REG_P (vui[jj].lc->loc)
2018                            && REG_P (node->loc)
2019                            && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
2020                           || rtx_equal_p (vui[jj].lc->loc, node->loc))
2021                         {
2022                           vui[jj].pos = jj + ii;
2023                           break;
2024                         }
2025                     }
2026                   if (jj >= dst_l)      /* The location has not been found.  */
2027                     {
2028                       location_chain new_node;
2029
2030                       /* Copy the location from SRC.  */
2031                       new_node = (location_chain) pool_alloc (loc_chain_pool);
2032                       new_node->loc = node->loc;
2033                       new_node->init = node->init;
2034                       if (!node->set_src || MEM_P (node->set_src))
2035                         new_node->set_src = NULL;
2036                       else
2037                         new_node->set_src = node->set_src;
2038                       vui[n].lc = new_node;
2039                       vui[n].pos_dst = src_l + dst_l;
2040                       vui[n].pos = ii + src_l + dst_l;
2041                       n++;
2042                     }
2043                 }
2044
2045               if (dst_l == 2)
2046                 {
2047                   /* Special case still very common case.  For dst_l == 2
2048                      all entries dst_l ... n-1 are sorted, with for i >= dst_l
2049                      vui[i].pos == i + src_l + dst_l.  */
2050                   if (vui[0].pos > vui[1].pos)
2051                     {
2052                       /* Order should be 1, 0, 2... */
2053                       dst->var_part[k].loc_chain = vui[1].lc;
2054                       vui[1].lc->next = vui[0].lc;
2055                       if (n >= 3)
2056                         {
2057                           vui[0].lc->next = vui[2].lc;
2058                           vui[n - 1].lc->next = NULL;
2059                         }
2060                       else
2061                         vui[0].lc->next = NULL;
2062                       ii = 3;
2063                     }
2064                   else
2065                     {
2066                       dst->var_part[k].loc_chain = vui[0].lc;
2067                       if (n >= 3 && vui[2].pos < vui[1].pos)
2068                         {
2069                           /* Order should be 0, 2, 1, 3... */
2070                           vui[0].lc->next = vui[2].lc;
2071                           vui[2].lc->next = vui[1].lc;
2072                           if (n >= 4)
2073                             {
2074                               vui[1].lc->next = vui[3].lc;
2075                               vui[n - 1].lc->next = NULL;
2076                             }
2077                           else
2078                             vui[1].lc->next = NULL;
2079                           ii = 4;
2080                         }
2081                       else
2082                         {
2083                           /* Order should be 0, 1, 2... */
2084                           ii = 1;
2085                           vui[n - 1].lc->next = NULL;
2086                         }
2087                     }
2088                   for (; ii < n; ii++)
2089                     vui[ii - 1].lc->next = vui[ii].lc;
2090                 }
2091               else
2092                 {
2093                   qsort (vui, n, sizeof (struct variable_union_info),
2094                          variable_union_info_cmp_pos);
2095
2096                   /* Reconnect the nodes in sorted order.  */
2097                   for (ii = 1; ii < n; ii++)
2098                     vui[ii - 1].lc->next = vui[ii].lc;
2099                   vui[n - 1].lc->next = NULL;
2100                   dst->var_part[k].loc_chain = vui[0].lc;
2101                 }
2102
2103               dst->var_part[k].offset = dst->var_part[j].offset;
2104             }
2105           i--;
2106           j--;
2107         }
2108       else if ((i >= 0 && j >= 0
2109                 && src->var_part[i].offset < dst->var_part[j].offset)
2110                || i < 0)
2111         {
2112           dst->var_part[k] = dst->var_part[j];
2113           j--;
2114         }
2115       else if ((i >= 0 && j >= 0
2116                 && src->var_part[i].offset > dst->var_part[j].offset)
2117                || j < 0)
2118         {
2119           location_chain *nextp;
2120
2121           /* Copy the chain from SRC.  */
2122           nextp = &dst->var_part[k].loc_chain;
2123           for (node = src->var_part[i].loc_chain; node; node = node->next)
2124             {
2125               location_chain new_lc;
2126
2127               new_lc = (location_chain) pool_alloc (loc_chain_pool);
2128               new_lc->next = NULL;
2129               new_lc->init = node->init;
2130               if (!node->set_src || MEM_P (node->set_src))
2131                 new_lc->set_src = NULL;
2132               else
2133                 new_lc->set_src = node->set_src;
2134               new_lc->loc = node->loc;
2135
2136               *nextp = new_lc;
2137               nextp = &new_lc->next;
2138             }
2139
2140           dst->var_part[k].offset = src->var_part[i].offset;
2141           i--;
2142         }
2143
2144       /* We are at the basic block boundary when computing union
2145          so set the CUR_LOC to be the first element of the chain.  */
2146       if (dst->var_part[k].loc_chain)
2147         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
2148       else
2149         dst->var_part[k].cur_loc = NULL;
2150     }
2151
2152   if (flag_var_tracking_uninit)
2153     for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++)
2154       {
2155         location_chain node, node2;
2156         for (node = src->var_part[i].loc_chain; node; node = node->next)
2157           for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next)
2158             if (rtx_equal_p (node->loc, node2->loc))
2159               {
2160                 if (node->init > node2->init)
2161                   node2->init = node->init;
2162               }
2163       }
2164
2165   /* Continue traversing the hash table.  */
2166   return 1;
2167 }
2168
2169 /* Like variable_union, but only used when doing dataflow_set_union
2170    into an empty hashtab.  To allow sharing, dst is initially shared
2171    with src (so all variables are "copied" from src to dst hashtab),
2172    so only unshare_variable for variables that need canonicalization
2173    are needed.  */
2174
2175 static int
2176 variable_canonicalize (void **slot, void *data)
2177 {
2178   variable src;
2179   dataflow_set *set = (dataflow_set *) data;
2180   int k;
2181
2182   src = *(variable *) slot;
2183
2184   /* If CUR_LOC of some variable part is not the first element of
2185      the location chain we are going to change it so we have to make
2186      a copy of the variable.  */
2187   for (k = 0; k < src->n_var_parts; k++)
2188     {
2189       gcc_assert (!src->var_part[k].loc_chain == !src->var_part[k].cur_loc);
2190       if (src->var_part[k].loc_chain)
2191         {
2192           gcc_assert (src->var_part[k].cur_loc);
2193           if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
2194             break;
2195         }
2196     }
2197   if (k < src->n_var_parts)
2198     slot = unshare_variable (set, slot, src, VAR_INIT_STATUS_UNKNOWN);
2199   return 1;
2200 }
2201
2202 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
2203
2204 static void
2205 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
2206 {
2207   int i;
2208
2209   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2210     attrs_list_union (&dst->regs[i], src->regs[i]);
2211
2212   if (dst->vars == empty_shared_hash)
2213     {
2214       shared_hash_destroy (dst->vars);
2215       dst->vars = shared_hash_copy (src->vars);
2216       dst->traversed_vars = dst->vars;
2217       htab_traverse (shared_hash_htab (dst->vars), variable_canonicalize, dst);
2218       dst->traversed_vars = NULL;
2219     }
2220   else
2221     htab_traverse (shared_hash_htab (src->vars), variable_union, dst);
2222 }
2223
2224 /* Whether the value is currently being expanded.  */
2225 #define VALUE_RECURSED_INTO(x) \
2226   (RTL_FLAG_CHECK2 ("VALUE_RECURSED_INTO", (x), VALUE, DEBUG_EXPR)->used)
2227 /* Whether the value is in changed_variables hash table.  */
2228 #define VALUE_CHANGED(x) \
2229   (RTL_FLAG_CHECK1 ("VALUE_CHANGED", (x), VALUE)->frame_related)
2230 /* Whether the decl is in changed_variables hash table.  */
2231 #define DECL_CHANGED(x) TREE_VISITED (x)
2232
2233 /* Record that DV has been added into resp. removed from changed_variables
2234    hashtable.  */
2235
2236 static inline void
2237 set_dv_changed (decl_or_value dv, bool newv)
2238 {
2239   if (dv_is_value_p (dv))
2240     VALUE_CHANGED (dv_as_value (dv)) = newv;
2241   else
2242     DECL_CHANGED (dv_as_decl (dv)) = newv;
2243 }
2244
2245 /* Return true if DV is present in changed_variables hash table.  */
2246
2247 static inline bool
2248 dv_changed_p (decl_or_value dv)
2249 {
2250   return (dv_is_value_p (dv)
2251           ? VALUE_CHANGED (dv_as_value (dv))
2252           : DECL_CHANGED (dv_as_decl (dv)));
2253 }
2254
2255 /* Return a location list node whose loc is rtx_equal to LOC, in the
2256    location list of a one-part variable or value VAR, or in that of
2257    any values recursively mentioned in the location lists.  */
2258
2259 static location_chain
2260 find_loc_in_1pdv (rtx loc, variable var, htab_t vars)
2261 {
2262   location_chain node;
2263
2264   if (!var)
2265     return NULL;
2266
2267   gcc_assert (dv_onepart_p (var->dv));
2268
2269   if (!var->n_var_parts)
2270     return NULL;
2271
2272   gcc_assert (var->var_part[0].offset == 0);
2273
2274   for (node = var->var_part[0].loc_chain; node; node = node->next)
2275     if (rtx_equal_p (loc, node->loc))
2276       return node;
2277     else if (GET_CODE (node->loc) == VALUE
2278              && !VALUE_RECURSED_INTO (node->loc))
2279       {
2280         decl_or_value dv = dv_from_value (node->loc);
2281         variable var = (variable)
2282                        htab_find_with_hash (vars, dv, dv_htab_hash (dv));
2283
2284         if (var)
2285           {
2286             location_chain where;
2287             VALUE_RECURSED_INTO (node->loc) = true;
2288             if ((where = find_loc_in_1pdv (loc, var, vars)))
2289               {
2290                 VALUE_RECURSED_INTO (node->loc) = false;
2291                 return where;
2292               }
2293             VALUE_RECURSED_INTO (node->loc) = false;
2294           }
2295       }
2296
2297   return NULL;
2298 }
2299
2300 /* Hash table iteration argument passed to variable_merge.  */
2301 struct dfset_merge
2302 {
2303   /* The set in which the merge is to be inserted.  */
2304   dataflow_set *dst;
2305   /* The set that we're iterating in.  */
2306   dataflow_set *cur;
2307   /* The set that may contain the other dv we are to merge with.  */
2308   dataflow_set *src;
2309   /* Number of onepart dvs in src.  */
2310   int src_onepart_cnt;
2311 };
2312
2313 /* Insert LOC in *DNODE, if it's not there yet.  The list must be in
2314    loc_cmp order, and it is maintained as such.  */
2315
2316 static void
2317 insert_into_intersection (location_chain *nodep, rtx loc,
2318                           enum var_init_status status)
2319 {
2320   location_chain node;
2321   int r;
2322
2323   for (node = *nodep; node; nodep = &node->next, node = *nodep)
2324     if ((r = loc_cmp (node->loc, loc)) == 0)
2325       {
2326         node->init = MIN (node->init, status);
2327         return;
2328       }
2329     else if (r > 0)
2330       break;
2331
2332   node = (location_chain) pool_alloc (loc_chain_pool);
2333
2334   node->loc = loc;
2335   node->set_src = NULL;
2336   node->init = status;
2337   node->next = *nodep;
2338   *nodep = node;
2339 }
2340
2341 /* Insert in DEST the intersection the locations present in both
2342    S1NODE and S2VAR, directly or indirectly.  S1NODE is from a
2343    variable in DSM->cur, whereas S2VAR is from DSM->src.  dvar is in
2344    DSM->dst.  */
2345
2346 static void
2347 intersect_loc_chains (rtx val, location_chain *dest, struct dfset_merge *dsm,
2348                       location_chain s1node, variable s2var)
2349 {
2350   dataflow_set *s1set = dsm->cur;
2351   dataflow_set *s2set = dsm->src;
2352   location_chain found;
2353
2354   for (; s1node; s1node = s1node->next)
2355     {
2356       if (s1node->loc == val)
2357         continue;
2358
2359       if ((found = find_loc_in_1pdv (s1node->loc, s2var,
2360                                      shared_hash_htab (s2set->vars))))
2361         {
2362           insert_into_intersection (dest, s1node->loc,
2363                                     MIN (s1node->init, found->init));
2364           continue;
2365         }
2366
2367       if (GET_CODE (s1node->loc) == VALUE
2368           && !VALUE_RECURSED_INTO (s1node->loc))
2369         {
2370           decl_or_value dv = dv_from_value (s1node->loc);
2371           variable svar = shared_hash_find (s1set->vars, dv);
2372           if (svar)
2373             {
2374               if (svar->n_var_parts == 1)
2375                 {
2376                   VALUE_RECURSED_INTO (s1node->loc) = true;
2377                   intersect_loc_chains (val, dest, dsm,
2378                                         svar->var_part[0].loc_chain,
2379                                         s2var);
2380                   VALUE_RECURSED_INTO (s1node->loc) = false;
2381                 }
2382             }
2383         }
2384
2385       /* ??? if the location is equivalent to any location in src,
2386          searched recursively
2387
2388            add to dst the values needed to represent the equivalence
2389
2390      telling whether locations S is equivalent to another dv's
2391      location list:
2392
2393        for each location D in the list
2394
2395          if S and D satisfy rtx_equal_p, then it is present
2396
2397          else if D is a value, recurse without cycles
2398
2399          else if S and D have the same CODE and MODE
2400
2401            for each operand oS and the corresponding oD
2402
2403              if oS and oD are not equivalent, then S an D are not equivalent
2404
2405              else if they are RTX vectors
2406
2407                if any vector oS element is not equivalent to its respective oD,
2408                then S and D are not equivalent
2409
2410    */
2411
2412
2413     }
2414 }
2415
2416 /* Return -1 if X should be before Y in a location list for a 1-part
2417    variable, 1 if Y should be before X, and 0 if they're equivalent
2418    and should not appear in the list.  */
2419
2420 static int
2421 loc_cmp (rtx x, rtx y)
2422 {
2423   int i, j, r;
2424   RTX_CODE code = GET_CODE (x);
2425   const char *fmt;
2426
2427   if (x == y)
2428     return 0;
2429
2430   if (REG_P (x))
2431     {
2432       if (!REG_P (y))
2433         return -1;
2434       gcc_assert (GET_MODE (x) == GET_MODE (y));
2435       if (REGNO (x) == REGNO (y))
2436         return 0;
2437       else if (REGNO (x) < REGNO (y))
2438         return -1;
2439       else
2440         return 1;
2441     }
2442
2443   if (REG_P (y))
2444     return 1;
2445
2446   if (MEM_P (x))
2447     {
2448       if (!MEM_P (y))
2449         return -1;
2450       gcc_assert (GET_MODE (x) == GET_MODE (y));
2451       return loc_cmp (XEXP (x, 0), XEXP (y, 0));
2452     }
2453
2454   if (MEM_P (y))
2455     return 1;
2456
2457   if (GET_CODE (x) == VALUE)
2458     {
2459       if (GET_CODE (y) != VALUE)
2460         return -1;
2461       gcc_assert (GET_MODE (x) == GET_MODE (y));
2462       if (canon_value_cmp (x, y))
2463         return -1;
2464       else
2465         return 1;
2466     }
2467
2468   if (GET_CODE (y) == VALUE)
2469     return 1;
2470
2471   if (GET_CODE (x) == GET_CODE (y))
2472     /* Compare operands below.  */;
2473   else if (GET_CODE (x) < GET_CODE (y))
2474     return -1;
2475   else
2476     return 1;
2477
2478   gcc_assert (GET_MODE (x) == GET_MODE (y));
2479
2480   fmt = GET_RTX_FORMAT (code);
2481   for (i = 0; i < GET_RTX_LENGTH (code); i++)
2482     switch (fmt[i])
2483       {
2484       case 'w':
2485         if (XWINT (x, i) == XWINT (y, i))
2486           break;
2487         else if (XWINT (x, i) < XWINT (y, i))
2488           return -1;
2489         else
2490           return 1;
2491
2492       case 'n':
2493       case 'i':
2494         if (XINT (x, i) == XINT (y, i))
2495           break;
2496         else if (XINT (x, i) < XINT (y, i))
2497           return -1;
2498         else
2499           return 1;
2500
2501       case 'V':
2502       case 'E':
2503         /* Compare the vector length first.  */
2504         if (XVECLEN (x, i) == XVECLEN (y, i))
2505           /* Compare the vectors elements.  */;
2506         else if (XVECLEN (x, i) < XVECLEN (y, i))
2507           return -1;
2508         else
2509           return 1;
2510
2511         for (j = 0; j < XVECLEN (x, i); j++)
2512           if ((r = loc_cmp (XVECEXP (x, i, j),
2513                             XVECEXP (y, i, j))))
2514             return r;
2515         break;
2516
2517       case 'e':
2518         if ((r = loc_cmp (XEXP (x, i), XEXP (y, i))))
2519           return r;
2520         break;
2521
2522       case 'S':
2523       case 's':
2524         if (XSTR (x, i) == XSTR (y, i))
2525           break;
2526         if (!XSTR (x, i))
2527           return -1;
2528         if (!XSTR (y, i))
2529           return 1;
2530         if ((r = strcmp (XSTR (x, i), XSTR (y, i))) == 0)
2531           break;
2532         else if (r < 0)
2533           return -1;
2534         else
2535           return 1;
2536
2537       case 'u':
2538         /* These are just backpointers, so they don't matter.  */
2539         break;
2540
2541       case '0':
2542       case 't':
2543         break;
2544
2545         /* It is believed that rtx's at this level will never
2546            contain anything but integers and other rtx's,
2547            except for within LABEL_REFs and SYMBOL_REFs.  */
2548       default:
2549         gcc_unreachable ();
2550       }
2551
2552   return 0;
2553 }
2554
2555 /* If decl or value DVP refers to VALUE from *LOC, add backlinks
2556    from VALUE to DVP.  */
2557
2558 static int
2559 add_value_chain (rtx *loc, void *dvp)
2560 {
2561   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2562     {
2563       decl_or_value dv = (decl_or_value) dvp;
2564       decl_or_value ldv = dv_from_value (*loc);
2565       value_chain vc, nvc;
2566       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2567                                               dv_htab_hash (ldv), INSERT);
2568       if (!*slot)
2569         {
2570           vc = (value_chain) pool_alloc (value_chain_pool);
2571           vc->dv = ldv;
2572           vc->next = NULL;
2573           vc->refcount = 0;
2574           *slot = (void *) vc;
2575         }
2576       else
2577         {
2578           for (vc = ((value_chain) *slot)->next; vc; vc = vc->next)
2579             if (dv_as_opaque (vc->dv) == dv_as_opaque (dv))
2580               break;
2581           if (vc)
2582             {
2583               vc->refcount++;
2584               return 0;
2585             }
2586         }
2587       vc = (value_chain) *slot;
2588       nvc = (value_chain) pool_alloc (value_chain_pool);
2589       nvc->dv = dv;
2590       nvc->next = vc->next;
2591       nvc->refcount = 1;
2592       vc->next = nvc;
2593     }
2594   return 0;
2595 }
2596
2597 /* If decl or value DVP refers to VALUEs from within LOC, add backlinks
2598    from those VALUEs to DVP.  */
2599
2600 static void
2601 add_value_chains (decl_or_value dv, rtx loc)
2602 {
2603   if (GET_CODE (loc) == VALUE)
2604     {
2605       add_value_chain (&loc, dv_as_opaque (dv));
2606       return;
2607     }
2608   if (REG_P (loc))
2609     return;
2610   if (MEM_P (loc))
2611     loc = XEXP (loc, 0);
2612   for_each_rtx (&loc, add_value_chain, dv_as_opaque (dv));
2613 }
2614
2615 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, add backlinks from those
2616    VALUEs to DV.  */
2617
2618 static void
2619 add_cselib_value_chains (decl_or_value dv)
2620 {
2621   struct elt_loc_list *l;
2622
2623   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2624     for_each_rtx (&l->loc, add_value_chain, dv_as_opaque (dv));
2625 }
2626
2627 /* If decl or value DVP refers to VALUE from *LOC, remove backlinks
2628    from VALUE to DVP.  */
2629
2630 static int
2631 remove_value_chain (rtx *loc, void *dvp)
2632 {
2633   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2634     {
2635       decl_or_value dv = (decl_or_value) dvp;
2636       decl_or_value ldv = dv_from_value (*loc);
2637       value_chain vc, dvc = NULL;
2638       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2639                                               dv_htab_hash (ldv), NO_INSERT);
2640       for (vc = (value_chain) *slot; vc->next; vc = vc->next)
2641         if (dv_as_opaque (vc->next->dv) == dv_as_opaque (dv))
2642           {
2643             dvc = vc->next;
2644             gcc_assert (dvc->refcount > 0);
2645             if (--dvc->refcount == 0)
2646               {
2647                 vc->next = dvc->next;
2648                 pool_free (value_chain_pool, dvc);
2649                 if (vc->next == NULL && vc == (value_chain) *slot)
2650                   {
2651                     pool_free (value_chain_pool, vc);
2652                     htab_clear_slot (value_chains, slot);
2653                   }
2654               }
2655             return 0;
2656           }
2657       gcc_unreachable ();
2658     }
2659   return 0;
2660 }
2661
2662 /* If decl or value DVP refers to VALUEs from within LOC, remove backlinks
2663    from those VALUEs to DVP.  */
2664
2665 static void
2666 remove_value_chains (decl_or_value dv, rtx loc)
2667 {
2668   if (GET_CODE (loc) == VALUE)
2669     {
2670       remove_value_chain (&loc, dv_as_opaque (dv));
2671       return;
2672     }
2673   if (REG_P (loc))
2674     return;
2675   if (MEM_P (loc))
2676     loc = XEXP (loc, 0);
2677   for_each_rtx (&loc, remove_value_chain, dv_as_opaque (dv));
2678 }
2679
2680 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, remove backlinks from those
2681    VALUEs to DV.  */
2682
2683 static void
2684 remove_cselib_value_chains (decl_or_value dv)
2685 {
2686   struct elt_loc_list *l;
2687
2688   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2689     for_each_rtx (&l->loc, remove_value_chain, dv_as_opaque (dv));
2690 }
2691
2692 #if ENABLE_CHECKING
2693 /* Check the order of entries in one-part variables.   */
2694
2695 static int
2696 canonicalize_loc_order_check (void **slot, void *data ATTRIBUTE_UNUSED)
2697 {
2698   variable var = (variable) *slot;
2699   decl_or_value dv = var->dv;
2700   location_chain node, next;
2701
2702   if (!dv_onepart_p (dv))
2703     return 1;
2704
2705   gcc_assert (var->n_var_parts == 1);
2706   node = var->var_part[0].loc_chain;
2707   gcc_assert (node);
2708
2709   while ((next = node->next))
2710     {
2711       gcc_assert (loc_cmp (node->loc, next->loc) < 0);
2712       node = next;
2713     }
2714
2715   return 1;
2716 }
2717 #endif
2718
2719 /* Mark with VALUE_RECURSED_INTO values that have neighbors that are
2720    more likely to be chosen as canonical for an equivalence set.
2721    Ensure less likely values can reach more likely neighbors, making
2722    the connections bidirectional.  */
2723
2724 static int
2725 canonicalize_values_mark (void **slot, void *data)
2726 {
2727   dataflow_set *set = (dataflow_set *)data;
2728   variable var = (variable) *slot;
2729   decl_or_value dv = var->dv;
2730   rtx val;
2731   location_chain node;
2732
2733   if (!dv_is_value_p (dv))
2734     return 1;
2735
2736   gcc_assert (var->n_var_parts == 1);
2737
2738   val = dv_as_value (dv);
2739
2740   for (node = var->var_part[0].loc_chain; node; node = node->next)
2741     if (GET_CODE (node->loc) == VALUE)
2742       {
2743         if (canon_value_cmp (node->loc, val))
2744           VALUE_RECURSED_INTO (val) = true;
2745         else
2746           {
2747             decl_or_value odv = dv_from_value (node->loc);
2748             void **oslot = shared_hash_find_slot_noinsert (set->vars, odv);
2749
2750             oslot = set_slot_part (set, val, oslot, odv, 0,
2751                                    node->init, NULL_RTX);
2752
2753             VALUE_RECURSED_INTO (node->loc) = true;
2754           }
2755       }
2756
2757   return 1;
2758 }
2759
2760 /* Remove redundant entries from equivalence lists in onepart
2761    variables, canonicalizing equivalence sets into star shapes.  */
2762
2763 static int
2764 canonicalize_values_star (void **slot, void *data)
2765 {
2766   dataflow_set *set = (dataflow_set *)data;
2767   variable var = (variable) *slot;
2768   decl_or_value dv = var->dv;
2769   location_chain node;
2770   decl_or_value cdv;
2771   rtx val, cval;
2772   void **cslot;
2773   bool has_value;
2774   bool has_marks;
2775
2776   if (!dv_onepart_p (dv))
2777     return 1;
2778
2779   gcc_assert (var->n_var_parts == 1);
2780
2781   if (dv_is_value_p (dv))
2782     {
2783       cval = dv_as_value (dv);
2784       if (!VALUE_RECURSED_INTO (cval))
2785         return 1;
2786       VALUE_RECURSED_INTO (cval) = false;
2787     }
2788   else
2789     cval = NULL_RTX;
2790
2791  restart:
2792   val = cval;
2793   has_value = false;
2794   has_marks = false;
2795
2796   gcc_assert (var->n_var_parts == 1);
2797
2798   for (node = var->var_part[0].loc_chain; node; node = node->next)
2799     if (GET_CODE (node->loc) == VALUE)
2800       {
2801         has_value = true;
2802         if (VALUE_RECURSED_INTO (node->loc))
2803           has_marks = true;
2804         if (canon_value_cmp (node->loc, cval))
2805           cval = node->loc;
2806       }
2807
2808   if (!has_value)
2809     return 1;
2810
2811   if (cval == val)
2812     {
2813       if (!has_marks || dv_is_decl_p (dv))
2814         return 1;
2815
2816       /* Keep it marked so that we revisit it, either after visiting a
2817          child node, or after visiting a new parent that might be
2818          found out.  */
2819       VALUE_RECURSED_INTO (val) = true;
2820
2821       for (node = var->var_part[0].loc_chain; node; node = node->next)
2822         if (GET_CODE (node->loc) == VALUE
2823             && VALUE_RECURSED_INTO (node->loc))
2824           {
2825             cval = node->loc;
2826           restart_with_cval:
2827             VALUE_RECURSED_INTO (cval) = false;
2828             dv = dv_from_value (cval);
2829             slot = shared_hash_find_slot_noinsert (set->vars, dv);
2830             if (!slot)
2831               {
2832                 gcc_assert (dv_is_decl_p (var->dv));
2833                 /* The canonical value was reset and dropped.
2834                    Remove it.  */
2835                 clobber_variable_part (set, NULL, var->dv, 0, NULL);
2836                 return 1;
2837               }
2838             var = (variable)*slot;
2839             gcc_assert (dv_is_value_p (var->dv));
2840             if (var->n_var_parts == 0)
2841               return 1;
2842             gcc_assert (var->n_var_parts == 1);
2843             goto restart;
2844           }
2845
2846       VALUE_RECURSED_INTO (val) = false;
2847
2848       return 1;
2849     }
2850
2851   /* Push values to the canonical one.  */
2852   cdv = dv_from_value (cval);
2853   cslot = shared_hash_find_slot_noinsert (set->vars, cdv);
2854
2855   for (node = var->var_part[0].loc_chain; node; node = node->next)
2856     if (node->loc != cval)
2857       {
2858         cslot = set_slot_part (set, node->loc, cslot, cdv, 0,
2859                                node->init, NULL_RTX);
2860         if (GET_CODE (node->loc) == VALUE)
2861           {
2862             decl_or_value ndv = dv_from_value (node->loc);
2863
2864             set_variable_part (set, cval, ndv, 0, node->init, NULL_RTX,
2865                                NO_INSERT);
2866
2867             if (canon_value_cmp (node->loc, val))
2868               {
2869                 /* If it could have been a local minimum, it's not any more,
2870                    since it's now neighbor to cval, so it may have to push
2871                    to it.  Conversely, if it wouldn't have prevailed over
2872                    val, then whatever mark it has is fine: if it was to
2873                    push, it will now push to a more canonical node, but if
2874                    it wasn't, then it has already pushed any values it might
2875                    have to.  */
2876                 VALUE_RECURSED_INTO (node->loc) = true;
2877                 /* Make sure we visit node->loc by ensuring we cval is
2878                    visited too.  */
2879                 VALUE_RECURSED_INTO (cval) = true;
2880               }
2881             else if (!VALUE_RECURSED_INTO (node->loc))
2882               /* If we have no need to "recurse" into this node, it's
2883                  already "canonicalized", so drop the link to the old
2884                  parent.  */
2885               clobber_variable_part (set, cval, ndv, 0, NULL);
2886           }
2887         else if (GET_CODE (node->loc) == REG)
2888           {
2889             attrs list = set->regs[REGNO (node->loc)], *listp;
2890
2891             /* Change an existing attribute referring to dv so that it
2892                refers to cdv, removing any duplicate this might
2893                introduce, and checking that no previous duplicates
2894                existed, all in a single pass.  */
2895
2896             while (list)
2897               {
2898                 if (list->offset == 0
2899                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2900                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2901                   break;
2902
2903                 list = list->next;
2904               }
2905
2906             gcc_assert (list);
2907             if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2908               {
2909                 list->dv = cdv;
2910                 for (listp = &list->next; (list = *listp); listp = &list->next)
2911                   {
2912                     if (list->offset)
2913                       continue;
2914
2915                     if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2916                       {
2917                         *listp = list->next;
2918                         pool_free (attrs_pool, list);
2919                         list = *listp;
2920                         break;
2921                       }
2922
2923                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (dv));
2924                   }
2925               }
2926             else if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2927               {
2928                 for (listp = &list->next; (list = *listp); listp = &list->next)
2929                   {
2930                     if (list->offset)
2931                       continue;
2932
2933                     if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2934                       {
2935                         *listp = list->next;
2936                         pool_free (attrs_pool, list);
2937                         list = *listp;
2938                         break;
2939                       }
2940
2941                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (cdv));
2942                   }
2943               }
2944             else
2945               gcc_unreachable ();
2946
2947 #if ENABLE_CHECKING
2948             while (list)
2949               {
2950                 if (list->offset == 0
2951                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2952                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2953                   gcc_unreachable ();
2954
2955                 list = list->next;
2956               }
2957 #endif
2958           }
2959       }
2960
2961   if (val)
2962     cslot = set_slot_part (set, val, cslot, cdv, 0,
2963                            VAR_INIT_STATUS_INITIALIZED, NULL_RTX);
2964
2965   slot = clobber_slot_part (set, cval, slot, 0, NULL);
2966
2967   /* Variable may have been unshared.  */
2968   var = (variable)*slot;
2969   gcc_assert (var->n_var_parts && var->var_part[0].loc_chain->loc == cval
2970               && var->var_part[0].loc_chain->next == NULL);
2971
2972   if (VALUE_RECURSED_INTO (cval))
2973     goto restart_with_cval;
2974
2975   return 1;
2976 }
2977
2978 /* Combine variable or value in *S1SLOT (in DSM->cur) with the
2979    corresponding entry in DSM->src.  Multi-part variables are combined
2980    with variable_union, whereas onepart dvs are combined with
2981    intersection.  */
2982
2983 static int
2984 variable_merge_over_cur (void **s1slot, void *data)
2985 {
2986   struct dfset_merge *dsm = (struct dfset_merge *)data;
2987   dataflow_set *dst = dsm->dst;
2988   void **dstslot;
2989   variable s1var = (variable) *s1slot;
2990   variable s2var, dvar = NULL;
2991   decl_or_value dv = s1var->dv;
2992   bool onepart = dv_onepart_p (dv);
2993   rtx val;
2994   hashval_t dvhash;
2995   location_chain node, *nodep;
2996
2997   /* If the incoming onepart variable has an empty location list, then
2998      the intersection will be just as empty.  For other variables,
2999      it's always union.  */
3000   gcc_assert (s1var->n_var_parts);
3001   gcc_assert (s1var->var_part[0].loc_chain);
3002
3003   if (!onepart)
3004     return variable_union (s1slot, dst);
3005
3006   gcc_assert (s1var->n_var_parts == 1);
3007   gcc_assert (s1var->var_part[0].offset == 0);
3008
3009   dvhash = dv_htab_hash (dv);
3010   if (dv_is_value_p (dv))
3011     val = dv_as_value (dv);
3012   else
3013     val = NULL;
3014
3015   s2var = shared_hash_find_1 (dsm->src->vars, dv, dvhash);
3016   if (!s2var)
3017     {
3018       dst_can_be_shared = false;
3019       return 1;
3020     }
3021
3022   dsm->src_onepart_cnt--;
3023   gcc_assert (s2var->var_part[0].loc_chain);
3024   gcc_assert (s2var->n_var_parts == 1);
3025   gcc_assert (s2var->var_part[0].offset == 0);
3026
3027   dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3028   if (dstslot)
3029     {
3030       dvar = (variable)*dstslot;
3031       gcc_assert (dvar->refcount == 1);
3032       gcc_assert (dvar->n_var_parts == 1);
3033       gcc_assert (dvar->var_part[0].offset == 0);
3034       nodep = &dvar->var_part[0].loc_chain;
3035     }
3036   else
3037     {
3038       nodep = &node;
3039       node = NULL;
3040     }
3041
3042   if (!dstslot && !onepart_variable_different_p (s1var, s2var))
3043     {
3044       dstslot = shared_hash_find_slot_unshare_1 (&dst->vars, dv,
3045                                                  dvhash, INSERT);
3046       *dstslot = dvar = s2var;
3047       dvar->refcount++;
3048     }
3049   else
3050     {
3051       dst_can_be_shared = false;
3052
3053       intersect_loc_chains (val, nodep, dsm,
3054                             s1var->var_part[0].loc_chain, s2var);
3055
3056       if (!dstslot)
3057         {
3058           if (node)
3059             {
3060               dvar = (variable) pool_alloc (dv_pool (dv));
3061               dvar->dv = dv;
3062               dvar->refcount = 1;
3063               dvar->n_var_parts = 1;
3064               dvar->var_part[0].offset = 0;
3065               dvar->var_part[0].loc_chain = node;
3066               dvar->var_part[0].cur_loc = node->loc;
3067
3068               dstslot
3069                 = shared_hash_find_slot_unshare_1 (&dst->vars, dv, dvhash,
3070                                                    INSERT);
3071               gcc_assert (!*dstslot);
3072               *dstslot = dvar;
3073             }
3074           else
3075             return 1;
3076         }
3077     }
3078
3079   nodep = &dvar->var_part[0].loc_chain;
3080   while ((node = *nodep))
3081     {
3082       location_chain *nextp = &node->next;
3083
3084       if (GET_CODE (node->loc) == REG)
3085         {
3086           attrs list;
3087
3088           for (list = dst->regs[REGNO (node->loc)]; list; list = list->next)
3089             if (GET_MODE (node->loc) == GET_MODE (list->loc)
3090                 && dv_is_value_p (list->dv))
3091               break;
3092
3093           if (!list)
3094             attrs_list_insert (&dst->regs[REGNO (node->loc)],
3095                                dv, 0, node->loc);
3096           /* If this value became canonical for another value that had
3097              this register, we want to leave it alone.  */
3098           else if (dv_as_value (list->dv) != val)
3099             {
3100               dstslot = set_slot_part (dst, dv_as_value (list->dv),
3101                                        dstslot, dv, 0,
3102                                        node->init, NULL_RTX);
3103               dstslot = delete_slot_part (dst, node->loc, dstslot, 0);
3104
3105               /* Since nextp points into the removed node, we can't
3106                  use it.  The pointer to the next node moved to nodep.
3107                  However, if the variable we're walking is unshared
3108                  during our walk, we'll keep walking the location list
3109                  of the previously-shared variable, in which case the
3110                  node won't have been removed, and we'll want to skip
3111                  it.  That's why we test *nodep here.  */
3112               if (*nodep != node)
3113                 nextp = nodep;
3114             }
3115         }
3116       else
3117         /* Canonicalization puts registers first, so we don't have to
3118            walk it all.  */
3119         break;
3120       nodep = nextp;
3121     }
3122
3123   if (dvar != (variable)*dstslot)
3124     dvar = (variable)*dstslot;
3125   nodep = &dvar->var_part[0].loc_chain;
3126
3127   if (val)
3128     {
3129       /* Mark all referenced nodes for canonicalization, and make sure
3130          we have mutual equivalence links.  */
3131       VALUE_RECURSED_INTO (val) = true;
3132       for (node = *nodep; node; node = node->next)
3133         if (GET_CODE (node->loc) == VALUE)
3134           {
3135             VALUE_RECURSED_INTO (node->loc) = true;
3136             set_variable_part (dst, val, dv_from_value (node->loc), 0,
3137                                node->init, NULL, INSERT);
3138           }
3139
3140       dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3141       gcc_assert (*dstslot == dvar);
3142       canonicalize_values_star (dstslot, dst);
3143 #ifdef ENABLE_CHECKING
3144       gcc_assert (dstslot
3145                   == shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash));
3146 #endif
3147       dvar = (variable)*dstslot;
3148     }
3149   else
3150     {
3151       bool has_value = false, has_other = false;
3152
3153       /* If we have one value and anything else, we're going to
3154          canonicalize this, so make sure all values have an entry in
3155          the table and are marked for canonicalization.  */
3156       for (node = *nodep; node; node = node->next)
3157         {
3158           if (GET_CODE (node->loc) == VALUE)
3159             {
3160               /* If this was marked during register canonicalization,
3161                  we know we have to canonicalize values.  */
3162               if (has_value)
3163                 has_other = true;
3164               has_value = true;
3165               if (has_other)
3166                 break;
3167             }
3168           else
3169             {
3170               has_other = true;
3171               if (has_value)
3172                 break;
3173             }
3174         }
3175
3176       if (has_value && has_other)
3177         {
3178           for (node = *nodep; node; node = node->next)
3179             {
3180               if (GET_CODE (node->loc) == VALUE)
3181                 {
3182                   decl_or_value dv = dv_from_value (node->loc);
3183                   void **slot = NULL;
3184
3185                   if (shared_hash_shared (dst->vars))
3186                     slot = shared_hash_find_slot_noinsert (dst->vars, dv);
3187                   if (!slot)
3188                     slot = shared_hash_find_slot_unshare (&dst->vars, dv,
3189                                                           INSERT);
3190                   if (!*slot)
3191                     {
3192                       variable var = (variable) pool_alloc (dv_pool (dv));
3193                       var->dv = dv;
3194                       var->refcount = 1;
3195                       var->n_var_parts = 1;
3196                       var->var_part[0].offset = 0;
3197                       var->var_part[0].loc_chain = NULL;
3198                       var->var_part[0].cur_loc = NULL;
3199                       *slot = var;
3200                     }
3201
3202                   VALUE_RECURSED_INTO (node->loc) = true;
3203                 }
3204             }
3205
3206           dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3207           gcc_assert (*dstslot == dvar);
3208           canonicalize_values_star (dstslot, dst);
3209 #ifdef ENABLE_CHECKING
3210           gcc_assert (dstslot
3211                       == shared_hash_find_slot_noinsert_1 (dst->vars,
3212                                                            dv, dvhash));
3213 #endif
3214           dvar = (variable)*dstslot;
3215         }
3216     }
3217
3218   if (!onepart_variable_different_p (dvar, s2var))
3219     {
3220       variable_htab_free (dvar);
3221       *dstslot = dvar = s2var;
3222       dvar->refcount++;
3223     }
3224   else if (s2var != s1var && !onepart_variable_different_p (dvar, s1var))
3225     {
3226       variable_htab_free (dvar);
3227       *dstslot = dvar = s1var;
3228       dvar->refcount++;
3229       dst_can_be_shared = false;
3230     }
3231   else
3232     {
3233       if (dvar->refcount == 1)
3234         dvar->var_part[0].cur_loc = dvar->var_part[0].loc_chain->loc;
3235       dst_can_be_shared = false;
3236     }
3237
3238   return 1;
3239 }
3240
3241 /* Combine variable in *S1SLOT (in DSM->src) with the corresponding
3242    entry in DSM->src.  Only multi-part variables are combined, using
3243    variable_union.  onepart dvs were already combined with
3244    intersection in variable_merge_over_cur().  */
3245
3246 static int
3247 variable_merge_over_src (void **s2slot, void *data)
3248 {
3249   struct dfset_merge *dsm = (struct dfset_merge *)data;
3250   dataflow_set *dst = dsm->dst;
3251   variable s2var = (variable) *s2slot;
3252   decl_or_value dv = s2var->dv;
3253   bool onepart = dv_onepart_p (dv);
3254
3255   if (!onepart)
3256     {
3257       void **dstp = shared_hash_find_slot (dst->vars, dv);
3258       *dstp = s2var;
3259       s2var->refcount++;
3260       return variable_canonicalize (dstp, dst);
3261     }
3262
3263   dsm->src_onepart_cnt++;
3264   return 1;
3265 }
3266
3267 /* Combine dataflow set information from SRC into DST, using PDST
3268    to carry over information across passes.  */
3269
3270 static void
3271 dataflow_set_merge (dataflow_set *dst, dataflow_set *src)
3272 {
3273   dataflow_set src2 = *dst;
3274   struct dfset_merge dsm;
3275   int i;
3276   size_t src_elems, dst_elems;
3277
3278   src_elems = htab_elements (shared_hash_htab (src->vars));
3279   dst_elems = htab_elements (shared_hash_htab (src2.vars));
3280   dataflow_set_init (dst);
3281   dst->stack_adjust = src2.stack_adjust;
3282   shared_hash_destroy (dst->vars);
3283   dst->vars = (shared_hash) pool_alloc (shared_hash_pool);
3284   dst->vars->refcount = 1;
3285   dst->vars->htab
3286     = htab_create (MAX (src_elems, dst_elems), variable_htab_hash,
3287                    variable_htab_eq, variable_htab_free);
3288
3289   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3290     attrs_list_mpdv_union (&dst->regs[i], src->regs[i], src2.regs[i]);
3291
3292   dsm.dst = dst;
3293   dsm.src = &src2;
3294   dsm.cur = src;
3295   dsm.src_onepart_cnt = 0;
3296
3297   htab_traverse (shared_hash_htab (dsm.src->vars), variable_merge_over_src,
3298                  &dsm);
3299   htab_traverse (shared_hash_htab (dsm.cur->vars), variable_merge_over_cur,
3300                  &dsm);
3301
3302   if (dsm.src_onepart_cnt)
3303     dst_can_be_shared = false;
3304
3305   dataflow_set_destroy (&src2);
3306 }
3307
3308 /* Mark register equivalences.  */
3309
3310 static void
3311 dataflow_set_equiv_regs (dataflow_set *set)
3312 {
3313   int i;
3314   attrs list, *listp;
3315
3316   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3317     {
3318       rtx canon[NUM_MACHINE_MODES];
3319
3320       memset (canon, 0, sizeof (canon));
3321
3322       for (list = set->regs[i]; list; list = list->next)
3323         if (list->offset == 0 && dv_is_value_p (list->dv))
3324           {
3325             rtx val = dv_as_value (list->dv);
3326             rtx *cvalp = &canon[(int)GET_MODE (val)];
3327             rtx cval = *cvalp;
3328
3329             if (canon_value_cmp (val, cval))
3330               *cvalp = val;
3331           }
3332
3333       for (list = set->regs[i]; list; list = list->next)
3334         if (list->offset == 0 && dv_onepart_p (list->dv))
3335           {
3336             rtx cval = canon[(int)GET_MODE (list->loc)];
3337
3338             if (!cval)
3339               continue;
3340
3341             if (dv_is_value_p (list->dv))
3342               {
3343                 rtx val = dv_as_value (list->dv);
3344
3345                 if (val == cval)
3346                   continue;
3347
3348                 VALUE_RECURSED_INTO (val) = true;
3349                 set_variable_part (set, val, dv_from_value (cval), 0,
3350                                    VAR_INIT_STATUS_INITIALIZED,
3351                                    NULL, NO_INSERT);
3352               }
3353
3354             VALUE_RECURSED_INTO (cval) = true;
3355             set_variable_part (set, cval, list->dv, 0,
3356                                VAR_INIT_STATUS_INITIALIZED, NULL, NO_INSERT);
3357           }
3358
3359       for (listp = &set->regs[i]; (list = *listp);
3360            listp = list ? &list->next : listp)
3361         if (list->offset == 0 && dv_onepart_p (list->dv))
3362           {
3363             rtx cval = canon[(int)GET_MODE (list->loc)];
3364             void **slot;
3365
3366             if (!cval)
3367               continue;
3368
3369             if (dv_is_value_p (list->dv))
3370               {
3371                 rtx val = dv_as_value (list->dv);
3372                 if (!VALUE_RECURSED_INTO (val))
3373                   continue;
3374               }
3375
3376             slot = shared_hash_find_slot_noinsert (set->vars, list->dv);
3377             canonicalize_values_star (slot, set);
3378             if (*listp != list)
3379               list = NULL;
3380           }
3381     }
3382 }
3383
3384 /* Remove any redundant values in the location list of VAR, which must
3385    be unshared and 1-part.  */
3386
3387 static void
3388 remove_duplicate_values (variable var)
3389 {
3390   location_chain node, *nodep;
3391
3392   gcc_assert (dv_onepart_p (var->dv));
3393   gcc_assert (var->n_var_parts == 1);
3394   gcc_assert (var->refcount == 1);
3395
3396   for (nodep = &var->var_part[0].loc_chain; (node = *nodep); )
3397     {
3398       if (GET_CODE (node->loc) == VALUE)
3399         {
3400           if (VALUE_RECURSED_INTO (node->loc))
3401             {
3402               /* Remove duplicate value node.  */
3403               *nodep = node->next;
3404               pool_free (loc_chain_pool, node);
3405               continue;
3406             }
3407           else
3408             VALUE_RECURSED_INTO (node->loc) = true;
3409         }
3410       nodep = &node->next;
3411     }
3412
3413   for (node = var->var_part[0].loc_chain; node; node = node->next)
3414     if (GET_CODE (node->loc) == VALUE)
3415       {
3416         gcc_assert (VALUE_RECURSED_INTO (node->loc));
3417         VALUE_RECURSED_INTO (node->loc) = false;
3418       }
3419 }
3420
3421
3422 /* Hash table iteration argument passed to variable_post_merge.  */
3423 struct dfset_post_merge
3424 {
3425   /* The new input set for the current block.  */
3426   dataflow_set *set;
3427   /* Pointer to the permanent input set for the current block, or
3428      NULL.  */
3429   dataflow_set **permp;
3430 };
3431
3432 /* Create values for incoming expressions associated with one-part
3433    variables that don't have value numbers for them.  */
3434
3435 static int
3436 variable_post_merge_new_vals (void **slot, void *info)
3437 {
3438   struct dfset_post_merge *dfpm = (struct dfset_post_merge *)info;
3439   dataflow_set *set = dfpm->set;
3440   variable var = (variable)*slot;
3441   location_chain node;
3442
3443   if (!dv_onepart_p (var->dv) || !var->n_var_parts)
3444     return 1;
3445
3446   gcc_assert (var->n_var_parts == 1);
3447
3448   if (dv_is_decl_p (var->dv))
3449     {
3450       bool check_dupes = false;
3451
3452     restart:
3453       for (node = var->var_part[0].loc_chain; node; node = node->next)
3454         {
3455           if (GET_CODE (node->loc) == VALUE)
3456             gcc_assert (!VALUE_RECURSED_INTO (node->loc));
3457           else if (GET_CODE (node->loc) == REG)
3458             {
3459               attrs att, *attp, *curp = NULL;
3460
3461               if (var->refcount != 1)
3462                 {
3463                   slot = unshare_variable (set, slot, var,
3464                                            VAR_INIT_STATUS_INITIALIZED);
3465                   var = (variable)*slot;
3466                   goto restart;
3467                 }
3468
3469               for (attp = &set->regs[REGNO (node->loc)]; (att = *attp);
3470                    attp = &att->next)
3471                 if (att->offset == 0
3472                     && GET_MODE (att->loc) == GET_MODE (node->loc))
3473                   {
3474                     if (dv_is_value_p (att->dv))
3475                       {
3476                         rtx cval = dv_as_value (att->dv);
3477                         node->loc = cval;
3478                         check_dupes = true;
3479                         break;
3480                       }
3481                     else if (dv_as_opaque (att->dv) == dv_as_opaque (var->dv))
3482                       curp = attp;
3483                   }
3484
3485               if (!curp)
3486                 {
3487                   curp = attp;
3488                   while (*curp)
3489                     if ((*curp)->offset == 0
3490                         && GET_MODE ((*curp)->loc) == GET_MODE (node->loc)
3491                         && dv_as_opaque ((*curp)->dv) == dv_as_opaque (var->dv))
3492                       break;
3493                     else
3494                       curp = &(*curp)->next;
3495                   gcc_assert (*curp);
3496                 }
3497
3498               if (!att)
3499                 {
3500                   decl_or_value cdv;
3501                   rtx cval;
3502
3503                   if (!*dfpm->permp)
3504                     {
3505                       *dfpm->permp = XNEW (dataflow_set);
3506                       dataflow_set_init (*dfpm->permp);
3507                     }
3508
3509                   for (att = (*dfpm->permp)->regs[REGNO (node->loc)];
3510                        att; att = att->next)
3511                     if (GET_MODE (att->loc) == GET_MODE (node->loc))
3512                       {
3513                         gcc_assert (att->offset == 0);
3514                         gcc_assert (dv_is_value_p (att->dv));
3515                         val_reset (set, att->dv);
3516                         break;
3517                       }
3518
3519                   if (att)
3520                     {
3521                       cdv = att->dv;
3522                       cval = dv_as_value (cdv);
3523                     }
3524                   else
3525                     {
3526                       /* Create a unique value to hold this register,
3527                          that ought to be found and reused in
3528                          subsequent rounds.  */
3529                       cselib_val *v;
3530