OSDN Git Service

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