gcc/var-tracking.c

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