gcc/var-tracking.c

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