OSDN Git Service

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