OSDN Git Service

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