OSDN Git Service

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