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