OSDN Git Service

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