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))
4176     return 0;
4177
4178   /* When the EXPR is a DECL for alias of some variable (see example)
4179      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
4180      DECL_RTL contains SYMBOL_REF.
4181
4182      Example:
4183      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
4184      char **_dl_argv;
4185   */
4186   if (decl_rtl && MEM_P (decl_rtl)
4187       && contains_symbol_ref (XEXP (decl_rtl, 0)))
4188     return 0;
4189
4190   /* If RTX is a memory it should not be very large (because it would be
4191      an array or struct).  */
4192   if (decl_rtl && MEM_P (decl_rtl))
4193     {
4194       /* Do not track structures and arrays.  */
4195       if (GET_MODE (decl_rtl) == BLKmode
4196           || AGGREGATE_TYPE_P (TREE_TYPE (realdecl)))
4197         return 0;
4198       if (MEM_SIZE (decl_rtl)
4199           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
4200         return 0;
4201     }
4202
4203   DECL_CHANGED (expr) = 0;
4204   DECL_CHANGED (realdecl) = 0;
4205   return 1;
4206 }
4207
4208 /* Determine whether a given LOC refers to the same variable part as
4209    EXPR+OFFSET.  */
4210
4211 static bool
4212 same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset)
4213 {
4214   tree expr2;
4215   HOST_WIDE_INT offset2;
4216
4217   if (! DECL_P (expr))
4218     return false;
4219
4220   if (REG_P (loc))
4221     {
4222       expr2 = REG_EXPR (loc);
4223       offset2 = REG_OFFSET (loc);
4224     }
4225   else if (MEM_P (loc))
4226     {
4227       expr2 = MEM_EXPR (loc);
4228       offset2 = INT_MEM_OFFSET (loc);
4229     }
4230   else
4231     return false;
4232
4233   if (! expr2 || ! DECL_P (expr2))
4234     return false;
4235
4236   expr = var_debug_decl (expr);
4237   expr2 = var_debug_decl (expr2);
4238
4239   return (expr == expr2 && offset == offset2);
4240 }
4241
4242 /* LOC is a REG or MEM that we would like to track if possible.
4243    If EXPR is null, we don't know what expression LOC refers to,
4244    otherwise it refers to EXPR + OFFSET.  STORE_REG_P is true if
4245    LOC is an lvalue register.
4246
4247    Return true if EXPR is nonnull and if LOC, or some lowpart of it,
4248    is something we can track.  When returning true, store the mode of
4249    the lowpart we can track in *MODE_OUT (if nonnull) and its offset
4250    from EXPR in *OFFSET_OUT (if nonnull).  */
4251
4252 static bool
4253 track_loc_p (rtx loc, tree expr, HOST_WIDE_INT offset, bool store_reg_p,
4254              enum machine_mode *mode_out, HOST_WIDE_INT *offset_out)
4255 {
4256   enum machine_mode mode;
4257
4258   if (expr == NULL || !track_expr_p (expr, true))
4259     return false;
4260
4261   /* If REG was a paradoxical subreg, its REG_ATTRS will describe the
4262      whole subreg, but only the old inner part is really relevant.  */
4263   mode = GET_MODE (loc);
4264   if (REG_P (loc) && !HARD_REGISTER_NUM_P (ORIGINAL_REGNO (loc)))
4265     {
4266       enum machine_mode pseudo_mode;
4267
4268       pseudo_mode = PSEUDO_REGNO_MODE (ORIGINAL_REGNO (loc));
4269       if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (pseudo_mode))
4270         {
4271           offset += byte_lowpart_offset (pseudo_mode, mode);
4272           mode = pseudo_mode;
4273         }
4274     }
4275
4276   /* If LOC is a paradoxical lowpart of EXPR, refer to EXPR itself.
4277      Do the same if we are storing to a register and EXPR occupies
4278      the whole of register LOC; in that case, the whole of EXPR is
4279      being changed.  We exclude complex modes from the second case
4280      because the real and imaginary parts are represented as separate
4281      pseudo registers, even if the whole complex value fits into one
4282      hard register.  */
4283   if ((GET_MODE_SIZE (mode) > GET_MODE_SIZE (DECL_MODE (expr))
4284        || (store_reg_p
4285            && !COMPLEX_MODE_P (DECL_MODE (expr))
4286            && hard_regno_nregs[REGNO (loc)][DECL_MODE (expr)] == 1))
4287       && offset + byte_lowpart_offset (DECL_MODE (expr), mode) == 0)
4288     {
4289       mode = DECL_MODE (expr);
4290       offset = 0;
4291     }
4292
4293   if (offset < 0 || offset >= MAX_VAR_PARTS)
4294     return false;
4295
4296   if (mode_out)
4297     *mode_out = mode;
4298   if (offset_out)
4299     *offset_out = offset;
4300   return true;
4301 }
4302
4303 /* Return the MODE lowpart of LOC, or null if LOC is not something we
4304    want to track.  When returning nonnull, make sure that the attributes
4305    on the returned value are updated.  */
4306
4307 static rtx
4308 var_lowpart (enum machine_mode mode, rtx loc)
4309 {
4310   unsigned int offset, reg_offset, regno;
4311
4312   if (!REG_P (loc) && !MEM_P (loc))
4313     return NULL;
4314
4315   if (GET_MODE (loc) == mode)
4316     return loc;
4317
4318   offset = byte_lowpart_offset (mode, GET_MODE (loc));
4319
4320   if (MEM_P (loc))
4321     return adjust_address_nv (loc, mode, offset);
4322
4323   reg_offset = subreg_lowpart_offset (mode, GET_MODE (loc));
4324   regno = REGNO (loc) + subreg_regno_offset (REGNO (loc), GET_MODE (loc),
4325                                              reg_offset, mode);
4326   return gen_rtx_REG_offset (loc, mode, regno, offset);
4327 }
4328
4329 /* Carry information about uses and stores while walking rtx.  */
4330
4331 struct count_use_info
4332 {
4333   /* The insn where the RTX is.  */
4334   rtx insn;
4335
4336   /* The basic block where insn is.  */
4337   basic_block bb;
4338
4339   /* The array of n_sets sets in the insn, as determined by cselib.  */
4340   struct cselib_set *sets;
4341   int n_sets;
4342
4343   /* True if we're counting stores, false otherwise.  */
4344   bool store_p;
4345 };
4346
4347 /* Find a VALUE corresponding to X.   */
4348
4349 static inline cselib_val *
4350 find_use_val (rtx x, enum machine_mode mode, struct count_use_info *cui)
4351 {
4352   int i;
4353
4354   if (cui->sets)
4355     {
4356       /* This is called after uses are set up and before stores are
4357          processed bycselib, so it's safe to look up srcs, but not
4358          dsts.  So we look up expressions that appear in srcs or in
4359          dest expressions, but we search the sets array for dests of
4360          stores.  */
4361       if (cui->store_p)
4362         {
4363           for (i = 0; i < cui->n_sets; i++)
4364             if (cui->sets[i].dest == x)
4365               return cui->sets[i].src_elt;
4366         }
4367       else
4368         return cselib_lookup (x, mode, 0);
4369     }
4370
4371   return NULL;
4372 }
4373
4374 /* Replace all registers and addresses in an expression with VALUE
4375    expressions that map back to them, unless the expression is a
4376    register.  If no mapping is or can be performed, returns NULL.  */
4377
4378 static rtx
4379 replace_expr_with_values (rtx loc)
4380 {
4381   if (REG_P (loc))
4382     return NULL;
4383   else if (MEM_P (loc))
4384     {
4385       enum machine_mode address_mode
4386         = targetm.addr_space.address_mode (MEM_ADDR_SPACE (loc));
4387       cselib_val *addr = cselib_lookup (XEXP (loc, 0), address_mode, 0);
4388       if (addr)
4389         return replace_equiv_address_nv (loc, addr->val_rtx);
4390       else
4391         return NULL;
4392     }
4393   else
4394     return cselib_subst_to_values (loc);
4395 }
4396
4397 /* Determine what kind of micro operation to choose for a USE.  Return
4398    MO_CLOBBER if no micro operation is to be generated.  */
4399
4400 static enum micro_operation_type
4401 use_type (rtx loc, struct count_use_info *cui, enum machine_mode *modep)
4402 {
4403   tree expr;
4404
4405   if (cui && cui->sets)
4406     {
4407       if (GET_CODE (loc) == VAR_LOCATION)
4408         {
4409           if (track_expr_p (PAT_VAR_LOCATION_DECL (loc), false))
4410             {
4411               rtx ploc = PAT_VAR_LOCATION_LOC (loc);
4412               cselib_val *val = cselib_lookup (ploc, GET_MODE (loc), 1);
4413
4414               /* ??? flag_float_store and volatile mems are never
4415                  given values, but we could in theory use them for
4416                  locations.  */
4417               gcc_assert (val || 1);
4418               return MO_VAL_LOC;
4419             }
4420           else
4421             return MO_CLOBBER;
4422         }
4423
4424       if (REG_P (loc) || MEM_P (loc))
4425         {
4426           if (modep)
4427             *modep = GET_MODE (loc);
4428           if (cui->store_p)
4429             {
4430               if (REG_P (loc)
4431                   || (find_use_val (loc, GET_MODE (loc), cui)
4432                       && cselib_lookup (XEXP (loc, 0), GET_MODE (loc), 0)))
4433                 return MO_VAL_SET;
4434             }
4435           else
4436             {
4437               cselib_val *val = find_use_val (loc, GET_MODE (loc), cui);
4438
4439               if (val && !cselib_preserved_value_p (val))
4440                 return MO_VAL_USE;
4441             }
4442         }
4443     }
4444
4445   if (REG_P (loc))
4446     {
4447       gcc_assert (REGNO (loc) < FIRST_PSEUDO_REGISTER);
4448
4449       expr = REG_EXPR (loc);
4450
4451       if (!expr)
4452         return MO_USE_NO_VAR;
4453       else if (target_for_debug_bind (var_debug_decl (expr)))
4454         return MO_CLOBBER;
4455       else if (track_loc_p (loc, expr, REG_OFFSET (loc),
4456                             false, modep, NULL))
4457         return MO_USE;
4458       else
4459         return MO_USE_NO_VAR;
4460     }
4461   else if (MEM_P (loc))
4462     {
4463       expr = MEM_EXPR (loc);
4464
4465       if (!expr)
4466         return MO_CLOBBER;
4467       else if (target_for_debug_bind (var_debug_decl (expr)))
4468         return MO_CLOBBER;
4469       else if (track_loc_p (loc, expr, INT_MEM_OFFSET (loc),
4470                             false, modep, NULL))
4471         return MO_USE;
4472       else
4473         return MO_CLOBBER;
4474     }
4475
4476   return MO_CLOBBER;
4477 }
4478
4479 /* Log to OUT information about micro-operation MOPT involving X in
4480    INSN of BB.  */
4481
4482 static inline void
4483 log_op_type (rtx x, basic_block bb, rtx insn,
4484              enum micro_operation_type mopt, FILE *out)
4485 {
4486   fprintf (out, "bb %i op %i insn %i %s ",
4487            bb->index, VEC_length (micro_operation, VTI (bb)->mos),
4488            INSN_UID (insn), micro_operation_type_name[mopt]);
4489   print_inline_rtx (out, x, 2);
4490   fputc ('\n', out);
4491 }
4492
4493 /* Adjust sets if needed.  Currently this optimizes read-only MEM loads
4494    if REG_EQUAL/REG_EQUIV note is present.  */
4495
4496 static void
4497 adjust_sets (rtx insn, struct cselib_set *sets, int n_sets)
4498 {
4499   if (n_sets == 1 && MEM_P (sets[0].src) && MEM_READONLY_P (sets[0].src))
4500     {
4501       /* For read-only MEMs containing some constant, prefer those
4502          constants.  */
4503       rtx note = find_reg_equal_equiv_note (insn), src;
4504
4505       if (note && CONSTANT_P (XEXP (note, 0)))
4506         {
4507           sets[0].src = src = XEXP (note, 0);
4508           if (GET_CODE (PATTERN (insn)) == COND_EXEC)
4509             src = gen_rtx_IF_THEN_ELSE (GET_MODE (sets[0].dest),
4510                                         COND_EXEC_TEST (PATTERN (insn)),
4511                                         src, sets[0].dest);
4512           sets[0].src_elt = cselib_lookup (src, GET_MODE (sets[0].dest), 1);
4513         }
4514     }
4515 }
4516
4517 /* Tell whether the CONCAT used to holds a VALUE and its location
4518    needs value resolution, i.e., an attempt of mapping the location
4519    back to other incoming values.  */
4520 #define VAL_NEEDS_RESOLUTION(x) \
4521   (RTL_FLAG_CHECK1 ("VAL_NEEDS_RESOLUTION", (x), CONCAT)->volatil)
4522 /* Whether the location in the CONCAT is a tracked expression, that
4523    should also be handled like a MO_USE.  */
4524 #define VAL_HOLDS_TRACK_EXPR(x) \
4525   (RTL_FLAG_CHECK1 ("VAL_HOLDS_TRACK_EXPR", (x), CONCAT)->used)
4526 /* Whether the location in the CONCAT should be handled like a MO_COPY
4527    as well.  */
4528 #define VAL_EXPR_IS_COPIED(x) \
4529   (RTL_FLAG_CHECK1 ("VAL_EXPR_IS_COPIED", (x), CONCAT)->jump)
4530 /* Whether the location in the CONCAT should be handled like a
4531    MO_CLOBBER as well.  */
4532 #define VAL_EXPR_IS_CLOBBERED(x) \
4533   (RTL_FLAG_CHECK1 ("VAL_EXPR_IS_CLOBBERED", (x), CONCAT)->unchanging)
4534 /* Whether the location is a CONCAT of the MO_VAL_SET expression and
4535    a reverse operation that should be handled afterwards.  */
4536 #define VAL_EXPR_HAS_REVERSE(x) \
4537   (RTL_FLAG_CHECK1 ("VAL_EXPR_HAS_REVERSE", (x), CONCAT)->return_val)
4538
4539 /* All preserved VALUEs.  */
4540 static VEC (rtx, heap) *preserved_values;
4541
4542 /* Ensure VAL is preserved and remember it in a vector for vt_emit_notes.  */
4543
4544 static void
4545 preserve_value (cselib_val *val)
4546 {
4547   cselib_preserve_value (val);
4548   VEC_safe_push (rtx, heap, preserved_values, val->val_rtx);
4549 }
4550
4551 /* Add uses (register and memory references) LOC which will be tracked
4552    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
4553
4554 static int
4555 add_uses (rtx *ploc, void *data)
4556 {
4557   rtx loc = *ploc;
4558   enum machine_mode mode = VOIDmode;
4559   struct count_use_info *cui = (struct count_use_info *)data;
4560   enum micro_operation_type type = use_type (loc, cui, &mode);
4561
4562   if (type != MO_CLOBBER)
4563     {
4564       basic_block bb = cui->bb;
4565       micro_operation mo;
4566
4567       mo.type = type;
4568       mo.u.loc = type == MO_USE ? var_lowpart (mode, loc) : loc;
4569       mo.insn = cui->insn;
4570
4571       if (type == MO_VAL_LOC)
4572         {
4573           rtx oloc = loc;
4574           rtx vloc = PAT_VAR_LOCATION_LOC (oloc);
4575           cselib_val *val;
4576
4577           gcc_assert (cui->sets);
4578
4579           if (MEM_P (vloc)
4580               && !REG_P (XEXP (vloc, 0)) && !MEM_P (XEXP (vloc, 0)))
4581             {
4582               rtx mloc = vloc;
4583               enum machine_mode address_mode
4584                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4585               cselib_val *val
4586                 = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4587
4588               if (val && !cselib_preserved_value_p (val))
4589                 {
4590                   micro_operation moa;
4591                   preserve_value (val);
4592                   mloc = cselib_subst_to_values (XEXP (mloc, 0));
4593                   moa.type = MO_VAL_USE;
4594                   moa.insn = cui->insn;
4595                   moa.u.loc = gen_rtx_CONCAT (address_mode,
4596                                               val->val_rtx, mloc);
4597                   if (dump_file && (dump_flags & TDF_DETAILS))
4598                     log_op_type (moa.u.loc, cui->bb, cui->insn,
4599                                  moa.type, dump_file);
4600                   VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &moa);
4601                 }
4602             }
4603
4604           if (!VAR_LOC_UNKNOWN_P (vloc)
4605               && (val = find_use_val (vloc, GET_MODE (oloc), cui)))
4606             {
4607               enum machine_mode mode2;
4608               enum micro_operation_type type2;
4609               rtx nloc = replace_expr_with_values (vloc);
4610
4611               if (nloc)
4612                 {
4613                   oloc = shallow_copy_rtx (oloc);
4614                   PAT_VAR_LOCATION_LOC (oloc) = nloc;
4615                 }
4616
4617               oloc = gen_rtx_CONCAT (mode, val->val_rtx, oloc);
4618
4619               type2 = use_type (vloc, 0, &mode2);
4620
4621               gcc_assert (type2 == MO_USE || type2 == MO_USE_NO_VAR
4622                           || type2 == MO_CLOBBER);
4623
4624               if (type2 == MO_CLOBBER
4625                   && !cselib_preserved_value_p (val))
4626                 {
4627                   VAL_NEEDS_RESOLUTION (oloc) = 1;
4628                   preserve_value (val);
4629                 }
4630             }
4631           else if (!VAR_LOC_UNKNOWN_P (vloc))
4632             {
4633               oloc = shallow_copy_rtx (oloc);
4634               PAT_VAR_LOCATION_LOC (oloc) = gen_rtx_UNKNOWN_VAR_LOC ();
4635             }
4636
4637           mo.u.loc = oloc;
4638         }
4639       else if (type == MO_VAL_USE)
4640         {
4641           enum machine_mode mode2 = VOIDmode;
4642           enum micro_operation_type type2;
4643           cselib_val *val = find_use_val (loc, GET_MODE (loc), cui);
4644           rtx vloc, oloc = loc, nloc;
4645
4646           gcc_assert (cui->sets);
4647
4648           if (MEM_P (oloc)
4649               && !REG_P (XEXP (oloc, 0)) && !MEM_P (XEXP (oloc, 0)))
4650             {
4651               rtx mloc = oloc;
4652               enum machine_mode address_mode
4653                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4654               cselib_val *val
4655                 = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4656
4657               if (val && !cselib_preserved_value_p (val))
4658                 {
4659                   micro_operation moa;
4660                   preserve_value (val);
4661                   mloc = cselib_subst_to_values (XEXP (mloc, 0));
4662                   moa.type = MO_VAL_USE;
4663                   moa.insn = cui->insn;
4664                   moa.u.loc = gen_rtx_CONCAT (address_mode,
4665                                               val->val_rtx, mloc);
4666                   if (dump_file && (dump_flags & TDF_DETAILS))
4667                     log_op_type (moa.u.loc, cui->bb, cui->insn,
4668                                  moa.type, dump_file);
4669                   VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &moa);
4670                 }
4671             }
4672
4673           type2 = use_type (loc, 0, &mode2);
4674
4675           gcc_assert (type2 == MO_USE || type2 == MO_USE_NO_VAR
4676                       || type2 == MO_CLOBBER);
4677
4678           if (type2 == MO_USE)
4679             vloc = var_lowpart (mode2, loc);
4680           else
4681             vloc = oloc;
4682
4683           /* The loc of a MO_VAL_USE may have two forms:
4684
4685              (concat val src): val is at src, a value-based
4686              representation.
4687
4688              (concat (concat val use) src): same as above, with use as
4689              the MO_USE tracked value, if it differs from src.
4690
4691           */
4692
4693           nloc = replace_expr_with_values (loc);
4694           if (!nloc)
4695             nloc = oloc;
4696
4697           if (vloc != nloc)
4698             oloc = gen_rtx_CONCAT (mode2, val->val_rtx, vloc);
4699           else
4700             oloc = val->val_rtx;
4701
4702           mo.u.loc = gen_rtx_CONCAT (mode, oloc, nloc);
4703
4704           if (type2 == MO_USE)
4705             VAL_HOLDS_TRACK_EXPR (mo.u.loc) = 1;
4706           if (!cselib_preserved_value_p (val))
4707             {
4708               VAL_NEEDS_RESOLUTION (mo.u.loc) = 1;
4709               preserve_value (val);
4710             }
4711         }
4712       else
4713         gcc_assert (type == MO_USE || type == MO_USE_NO_VAR);
4714
4715       if (dump_file && (dump_flags & TDF_DETAILS))
4716         log_op_type (mo.u.loc, cui->bb, cui->insn, mo.type, dump_file);
4717       VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &mo);
4718     }
4719
4720   return 0;
4721 }
4722
4723 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
4724
4725 static void
4726 add_uses_1 (rtx *x, void *cui)
4727 {
4728   for_each_rtx (x, add_uses, cui);
4729 }
4730
4731 /* Attempt to reverse the EXPR operation in the debug info.  Say for
4732    reg1 = reg2 + 6 even when reg2 is no longer live we
4733    can express its value as VAL - 6.  */
4734
4735 static rtx
4736 reverse_op (rtx val, const_rtx expr)
4737 {
4738   rtx src, arg, ret;
4739   cselib_val *v;
4740   enum rtx_code code;
4741
4742   if (GET_CODE (expr) != SET)
4743     return NULL_RTX;
4744
4745   if (!REG_P (SET_DEST (expr)) || GET_MODE (val) != GET_MODE (SET_DEST (expr)))
4746     return NULL_RTX;
4747
4748   src = SET_SRC (expr);
4749   switch (GET_CODE (src))
4750     {
4751     case PLUS:
4752     case MINUS:
4753     case XOR:
4754     case NOT:
4755     case NEG:
4756     case SIGN_EXTEND:
4757     case ZERO_EXTEND:
4758       break;
4759     default:
4760       return NULL_RTX;
4761     }
4762
4763   if (!REG_P (XEXP (src, 0)) || !SCALAR_INT_MODE_P (GET_MODE (src)))
4764     return NULL_RTX;
4765
4766   v = cselib_lookup (XEXP (src, 0), GET_MODE (XEXP (src, 0)), 0);
4767   if (!v || !cselib_preserved_value_p (v))
4768     return NULL_RTX;
4769
4770   switch (GET_CODE (src))
4771     {
4772     case NOT:
4773     case NEG:
4774       if (GET_MODE (v->val_rtx) != GET_MODE (val))
4775         return NULL_RTX;
4776       ret = gen_rtx_fmt_e (GET_CODE (src), GET_MODE (val), val);
4777       break;
4778     case SIGN_EXTEND:
4779     case ZERO_EXTEND:
4780       ret = gen_lowpart_SUBREG (GET_MODE (v->val_rtx), val);
4781       break;
4782     case XOR:
4783       code = XOR;
4784       goto binary;
4785     case PLUS:
4786       code = MINUS;
4787       goto binary;
4788     case MINUS:
4789       code = PLUS;
4790       goto binary;
4791     binary:
4792       if (GET_MODE (v->val_rtx) != GET_MODE (val))
4793         return NULL_RTX;
4794       arg = XEXP (src, 1);
4795       if (!CONST_INT_P (arg) && GET_CODE (arg) != SYMBOL_REF)
4796         {
4797           arg = cselib_expand_value_rtx (arg, scratch_regs, 5);
4798           if (arg == NULL_RTX)
4799             return NULL_RTX;
4800           if (!CONST_INT_P (arg) && GET_CODE (arg) != SYMBOL_REF)
4801             return NULL_RTX;
4802         }
4803       ret = simplify_gen_binary (code, GET_MODE (val), val, arg);
4804       if (ret == val)
4805         /* Ensure ret isn't VALUE itself (which can happen e.g. for
4806            (plus (reg1) (reg2)) when reg2 is known to be 0), as that
4807            breaks a lot of routines during var-tracking.  */
4808         ret = gen_rtx_fmt_ee (PLUS, GET_MODE (val), val, const0_rtx);
4809       break;
4810     default:
4811       gcc_unreachable ();
4812     }
4813
4814   return gen_rtx_CONCAT (GET_MODE (v->val_rtx), v->val_rtx, ret);
4815 }
4816
4817 /* Return SRC, or, if it is a read-only MEM for which adjust_sets
4818    replated it with a constant from REG_EQUIV/REG_EQUAL note,
4819    that constant.  */
4820
4821 static inline rtx
4822 get_adjusted_src (struct count_use_info *cui, rtx src)
4823 {
4824   if (cui->n_sets == 1
4825       && MEM_P (src)
4826       && MEM_READONLY_P (src)
4827       && CONSTANT_P (cui->sets[0].src))
4828     return cui->sets[0].src;
4829   return src;
4830 }
4831
4832 /* Add stores (register and memory references) LOC which will be tracked
4833    to VTI (bb)->mos.  EXPR is the RTL expression containing the store.
4834    CUIP->insn is instruction which the LOC is part of.  */
4835
4836 static void
4837 add_stores (rtx loc, const_rtx expr, void *cuip)
4838 {
4839   enum machine_mode mode = VOIDmode, mode2;
4840   struct count_use_info *cui = (struct count_use_info *)cuip;
4841   basic_block bb = cui->bb;
4842   micro_operation mo;
4843   rtx oloc = loc, nloc, src = NULL;
4844   enum micro_operation_type type = use_type (loc, cui, &mode);
4845   bool track_p = false;
4846   cselib_val *v;
4847   bool resolve, preserve;
4848   rtx reverse;
4849
4850   if (type == MO_CLOBBER)
4851     return;
4852
4853   mode2 = mode;
4854
4855   if (REG_P (loc))
4856     {
4857       if ((GET_CODE (expr) == CLOBBER && type != MO_VAL_SET)
4858           || !(track_p = use_type (loc, NULL, &mode2) == MO_USE)
4859           || GET_CODE (expr) == CLOBBER)
4860         {
4861           mo.type = MO_CLOBBER;
4862           mo.u.loc = loc;
4863         }
4864       else
4865         {
4866           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
4867             {
4868               src = get_adjusted_src (cui, SET_SRC (expr));
4869               src = var_lowpart (mode2, src);
4870             }
4871           loc = var_lowpart (mode2, loc);
4872
4873           if (src == NULL)
4874             {
4875               mo.type = MO_SET;
4876               mo.u.loc = loc;
4877             }
4878           else
4879             {
4880               rtx xexpr = CONST_CAST_RTX (expr);
4881
4882               if (SET_SRC (expr) != src)
4883                 xexpr = gen_rtx_SET (VOIDmode, loc, src);
4884               if (same_variable_part_p (src, REG_EXPR (loc), REG_OFFSET (loc)))
4885                 mo.type = MO_COPY;
4886               else
4887                 mo.type = MO_SET;
4888               mo.u.loc = xexpr;
4889             }
4890         }
4891       mo.insn = cui->insn;
4892     }
4893   else if (MEM_P (loc)
4894            && ((track_p = use_type (loc, NULL, &mode2) == MO_USE)
4895                || cui->sets))
4896     {
4897       if (MEM_P (loc) && type == MO_VAL_SET
4898           && !REG_P (XEXP (loc, 0)) && !MEM_P (XEXP (loc, 0)))
4899         {
4900           rtx mloc = loc;
4901           enum machine_mode address_mode
4902             = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4903           cselib_val *val = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4904
4905           if (val && !cselib_preserved_value_p (val))
4906             {
4907               preserve_value (val);
4908               mo.type = MO_VAL_USE;
4909               mloc = cselib_subst_to_values (XEXP (mloc, 0));
4910               mo.u.loc = gen_rtx_CONCAT (address_mode, val->val_rtx, mloc);
4911               mo.insn = cui->insn;
4912               if (dump_file && (dump_flags & TDF_DETAILS))
4913                 log_op_type (mo.u.loc, cui->bb, cui->insn,
4914                              mo.type, dump_file);
4915               VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &mo);
4916             }
4917         }
4918
4919       if (GET_CODE (expr) == CLOBBER || !track_p)
4920         {
4921           mo.type = MO_CLOBBER;
4922           mo.u.loc = track_p ? var_lowpart (mode2, loc) : loc;
4923         }
4924       else
4925         {
4926           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
4927             {
4928               src = get_adjusted_src (cui, SET_SRC (expr));
4929               src = var_lowpart (mode2, src);
4930             }
4931           loc = var_lowpart (mode2, loc);
4932
4933           if (src == NULL)
4934             {
4935               mo.type = MO_SET;
4936               mo.u.loc = loc;
4937             }
4938           else
4939             {
4940               rtx xexpr = CONST_CAST_RTX (expr);
4941
4942               if (SET_SRC (expr) != src)
4943                 xexpr = gen_rtx_SET (VOIDmode, loc, src);
4944               if (same_variable_part_p (SET_SRC (xexpr),
4945                                         MEM_EXPR (loc),
4946                                         INT_MEM_OFFSET (loc)))
4947                 mo.type = MO_COPY;
4948               else
4949                 mo.type = MO_SET;
4950               mo.u.loc = xexpr;
4951             }
4952         }
4953       mo.insn = cui->insn;
4954     }
4955   else
4956     return;
4957
4958   if (type != MO_VAL_SET)
4959     goto log_and_return;
4960
4961   v = find_use_val (oloc, mode, cui);
4962
4963   if (!v)
4964     goto log_and_return;
4965
4966   resolve = preserve = !cselib_preserved_value_p (v);
4967
4968   nloc = replace_expr_with_values (oloc);
4969   if (nloc)
4970     oloc = nloc;
4971
4972   if (GET_CODE (PATTERN (cui->insn)) == COND_EXEC)
4973     {
4974       cselib_val *oval = cselib_lookup (oloc, GET_MODE (oloc), 0);
4975
4976       gcc_assert (oval != v);
4977       gcc_assert (REG_P (oloc) || MEM_P (oloc));
4978
4979       if (!cselib_preserved_value_p (oval))
4980         {
4981           micro_operation moa;
4982
4983           preserve_value (oval);
4984
4985           moa.type = MO_VAL_USE;
4986           moa.u.loc = gen_rtx_CONCAT (mode, oval->val_rtx, oloc);
4987           VAL_NEEDS_RESOLUTION (moa.u.loc) = 1;
4988           moa.insn = cui->insn;
4989
4990           if (dump_file && (dump_flags & TDF_DETAILS))
4991             log_op_type (moa.u.loc, cui->bb, cui->insn,
4992                          moa.type, dump_file);
4993           VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &moa);
4994         }
4995
4996       resolve = false;
4997     }
4998   else if (resolve && GET_CODE (mo.u.loc) == SET)
4999     {
5000       src = get_adjusted_src (cui, SET_SRC (expr));
5001       nloc = replace_expr_with_values (src);
5002
5003       /* Avoid the mode mismatch between oexpr and expr.  */
5004       if (!nloc && mode != mode2)
5005         {
5006           nloc = src;
5007           gcc_assert (oloc == SET_DEST (expr));
5008         }
5009
5010       if (nloc)
5011         oloc = gen_rtx_SET (GET_MODE (mo.u.loc), oloc, nloc);
5012       else
5013         {
5014           if (oloc == SET_DEST (mo.u.loc))
5015             /* No point in duplicating.  */
5016             oloc = mo.u.loc;
5017           if (!REG_P (SET_SRC (mo.u.loc)))
5018             resolve = false;
5019         }
5020     }
5021   else if (!resolve)
5022     {
5023       if (GET_CODE (mo.u.loc) == SET
5024           && oloc == SET_DEST (mo.u.loc))
5025         /* No point in duplicating.  */
5026         oloc = mo.u.loc;
5027     }
5028   else
5029     resolve = false;
5030
5031   loc = gen_rtx_CONCAT (mode, v->val_rtx, oloc);
5032
5033   if (mo.u.loc != oloc)
5034     loc = gen_rtx_CONCAT (GET_MODE (mo.u.loc), loc, mo.u.loc);
5035
5036   /* The loc of a MO_VAL_SET may have various forms:
5037
5038      (concat val dst): dst now holds val
5039
5040      (concat val (set dst src)): dst now holds val, copied from src
5041
5042      (concat (concat val dstv) dst): dst now holds val; dstv is dst
5043      after replacing mems and non-top-level regs with values.
5044
5045      (concat (concat val dstv) (set dst src)): dst now holds val,
5046      copied from src.  dstv is a value-based representation of dst, if
5047      it differs from dst.  If resolution is needed, src is a REG, and
5048      its mode is the same as that of val.
5049
5050      (concat (concat val (set dstv srcv)) (set dst src)): src
5051      copied to dst, holding val.  dstv and srcv are value-based
5052      representations of dst and src, respectively.
5053
5054   */
5055
5056   if (GET_CODE (PATTERN (cui->insn)) != COND_EXEC)
5057     {
5058       reverse = reverse_op (v->val_rtx, expr);
5059       if (reverse)
5060         {
5061           loc = gen_rtx_CONCAT (GET_MODE (mo.u.loc), loc, reverse);
5062           VAL_EXPR_HAS_REVERSE (loc) = 1;
5063         }
5064     }
5065
5066   mo.u.loc = loc;
5067
5068   if (track_p)
5069     VAL_HOLDS_TRACK_EXPR (loc) = 1;
5070   if (preserve)
5071     {
5072       VAL_NEEDS_RESOLUTION (loc) = resolve;
5073       preserve_value (v);
5074     }
5075   if (mo.type == MO_CLOBBER)
5076     VAL_EXPR_IS_CLOBBERED (loc) = 1;
5077   if (mo.type == MO_COPY)
5078     VAL_EXPR_IS_COPIED (loc) = 1;
5079
5080   mo.type = MO_VAL_SET;
5081
5082  log_and_return:
5083   if (dump_file && (dump_flags & TDF_DETAILS))
5084     log_op_type (mo.u.loc, cui->bb, cui->insn, mo.type, dump_file);
5085   VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &mo);
5086 }
5087
5088 /* Callback for cselib_record_sets_hook, that records as micro
5089    operations uses and stores in an insn after cselib_record_sets has
5090    analyzed the sets in an insn, but before it modifies the stored
5091    values in the internal tables, unless cselib_record_sets doesn't
5092    call it directly (perhaps because we're not doing cselib in the
5093    first place, in which case sets and n_sets will be 0).  */
5094
5095 static void
5096 add_with_sets (rtx insn, struct cselib_set *sets, int n_sets)
5097 {
5098   basic_block bb = BLOCK_FOR_INSN (insn);
5099   int n1, n2;
5100   struct count_use_info cui;
5101   micro_operation *mos;
5102
5103   cselib_hook_called = true;
5104
5105   adjust_sets (insn, sets, n_sets);
5106
5107   cui.insn = insn;
5108   cui.bb = bb;
5109   cui.sets = sets;
5110   cui.n_sets = n_sets;
5111
5112   n1 = VEC_length (micro_operation, VTI (bb)->mos);
5113   cui.store_p = false;
5114   note_uses (&PATTERN (insn), add_uses_1, &cui);
5115   n2 = VEC_length (micro_operation, VTI (bb)->mos) - 1;
5116   mos = VEC_address (micro_operation, VTI (bb)->mos);
5117
5118   /* Order the MO_USEs to be before MO_USE_NO_VARs and MO_VAL_USE, and
5119      MO_VAL_LOC last.  */
5120   while (n1 < n2)
5121     {
5122       while (n1 < n2 && mos[n1].type == MO_USE)
5123         n1++;
5124       while (n1 < n2 && mos[n2].type != MO_USE)
5125         n2--;
5126       if (n1 < n2)
5127         {
5128           micro_operation sw;
5129
5130           sw = mos[n1];
5131           mos[n1] = mos[n2];
5132           mos[n2] = sw;
5133         }
5134     }
5135
5136   n2 = VEC_length (micro_operation, VTI (bb)->mos) - 1;
5137   while (n1 < n2)
5138     {
5139       while (n1 < n2 && mos[n1].type != MO_VAL_LOC)
5140         n1++;
5141       while (n1 < n2 && mos[n2].type == MO_VAL_LOC)
5142         n2--;
5143       if (n1 < n2)
5144         {
5145           micro_operation sw;
5146
5147           sw = mos[n1];
5148           mos[n1] = mos[n2];
5149           mos[n2] = sw;
5150         }
5151     }
5152
5153   if (CALL_P (insn))
5154     {
5155       micro_operation mo;
5156
5157       mo.type = MO_CALL;
5158       mo.insn = insn;
5159       mo.u.loc = NULL_RTX;
5160
5161       if (dump_file && (dump_flags & TDF_DETAILS))
5162         log_op_type (PATTERN (insn), bb, insn, mo.type, dump_file);
5163       VEC_safe_push (micro_operation, heap, VTI (bb)->mos, &mo);
5164     }
5165
5166   n1 = VEC_length (micro_operation, VTI (bb)->mos);
5167   /* This will record NEXT_INSN (insn), such that we can
5168      insert notes before it without worrying about any
5169      notes that MO_USEs might emit after the insn.  */
5170   cui.store_p = true;
5171   note_stores (PATTERN (insn), add_stores, &cui);
5172   n2 = VEC_length (micro_operation, VTI (bb)->mos) - 1;
5173   mos = VEC_address (micro_operation, VTI (bb)->mos);
5174
5175   /* Order the MO_VAL_USEs first (note_stores does nothing
5176      on DEBUG_INSNs, so there are no MO_VAL_LOCs from this
5177      insn), then MO_CLOBBERs, then MO_SET/MO_COPY/MO_VAL_SET.  */
5178   while (n1 < n2)
5179     {
5180       while (n1 < n2 && mos[n1].type == MO_VAL_USE)
5181         n1++;
5182       while (n1 < n2 && mos[n2].type != MO_VAL_USE)
5183         n2--;
5184       if (n1 < n2)
5185         {
5186           micro_operation sw;
5187
5188           sw = mos[n1];
5189           mos[n1] = mos[n2];
5190           mos[n2] = sw;
5191         }
5192     }
5193
5194   n2 = VEC_length (micro_operation, VTI (bb)->mos) - 1;
5195   while (n1 < n2)
5196     {
5197       while (n1 < n2 && mos[n1].type == MO_CLOBBER)
5198         n1++;
5199       while (n1 < n2 && mos[n2].type != MO_CLOBBER)
5200         n2--;
5201       if (n1 < n2)
5202         {
5203           micro_operation sw;
5204
5205           sw = mos[n1];
5206           mos[n1] = mos[n2];
5207           mos[n2] = sw;
5208         }
5209     }
5210 }
5211
5212 static enum var_init_status
5213 find_src_status (dataflow_set *in, rtx src)
5214 {
5215   tree decl = NULL_TREE;
5216   enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
5217
5218   if (! flag_var_tracking_uninit)
5219     status = VAR_INIT_STATUS_INITIALIZED;
5220
5221   if (src && REG_P (src))
5222     decl = var_debug_decl (REG_EXPR (src));
5223   else if (src && MEM_P (src))
5224     decl = var_debug_decl (MEM_EXPR (src));
5225
5226   if (src && decl)
5227     status = get_init_value (in, src, dv_from_decl (decl));
5228
5229   return status;
5230 }
5231
5232 /* SRC is the source of an assignment.  Use SET to try to find what
5233    was ultimately assigned to SRC.  Return that value if known,
5234    otherwise return SRC itself.  */
5235
5236 static rtx
5237 find_src_set_src (dataflow_set *set, rtx src)
5238 {
5239   tree decl = NULL_TREE;   /* The variable being copied around.          */
5240   rtx set_src = NULL_RTX;  /* The value for "decl" stored in "src".      */
5241   variable var;
5242   location_chain nextp;
5243   int i;
5244   bool found;
5245
5246   if (src && REG_P (src))
5247     decl = var_debug_decl (REG_EXPR (src));
5248   else if (src && MEM_P (src))
5249     decl = var_debug_decl (MEM_EXPR (src));
5250
5251   if (src && decl)
5252     {
5253       decl_or_value dv = dv_from_decl (decl);
5254
5255       var = shared_hash_find (set->vars, dv);
5256       if (var)
5257         {
5258           found = false;
5259           for (i = 0; i < var->n_var_parts && !found; i++)
5260             for (nextp = var->var_part[i].loc_chain; nextp && !found;
5261                  nextp = nextp->next)
5262               if (rtx_equal_p (nextp->loc, src))
5263                 {
5264                   set_src = nextp->set_src;
5265                   found = true;
5266                 }
5267
5268         }
5269     }
5270
5271   return set_src;
5272 }
5273
5274 /* Compute the changes of variable locations in the basic block BB.  */
5275
5276 static bool
5277 compute_bb_dataflow (basic_block bb)
5278 {
5279   unsigned int i;
5280   micro_operation *mo;
5281   bool changed;
5282   dataflow_set old_out;
5283   dataflow_set *in = &VTI (bb)->in;
5284   dataflow_set *out = &VTI (bb)->out;
5285
5286   dataflow_set_init (&old_out);
5287   dataflow_set_copy (&old_out, out);
5288   dataflow_set_copy (out, in);
5289
5290   for (i = 0; VEC_iterate (micro_operation, VTI (bb)->mos, i, mo); i++)
5291     {
5292       rtx insn = mo->insn;
5293
5294       switch (mo->type)
5295         {
5296           case MO_CALL:
5297             dataflow_set_clear_at_call (out);
5298             break;
5299
5300           case MO_USE:
5301             {
5302               rtx loc = mo->u.loc;
5303
5304               if (REG_P (loc))
5305                 var_reg_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
5306               else if (MEM_P (loc))
5307                 var_mem_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
5308             }
5309             break;
5310
5311           case MO_VAL_LOC:
5312             {
5313               rtx loc = mo->u.loc;
5314               rtx val, vloc;
5315               tree var;
5316
5317               if (GET_CODE (loc) == CONCAT)
5318                 {
5319                   val = XEXP (loc, 0);
5320                   vloc = XEXP (loc, 1);
5321                 }
5322               else
5323                 {
5324                   val = NULL_RTX;
5325                   vloc = loc;
5326                 }
5327
5328               var = PAT_VAR_LOCATION_DECL (vloc);
5329
5330               clobber_variable_part (out, NULL_RTX,
5331                                      dv_from_decl (var), 0, NULL_RTX);
5332               if (val)
5333                 {
5334                   if (VAL_NEEDS_RESOLUTION (loc))
5335                     val_resolve (out, val, PAT_VAR_LOCATION_LOC (vloc), insn);
5336                   set_variable_part (out, val, dv_from_decl (var), 0,
5337                                      VAR_INIT_STATUS_INITIALIZED, NULL_RTX,
5338                                      INSERT);
5339                 }
5340             }
5341             break;
5342
5343           case MO_VAL_USE:
5344             {
5345               rtx loc = mo->u.loc;
5346               rtx val, vloc, uloc;
5347
5348               vloc = uloc = XEXP (loc, 1);
5349               val = XEXP (loc, 0);
5350
5351               if (GET_CODE (val) == CONCAT)
5352                 {
5353                   uloc = XEXP (val, 1);
5354                   val = XEXP (val, 0);
5355                 }
5356
5357               if (VAL_NEEDS_RESOLUTION (loc))
5358                 val_resolve (out, val, vloc, insn);
5359               else
5360                 val_store (out, val, uloc, insn, false);
5361
5362               if (VAL_HOLDS_TRACK_EXPR (loc))
5363                 {
5364                   if (GET_CODE (uloc) == REG)
5365                     var_reg_set (out, uloc, VAR_INIT_STATUS_UNINITIALIZED,
5366                                  NULL);
5367                   else if (GET_CODE (uloc) == MEM)
5368                     var_mem_set (out, uloc, VAR_INIT_STATUS_UNINITIALIZED,
5369                                  NULL);
5370                 }
5371             }
5372             break;
5373
5374           case MO_VAL_SET:
5375             {
5376               rtx loc = mo->u.loc;
5377               rtx val, vloc, uloc, reverse = NULL_RTX;
5378
5379               vloc = loc;
5380               if (VAL_EXPR_HAS_REVERSE (loc))
5381                 {
5382                   reverse = XEXP (loc, 1);
5383                   vloc = XEXP (loc, 0);
5384                 }
5385               uloc = XEXP (vloc, 1);
5386               val = XEXP (vloc, 0);
5387               vloc = uloc;
5388
5389               if (GET_CODE (val) == CONCAT)
5390                 {
5391                   vloc = XEXP (val, 1);
5392                   val = XEXP (val, 0);
5393                 }
5394
5395               if (GET_CODE (vloc) == SET)
5396                 {
5397                   rtx vsrc = SET_SRC (vloc);
5398
5399                   gcc_assert (val != vsrc);
5400                   gcc_assert (vloc == uloc || VAL_NEEDS_RESOLUTION (loc));
5401
5402                   vloc = SET_DEST (vloc);
5403
5404                   if (VAL_NEEDS_RESOLUTION (loc))
5405                     val_resolve (out, val, vsrc, insn);
5406                 }
5407               else if (VAL_NEEDS_RESOLUTION (loc))
5408                 {
5409                   gcc_assert (GET_CODE (uloc) == SET
5410                               && GET_CODE (SET_SRC (uloc)) == REG);
5411                   val_resolve (out, val, SET_SRC (uloc), insn);
5412                 }
5413
5414               if (VAL_HOLDS_TRACK_EXPR (loc))
5415                 {
5416                   if (VAL_EXPR_IS_CLOBBERED (loc))
5417                     {
5418                       if (REG_P (uloc))
5419                         var_reg_delete (out, uloc, true);
5420                       else if (MEM_P (uloc))
5421                         var_mem_delete (out, uloc, true);
5422                     }
5423                   else
5424                     {
5425                       bool copied_p = VAL_EXPR_IS_COPIED (loc);
5426                       rtx set_src = NULL;
5427                       enum var_init_status status = VAR_INIT_STATUS_INITIALIZED;
5428
5429                       if (GET_CODE (uloc) == SET)
5430                         {
5431                           set_src = SET_SRC (uloc);
5432                           uloc = SET_DEST (uloc);
5433                         }
5434
5435                       if (copied_p)
5436                         {
5437                           if (flag_var_tracking_uninit)
5438                             {
5439                               status = find_src_status (in, set_src);
5440
5441                               if (status == VAR_INIT_STATUS_UNKNOWN)
5442                                 status = find_src_status (out, set_src);
5443                             }
5444
5445                           set_src = find_src_set_src (in, set_src);
5446                         }
5447
5448                       if (REG_P (uloc))
5449                         var_reg_delete_and_set (out, uloc, !copied_p,
5450                                                 status, set_src);
5451                       else if (MEM_P (uloc))
5452                         var_mem_delete_and_set (out, uloc, !copied_p,
5453                                                 status, set_src);
5454                     }
5455                 }
5456               else if (REG_P (uloc))
5457                 var_regno_delete (out, REGNO (uloc));
5458
5459               val_store (out, val, vloc, insn, true);
5460
5461               if (reverse)
5462                 val_store (out, XEXP (reverse, 0), XEXP (reverse, 1),
5463                            insn, false);
5464             }
5465             break;
5466
5467           case MO_SET:
5468             {
5469               rtx loc = mo->u.loc;
5470               rtx set_src = NULL;
5471
5472               if (GET_CODE (loc) == SET)
5473                 {
5474                   set_src = SET_SRC (loc);
5475                   loc = SET_DEST (loc);
5476                 }
5477
5478               if (REG_P (loc))
5479                 var_reg_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
5480                                         set_src);
5481               else if (MEM_P (loc))
5482                 var_mem_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
5483                                         set_src);
5484             }
5485             break;
5486
5487           case MO_COPY:
5488             {
5489               rtx loc = mo->u.loc;
5490               enum var_init_status src_status;
5491               rtx set_src = NULL;
5492
5493               if (GET_CODE (loc) == SET)
5494                 {
5495                   set_src = SET_SRC (loc);
5496                   loc = SET_DEST (loc);
5497                 }
5498
5499               if (! flag_var_tracking_uninit)
5500                 src_status = VAR_INIT_STATUS_INITIALIZED;
5501               else
5502                 {
5503                   src_status = find_src_status (in, set_src);
5504
5505                   if (src_status == VAR_INIT_STATUS_UNKNOWN)
5506                     src_status = find_src_status (out, set_src);
5507                 }
5508
5509               set_src = find_src_set_src (in, set_src);
5510
5511               if (REG_P (loc))
5512                 var_reg_delete_and_set (out, loc, false, src_status, set_src);
5513               else if (MEM_P (loc))
5514                 var_mem_delete_and_set (out, loc, false, src_status, set_src);
5515             }
5516             break;
5517
5518           case MO_USE_NO_VAR:
5519             {
5520               rtx loc = mo->u.loc;
5521
5522               if (REG_P (loc))
5523                 var_reg_delete (out, loc, false);
5524               else if (MEM_P (loc))
5525                 var_mem_delete (out, loc, false);
5526             }
5527             break;
5528
5529           case MO_CLOBBER:
5530             {
5531               rtx loc = mo->u.loc;
5532
5533               if (REG_P (loc))
5534                 var_reg_delete (out, loc, true);
5535               else if (MEM_P (loc))
5536                 var_mem_delete (out, loc, true);
5537             }
5538             break;
5539
5540           case MO_ADJUST:
5541             out->stack_adjust += mo->u.adjust;
5542             break;
5543         }
5544     }
5545
5546   if (MAY_HAVE_DEBUG_INSNS)
5547     {
5548       dataflow_set_equiv_regs (out);
5549       htab_traverse (shared_hash_htab (out->vars), canonicalize_values_mark,
5550                      out);
5551       htab_traverse (shared_hash_htab (out->vars), canonicalize_values_star,
5552                      out);
5553 #if ENABLE_CHECKING
5554       htab_traverse (shared_hash_htab (out->vars),
5555                      canonicalize_loc_order_check, out);
5556 #endif
5557     }
5558   changed = dataflow_set_different (&old_out, out);
5559   dataflow_set_destroy (&old_out);
5560   return changed;
5561 }
5562
5563 /* Find the locations of variables in the whole function.  */
5564
5565 static bool
5566 vt_find_locations (void)
5567 {
5568   fibheap_t worklist, pending, fibheap_swap;
5569   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
5570   basic_block bb;
5571   edge e;
5572   int *bb_order;
5573   int *rc_order;
5574   int i;
5575   int htabsz = 0;
5576   int htabmax = PARAM_VALUE (PARAM_MAX_VARTRACK_SIZE);
5577   bool success = true;
5578
5579   /* Compute reverse completion order of depth first search of the CFG
5580      so that the data-flow runs faster.  */
5581   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
5582   bb_order = XNEWVEC (int, last_basic_block);
5583   pre_and_rev_post_order_compute (NULL, rc_order, false);
5584   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
5585     bb_order[rc_order[i]] = i;
5586   free (rc_order);
5587
5588   worklist = fibheap_new ();
5589   pending = fibheap_new ();
5590   visited = sbitmap_alloc (last_basic_block);
5591   in_worklist = sbitmap_alloc (last_basic_block);
5592   in_pending = sbitmap_alloc (last_basic_block);
5593   sbitmap_zero (in_worklist);
5594
5595   FOR_EACH_BB (bb)
5596     fibheap_insert (pending, bb_order[bb->index], bb);
5597   sbitmap_ones (in_pending);
5598
5599   while (success && !fibheap_empty (pending))
5600     {
5601       fibheap_swap = pending;
5602       pending = worklist;
5603       worklist = fibheap_swap;
5604       sbitmap_swap = in_pending;
5605       in_pending = in_worklist;
5606       in_worklist = sbitmap_swap;
5607
5608       sbitmap_zero (visited);
5609
5610       while (!fibheap_empty (worklist))
5611         {
5612           bb = (basic_block) fibheap_extract_min (worklist);
5613           RESET_BIT (in_worklist, bb->index);
5614           if (!TEST_BIT (visited, bb->index))
5615             {
5616               bool changed;
5617               edge_iterator ei;
5618               int oldinsz, oldoutsz;
5619
5620               SET_BIT (visited, bb->index);
5621
5622               if (VTI (bb)->in.vars)
5623                 {
5624                   htabsz
5625                     -= (htab_size (shared_hash_htab (VTI (bb)->in.vars))
5626                         + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
5627                   oldinsz
5628                     = htab_elements (shared_hash_htab (VTI (bb)->in.vars));
5629                   oldoutsz
5630                     = htab_elements (shared_hash_htab (VTI (bb)->out.vars));
5631                 }
5632               else
5633                 oldinsz = oldoutsz = 0;
5634
5635               if (MAY_HAVE_DEBUG_INSNS)
5636                 {
5637                   dataflow_set *in = &VTI (bb)->in, *first_out = NULL;
5638                   bool first = true, adjust = false;
5639
5640                   /* Calculate the IN set as the intersection of
5641                      predecessor OUT sets.  */
5642
5643                   dataflow_set_clear (in);
5644                   dst_can_be_shared = true;
5645
5646                   FOR_EACH_EDGE (e, ei, bb->preds)
5647                     if (!VTI (e->src)->flooded)
5648                       gcc_assert (bb_order[bb->index]
5649                                   <= bb_order[e->src->index]);
5650                     else if (first)
5651                       {
5652                         dataflow_set_copy (in, &VTI (e->src)->out);
5653                         first_out = &VTI (e->src)->out;
5654                         first = false;
5655                       }
5656                     else
5657                       {
5658                         dataflow_set_merge (in, &VTI (e->src)->out);
5659                         adjust = true;
5660                       }
5661
5662                   if (adjust)
5663                     {
5664                       dataflow_post_merge_adjust (in, &VTI (bb)->permp);
5665 #if ENABLE_CHECKING
5666                       /* Merge and merge_adjust should keep entries in
5667                          canonical order.  */
5668                       htab_traverse (shared_hash_htab (in->vars),
5669                                      canonicalize_loc_order_check,
5670                                      in);
5671 #endif
5672                       if (dst_can_be_shared)
5673                         {
5674                           shared_hash_destroy (in->vars);
5675                           in->vars = shared_hash_copy (first_out->vars);
5676                         }
5677                     }
5678
5679                   VTI (bb)->flooded = true;
5680                 }
5681               else
5682                 {
5683                   /* Calculate the IN set as union of predecessor OUT sets.  */
5684                   dataflow_set_clear (&VTI (bb)->in);
5685                   FOR_EACH_EDGE (e, ei, bb->preds)
5686                     dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
5687                 }
5688
5689               changed = compute_bb_dataflow (bb);
5690               htabsz += (htab_size (shared_hash_htab (VTI (bb)->in.vars))
5691                          + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
5692
5693               if (htabmax && htabsz > htabmax)
5694                 {
5695                   if (MAY_HAVE_DEBUG_INSNS)
5696                     inform (DECL_SOURCE_LOCATION (cfun->decl),
5697                             "variable tracking size limit exceeded with "
5698                             "-fvar-tracking-assignments, retrying without");
5699                   else
5700                     inform (DECL_SOURCE_LOCATION (cfun->decl),
5701                             "variable tracking size limit exceeded");
5702                   success = false;
5703                   break;
5704                 }
5705
5706               if (changed)
5707                 {
5708                   FOR_EACH_EDGE (e, ei, bb->succs)
5709                     {
5710                       if (e->dest == EXIT_BLOCK_PTR)
5711                         continue;
5712
5713                       if (TEST_BIT (visited, e->dest->index))
5714                         {
5715                           if (!TEST_BIT (in_pending, e->dest->index))
5716                             {
5717                               /* Send E->DEST to next round.  */
5718                               SET_BIT (in_pending, e->dest->index);
5719                               fibheap_insert (pending,
5720                                               bb_order[e->dest->index],
5721                                               e->dest);
5722                             }
5723                         }
5724                       else if (!TEST_BIT (in_worklist, e->dest->index))
5725                         {
5726                           /* Add E->DEST to current round.  */
5727                           SET_BIT (in_worklist, e->dest->index);
5728                           fibheap_insert (worklist, bb_order[e->dest->index],
5729                                           e->dest);
5730                         }
5731                     }
5732                 }
5733
5734               if (dump_file)
5735                 fprintf (dump_file,
5736                          "BB %i: in %i (was %i), out %i (was %i), rem %i + %i, tsz %i\n",
5737                          bb->index,
5738                          (int)htab_elements (shared_hash_htab (VTI (bb)->in.vars)),
5739                          oldinsz,
5740                          (int)htab_elements (shared_hash_htab (VTI (bb)->out.vars)),
5741                          oldoutsz,
5742                          (int)worklist->nodes, (int)pending->nodes, htabsz);
5743
5744               if (dump_file && (dump_flags & TDF_DETAILS))
5745                 {
5746                   fprintf (dump_file, "BB %i IN:\n", bb->index);
5747                   dump_dataflow_set (&VTI (bb)->in);
5748                   fprintf (dump_file, "BB %i OUT:\n", bb->index);
5749                   dump_dataflow_set (&VTI (bb)->out);
5750                 }
5751             }
5752         }
5753     }
5754
5755   if (success && MAY_HAVE_DEBUG_INSNS)
5756     FOR_EACH_BB (bb)
5757       gcc_assert (VTI (bb)->flooded);
5758
5759   free (bb_order);
5760   fibheap_delete (worklist);
5761   fibheap_delete (pending);
5762   sbitmap_free (visited);
5763   sbitmap_free (in_worklist);
5764   sbitmap_free (in_pending);
5765
5766   return success;
5767 }
5768
5769 /* Print the content of the LIST to dump file.  */
5770
5771 static void
5772 dump_attrs_list (attrs list)
5773 {
5774   for (; list; list = list->next)
5775     {
5776       if (dv_is_decl_p (list->dv))
5777         print_mem_expr (dump_file, dv_as_decl (list->dv));
5778       else
5779         print_rtl_single (dump_file, dv_as_value (list->dv));
5780       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
5781     }
5782   fprintf (dump_file, "\n");
5783 }
5784
5785 /* Print the information about variable *SLOT to dump file.  */
5786
5787 static int
5788 dump_var_slot (void **slot, void *data ATTRIBUTE_UNUSED)
5789 {
5790   variable var = (variable) *slot;
5791
5792   dump_var (var);
5793
5794   /* Continue traversing the hash table.  */
5795   return 1;
5796 }
5797
5798 /* Print the information about variable VAR to dump file.  */
5799
5800 static void
5801 dump_var (variable var)
5802 {
5803   int i;
5804   location_chain node;
5805
5806   if (dv_is_decl_p (var->dv))
5807     {
5808       const_tree decl = dv_as_decl (var->dv);
5809
5810       if (DECL_NAME (decl))
5811         {
5812           fprintf (dump_file, "  name: %s",
5813                    IDENTIFIER_POINTER (DECL_NAME (decl)));
5814           if (dump_flags & TDF_UID)
5815             fprintf (dump_file, "D.%u", DECL_UID (decl));
5816         }
5817       else if (TREE_CODE (decl) == DEBUG_EXPR_DECL)
5818         fprintf (dump_file, "  name: D#%u", DEBUG_TEMP_UID (decl));
5819       else
5820         fprintf (dump_file, "  name: D.%u", DECL_UID (decl));
5821       fprintf (dump_file, "\n");
5822     }
5823   else
5824     {
5825       fputc (' ', dump_file);
5826       print_rtl_single (dump_file, dv_as_value (var->dv));
5827     }
5828
5829   for (i = 0; i < var->n_var_parts; i++)
5830     {
5831       fprintf (dump_file, "    offset %ld\n",
5832                (long) var->var_part[i].offset);
5833       for (node = var->var_part[i].loc_chain; node; node = node->next)
5834         {
5835           fprintf (dump_file, "      ");
5836           if (node->init == VAR_INIT_STATUS_UNINITIALIZED)
5837             fprintf (dump_file, "[uninit]");
5838           print_rtl_single (dump_file, node->loc);
5839         }
5840     }
5841 }
5842
5843 /* Print the information about variables from hash table VARS to dump file.  */
5844
5845 static void
5846 dump_vars (htab_t vars)
5847 {
5848   if (htab_elements (vars) > 0)
5849     {
5850       fprintf (dump_file, "Variables:\n");
5851       htab_traverse (vars, dump_var_slot, NULL);
5852     }
5853 }
5854
5855 /* Print the dataflow set SET to dump file.  */
5856
5857 static void
5858 dump_dataflow_set (dataflow_set *set)
5859 {
5860   int i;
5861
5862   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
5863            set->stack_adjust);
5864   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5865     {
5866       if (set->regs[i])
5867         {
5868           fprintf (dump_file, "Reg %d:", i);
5869           dump_attrs_list (set->regs[i]);
5870         }
5871     }
5872   dump_vars (shared_hash_htab (set->vars));
5873   fprintf (dump_file, "\n");
5874 }
5875
5876 /* Print the IN and OUT sets for each basic block to dump file.  */
5877
5878 static void
5879 dump_dataflow_sets (void)
5880 {
5881   basic_block bb;
5882
5883   FOR_EACH_BB (bb)
5884     {
5885       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
5886       fprintf (dump_file, "IN:\n");
5887       dump_dataflow_set (&VTI (bb)->in);
5888       fprintf (dump_file, "OUT:\n");
5889       dump_dataflow_set (&VTI (bb)->out);
5890     }
5891 }
5892
5893 /* Add variable VAR to the hash table of changed variables and
5894    if it has no locations delete it from SET's hash table.  */
5895
5896 static void
5897 variable_was_changed (variable var, dataflow_set *set)
5898 {
5899   hashval_t hash = dv_htab_hash (var->dv);
5900
5901   if (emit_notes)
5902     {
5903       void **slot;
5904       bool old_cur_loc_changed = false;
5905
5906       /* Remember this decl or VALUE has been added to changed_variables.  */
5907       set_dv_changed (var->dv, true);
5908
5909       slot = htab_find_slot_with_hash (changed_variables,
5910                                        var->dv,
5911                                        hash, INSERT);
5912
5913       if (*slot)
5914         {
5915           variable old_var = (variable) *slot;
5916           gcc_assert (old_var->in_changed_variables);
5917           old_var->in_changed_variables = false;
5918           old_cur_loc_changed = old_var->cur_loc_changed;
5919           variable_htab_free (*slot);
5920         }
5921       if (set && var->n_var_parts == 0)
5922         {
5923           variable empty_var;
5924
5925           empty_var = (variable) pool_alloc (dv_pool (var->dv));
5926           empty_var->dv = var->dv;
5927           empty_var->refcount = 1;
5928           empty_var->n_var_parts = 0;
5929           empty_var->cur_loc_changed = true;
5930           empty_var->in_changed_variables = true;
5931           *slot = empty_var;
5932           goto drop_var;
5933         }
5934       else
5935         {
5936           var->refcount++;
5937           var->in_changed_variables = true;
5938           /* If within processing one uop a variable is deleted
5939              and then readded, we need to assume it has changed.  */
5940           if (old_cur_loc_changed)
5941             var->cur_loc_changed = true;
5942           *slot = var;
5943         }
5944     }
5945   else
5946     {
5947       gcc_assert (set);
5948       if (var->n_var_parts == 0)
5949         {
5950           void **slot;
5951
5952         drop_var:
5953           slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
5954           if (slot)
5955             {
5956               if (shared_hash_shared (set->vars))
5957                 slot = shared_hash_find_slot_unshare (&set->vars, var->dv,
5958                                                       NO_INSERT);
5959               htab_clear_slot (shared_hash_htab (set->vars), slot);
5960             }
5961         }
5962     }
5963 }
5964
5965 /* Look for the index in VAR->var_part corresponding to OFFSET.
5966    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
5967    referenced int will be set to the index that the part has or should
5968    have, if it should be inserted.  */
5969
5970 static inline int
5971 find_variable_location_part (variable var, HOST_WIDE_INT offset,
5972                              int *insertion_point)
5973 {
5974   int pos, low, high;
5975
5976   /* Find the location part.  */
5977   low = 0;
5978   high = var->n_var_parts;
5979   while (low != high)
5980     {
5981       pos = (low + high) / 2;
5982       if (var->var_part[pos].offset < offset)
5983         low = pos + 1;
5984       else
5985         high = pos;
5986     }
5987   pos = low;
5988
5989   if (insertion_point)
5990     *insertion_point = pos;
5991
5992   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
5993     return pos;
5994
5995   return -1;
5996 }
5997
5998 static void **
5999 set_slot_part (dataflow_set *set, rtx loc, void **slot,
6000                decl_or_value dv, HOST_WIDE_INT offset,
6001                enum var_init_status initialized, rtx set_src)
6002 {
6003   int pos;
6004   location_chain node, next;
6005   location_chain *nextp;
6006   variable var;
6007   bool onepart = dv_onepart_p (dv);
6008
6009   gcc_assert (offset == 0 || !onepart);
6010   gcc_assert (loc != dv_as_opaque (dv));
6011
6012   var = (variable) *slot;
6013
6014   if (! flag_var_tracking_uninit)
6015     initialized = VAR_INIT_STATUS_INITIALIZED;
6016
6017   if (!var)
6018     {
6019       /* Create new variable information.  */
6020       var = (variable) pool_alloc (dv_pool (dv));
6021       var->dv = dv;
6022       var->refcount = 1;
6023       var->n_var_parts = 1;
6024       var->cur_loc_changed = false;
6025       var->in_changed_variables = false;
6026       var->var_part[0].offset = offset;
6027       var->var_part[0].loc_chain = NULL;
6028       var->var_part[0].cur_loc = NULL;
6029       *slot = var;
6030       pos = 0;
6031       nextp = &var->var_part[0].loc_chain;
6032     }
6033   else if (onepart)
6034     {
6035       int r = -1, c = 0;
6036
6037       gcc_assert (dv_as_opaque (var->dv) == dv_as_opaque (dv));
6038
6039       pos = 0;
6040
6041       if (GET_CODE (loc) == VALUE)
6042         {
6043           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6044                nextp = &node->next)
6045             if (GET_CODE (node->loc) == VALUE)
6046               {
6047                 if (node->loc == loc)
6048                   {
6049                     r = 0;
6050                     break;
6051                   }
6052                 if (canon_value_cmp (node->loc, loc))
6053                   c++;
6054                 else
6055                   {
6056                     r = 1;
6057                     break;
6058                   }
6059               }
6060             else if (REG_P (node->loc) || MEM_P (node->loc))
6061               c++;
6062             else
6063               {
6064                 r = 1;
6065                 break;
6066               }
6067         }
6068       else if (REG_P (loc))
6069         {
6070           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6071                nextp = &node->next)
6072             if (REG_P (node->loc))
6073               {
6074                 if (REGNO (node->loc) < REGNO (loc))
6075                   c++;
6076                 else
6077                   {
6078                     if (REGNO (node->loc) == REGNO (loc))
6079                       r = 0;
6080                     else
6081                       r = 1;
6082                     break;
6083                   }
6084               }
6085             else
6086               {
6087                 r = 1;
6088                 break;
6089               }
6090         }
6091       else if (MEM_P (loc))
6092         {
6093           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6094                nextp = &node->next)
6095             if (REG_P (node->loc))
6096               c++;
6097             else if (MEM_P (node->loc))
6098               {
6099                 if ((r = loc_cmp (XEXP (node->loc, 0), XEXP (loc, 0))) >= 0)
6100                   break;
6101                 else
6102                   c++;
6103               }
6104             else
6105               {
6106                 r = 1;
6107                 break;
6108               }
6109         }
6110       else
6111         for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6112              nextp = &node->next)
6113           if ((r = loc_cmp (node->loc, loc)) >= 0)
6114             break;
6115           else
6116             c++;
6117
6118       if (r == 0)
6119         return slot;
6120
6121       if (shared_var_p (var, set->vars))
6122         {
6123           slot = unshare_variable (set, slot, var, initialized);
6124           var = (variable)*slot;
6125           for (nextp = &var->var_part[0].loc_chain; c;
6126                nextp = &(*nextp)->next)
6127             c--;
6128           gcc_assert ((!node && !*nextp) || node->loc == (*nextp)->loc);
6129         }
6130     }
6131   else
6132     {
6133       int inspos = 0;
6134
6135       gcc_assert (dv_as_decl (var->dv) == dv_as_decl (dv));
6136
6137       pos = find_variable_location_part (var, offset, &inspos);
6138
6139       if (pos >= 0)
6140         {
6141           node = var->var_part[pos].loc_chain;
6142
6143           if (node
6144               && ((REG_P (node->loc) && REG_P (loc)
6145                    && REGNO (node->loc) == REGNO (loc))
6146                   || rtx_equal_p (node->loc, loc)))
6147             {
6148               /* LOC is in the beginning of the chain so we have nothing
6149                  to do.  */
6150               if (node->init < initialized)
6151                 node->init = initialized;
6152               if (set_src != NULL)
6153                 node->set_src = set_src;
6154
6155               return slot;
6156             }
6157           else
6158             {
6159               /* We have to make a copy of a shared variable.  */
6160               if (shared_var_p (var, set->vars))
6161                 {
6162                   slot = unshare_variable (set, slot, var, initialized);
6163                   var = (variable)*slot;
6164                 }
6165             }
6166         }
6167       else
6168         {
6169           /* We have not found the location part, new one will be created.  */
6170
6171           /* We have to make a copy of the shared variable.  */
6172           if (shared_var_p (var, set->vars))
6173             {
6174               slot = unshare_variable (set, slot, var, initialized);
6175               var = (variable)*slot;
6176             }
6177
6178           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
6179              thus there are at most MAX_VAR_PARTS different offsets.  */
6180           gcc_assert (var->n_var_parts < MAX_VAR_PARTS
6181                       && (!var->n_var_parts || !dv_onepart_p (var->dv)));
6182
6183           /* We have to move the elements of array starting at index
6184              inspos to the next position.  */
6185           for (pos = var->n_var_parts; pos > inspos; pos--)
6186             var->var_part[pos] = var->var_part[pos - 1];
6187
6188           var->n_var_parts++;
6189           var->var_part[pos].offset = offset;
6190           var->var_part[pos].loc_chain = NULL;
6191           var->var_part[pos].cur_loc = NULL;
6192         }
6193
6194       /* Delete the location from the list.  */
6195       nextp = &var->var_part[pos].loc_chain;
6196       for (node = var->var_part[pos].loc_chain; node; node = next)
6197         {
6198           next = node->next;
6199           if ((REG_P (node->loc) && REG_P (loc)
6200                && REGNO (node->loc) == REGNO (loc))
6201               || rtx_equal_p (node->loc, loc))
6202             {
6203               /* Save these values, to assign to the new node, before
6204                  deleting this one.  */
6205               if (node->init > initialized)
6206                 initialized = node->init;
6207               if (node->set_src != NULL && set_src == NULL)
6208                 set_src = node->set_src;
6209               if (var->var_part[pos].cur_loc == node->loc)
6210                 {
6211                   var->var_part[pos].cur_loc = NULL;
6212                   var->cur_loc_changed = true;
6213                 }
6214               pool_free (loc_chain_pool, node);
6215               *nextp = next;
6216               break;
6217             }
6218           else
6219             nextp = &node->next;
6220         }
6221
6222       nextp = &var->var_part[pos].loc_chain;
6223     }
6224
6225   /* Add the location to the beginning.  */
6226   node = (location_chain) pool_alloc (loc_chain_pool);
6227   node->loc = loc;
6228   node->init = initialized;
6229   node->set_src = set_src;
6230   node->next = *nextp;
6231   *nextp = node;
6232
6233   if (onepart && emit_notes)
6234     add_value_chains (var->dv, loc);
6235
6236   /* If no location was emitted do so.  */
6237   if (var->var_part[pos].cur_loc == NULL)
6238     variable_was_changed (var, set);
6239
6240   return slot;
6241 }
6242
6243 /* Set the part of variable's location in the dataflow set SET.  The
6244    variable part is specified by variable's declaration in DV and
6245    offset OFFSET and the part's location by LOC.  IOPT should be
6246    NO_INSERT if the variable is known to be in SET already and the
6247    variable hash table must not be resized, and INSERT otherwise.  */
6248
6249 static void
6250 set_variable_part (dataflow_set *set, rtx loc,
6251                    decl_or_value dv, HOST_WIDE_INT offset,
6252                    enum var_init_status initialized, rtx set_src,
6253                    enum insert_option iopt)
6254 {
6255   void **slot;
6256
6257   if (iopt == NO_INSERT)
6258     slot = shared_hash_find_slot_noinsert (set->vars, dv);
6259   else
6260     {
6261       slot = shared_hash_find_slot (set->vars, dv);
6262       if (!slot)
6263         slot = shared_hash_find_slot_unshare (&set->vars, dv, iopt);
6264     }
6265   slot = set_slot_part (set, loc, slot, dv, offset, initialized, set_src);
6266 }
6267
6268 /* Remove all recorded register locations for the given variable part
6269    from dataflow set SET, except for those that are identical to loc.
6270    The variable part is specified by variable's declaration or value
6271    DV and offset OFFSET.  */
6272
6273 static void **
6274 clobber_slot_part (dataflow_set *set, rtx loc, void **slot,
6275                    HOST_WIDE_INT offset, rtx set_src)
6276 {
6277   variable var = (variable) *slot;
6278   int pos = find_variable_location_part (var, offset, NULL);
6279
6280   if (pos >= 0)
6281     {
6282       location_chain node, next;
6283
6284       /* Remove the register locations from the dataflow set.  */
6285       next = var->var_part[pos].loc_chain;
6286       for (node = next; node; node = next)
6287         {
6288           next = node->next;
6289           if (node->loc != loc
6290               && (!flag_var_tracking_uninit
6291                   || !set_src
6292                   || MEM_P (set_src)
6293                   || !rtx_equal_p (set_src, node->set_src)))
6294             {
6295               if (REG_P (node->loc))
6296                 {
6297                   attrs anode, anext;
6298                   attrs *anextp;
6299
6300                   /* Remove the variable part from the register's
6301                      list, but preserve any other variable parts
6302                      that might be regarded as live in that same
6303                      register.  */
6304                   anextp = &set->regs[REGNO (node->loc)];
6305                   for (anode = *anextp; anode; anode = anext)
6306                     {
6307                       anext = anode->next;
6308                       if (dv_as_opaque (anode->dv) == dv_as_opaque (var->dv)
6309                           && anode->offset == offset)
6310                         {
6311                           pool_free (attrs_pool, anode);
6312                           *anextp = anext;
6313                         }
6314                       else
6315                         anextp = &anode->next;
6316                     }
6317                 }
6318
6319               slot = delete_slot_part (set, node->loc, slot, offset);
6320             }
6321         }
6322     }
6323
6324   return slot;
6325 }
6326
6327 /* Remove all recorded register locations for the given variable part
6328    from dataflow set SET, except for those that are identical to loc.
6329    The variable part is specified by variable's declaration or value
6330    DV and offset OFFSET.  */
6331
6332 static void
6333 clobber_variable_part (dataflow_set *set, rtx loc, decl_or_value dv,
6334                        HOST_WIDE_INT offset, rtx set_src)
6335 {
6336   void **slot;
6337
6338   if (!dv_as_opaque (dv)
6339       || (!dv_is_value_p (dv) && ! DECL_P (dv_as_decl (dv))))
6340     return;
6341
6342   slot = shared_hash_find_slot_noinsert (set->vars, dv);
6343   if (!slot)
6344     return;
6345
6346   slot = clobber_slot_part (set, loc, slot, offset, set_src);
6347 }
6348
6349 /* Delete the part of variable's location from dataflow set SET.  The
6350    variable part is specified by its SET->vars slot SLOT and offset
6351    OFFSET and the part's location by LOC.  */
6352
6353 static void **
6354 delete_slot_part (dataflow_set *set, rtx loc, void **slot,
6355                   HOST_WIDE_INT offset)
6356 {
6357   variable var = (variable) *slot;
6358   int pos = find_variable_location_part (var, offset, NULL);
6359
6360   if (pos >= 0)
6361     {
6362       location_chain node, next;
6363       location_chain *nextp;
6364       bool changed;
6365
6366       if (shared_var_p (var, set->vars))
6367         {
6368           /* If the variable contains the location part we have to
6369              make a copy of the variable.  */
6370           for (node = var->var_part[pos].loc_chain; node;
6371                node = node->next)
6372             {
6373               if ((REG_P (node->loc) && REG_P (loc)
6374                    && REGNO (node->loc) == REGNO (loc))
6375                   || rtx_equal_p (node->loc, loc))
6376                 {
6377                   slot = unshare_variable (set, slot, var,
6378                                            VAR_INIT_STATUS_UNKNOWN);
6379                   var = (variable)*slot;
6380                   break;
6381                 }
6382             }
6383         }
6384
6385       /* Delete the location part.  */
6386       changed = false;
6387       nextp = &var->var_part[pos].loc_chain;
6388       for (node = *nextp; node; node = next)
6389         {
6390           next = node->next;
6391           if ((REG_P (node->loc) && REG_P (loc)
6392                && REGNO (node->loc) == REGNO (loc))
6393               || rtx_equal_p (node->loc, loc))
6394             {
6395               if (emit_notes && pos == 0 && dv_onepart_p (var->dv))
6396                 remove_value_chains (var->dv, node->loc);
6397               /* If we have deleted the location which was last emitted
6398                  we have to emit new location so add the variable to set
6399                  of changed variables.  */
6400               if (var->var_part[pos].cur_loc == node->loc)
6401                 {
6402                   changed = true;
6403                   var->var_part[pos].cur_loc = NULL;
6404                   var->cur_loc_changed = true;
6405                 }
6406               pool_free (loc_chain_pool, node);
6407               *nextp = next;
6408               break;
6409             }
6410           else
6411             nextp = &node->next;
6412         }
6413
6414       if (var->var_part[pos].loc_chain == NULL)
6415         {
6416           changed = true;
6417           var->n_var_parts--;
6418           if (emit_notes)
6419             var->cur_loc_changed = true;
6420           while (pos < var->n_var_parts)
6421             {
6422               var->var_part[pos] = var->var_part[pos + 1];
6423               pos++;
6424             }
6425         }
6426       if (changed)
6427         variable_was_changed (var, set);
6428     }
6429
6430   return slot;
6431 }
6432
6433 /* Delete the part of variable's location from dataflow set SET.  The
6434    variable part is specified by variable's declaration or value DV
6435    and offset OFFSET and the part's location by LOC.  */
6436
6437 static void
6438 delete_variable_part (dataflow_set *set, rtx loc, decl_or_value dv,
6439                       HOST_WIDE_INT offset)
6440 {
6441   void **slot = shared_hash_find_slot_noinsert (set->vars, dv);
6442   if (!slot)
6443     return;
6444
6445   slot = delete_slot_part (set, loc, slot, offset);
6446 }
6447
6448 /* Structure for passing some other parameters to function
6449    vt_expand_loc_callback.  */
6450 struct expand_loc_callback_data
6451 {
6452   /* The variables and values active at this point.  */
6453   htab_t vars;
6454
6455   /* True in vt_expand_loc_dummy calls, no rtl should be allocated.
6456      Non-NULL should be returned if vt_expand_loc would return
6457      non-NULL in that case, NULL otherwise.  cur_loc_changed should be
6458      computed and cur_loc recomputed when possible (but just once
6459      per emit_notes_for_changes call).  */
6460   bool dummy;
6461
6462   /* True if expansion of subexpressions had to recompute some
6463      VALUE/DEBUG_EXPR_DECL's cur_loc or used a VALUE/DEBUG_EXPR_DECL
6464      whose cur_loc has been already recomputed during current
6465      emit_notes_for_changes call.  */
6466   bool cur_loc_changed;
6467 };
6468
6469 /* Callback for cselib_expand_value, that looks for expressions
6470    holding the value in the var-tracking hash tables.  Return X for
6471    standard processing, anything else is to be used as-is.  */
6472
6473 static rtx
6474 vt_expand_loc_callback (rtx x, bitmap regs, int max_depth, void *data)
6475 {
6476   struct expand_loc_callback_data *elcd
6477     = (struct expand_loc_callback_data *) data;
6478   bool dummy = elcd->dummy;
6479   bool cur_loc_changed = elcd->cur_loc_changed;
6480   decl_or_value dv;
6481   variable var;
6482   location_chain loc;
6483   rtx result, subreg, xret;
6484
6485   switch (GET_CODE (x))
6486     {
6487     case SUBREG:
6488       if (dummy)
6489         {
6490           if (cselib_dummy_expand_value_rtx_cb (SUBREG_REG (x), regs,
6491                                                 max_depth - 1,
6492                                                 vt_expand_loc_callback, data))
6493             return pc_rtx;
6494           else
6495             return NULL;
6496         }
6497
6498       subreg = cselib_expand_value_rtx_cb (SUBREG_REG (x), regs,
6499                                            max_depth - 1,
6500                                            vt_expand_loc_callback, data);
6501
6502       if (!subreg)
6503         return NULL;
6504
6505       result = simplify_gen_subreg (GET_MODE (x), subreg,
6506                                     GET_MODE (SUBREG_REG (x)),
6507                                     SUBREG_BYTE (x));
6508
6509       /* Invalid SUBREGs are ok in debug info.  ??? We could try
6510          alternate expansions for the VALUE as well.  */
6511       if (!result)
6512         result = gen_rtx_raw_SUBREG (GET_MODE (x), subreg, SUBREG_BYTE (x));
6513
6514       return result;
6515
6516     case DEBUG_EXPR:
6517       dv = dv_from_decl (DEBUG_EXPR_TREE_DECL (x));
6518       xret = NULL;
6519       break;
6520
6521     case VALUE:
6522       dv = dv_from_value (x);
6523       xret = x;
6524       break;
6525
6526     default:
6527       return x;
6528     }
6529
6530   if (VALUE_RECURSED_INTO (x))
6531     return NULL;
6532
6533   var = (variable) htab_find_with_hash (elcd->vars, dv, dv_htab_hash (dv));
6534
6535   if (!var)
6536     {
6537       if (dummy && dv_changed_p (dv))
6538         elcd->cur_loc_changed = true;
6539       return xret;
6540     }
6541
6542   if (var->n_var_parts == 0)
6543     {
6544       if (dummy)
6545         elcd->cur_loc_changed = true;
6546       return xret;
6547     }
6548
6549   gcc_assert (var->n_var_parts == 1);
6550
6551   VALUE_RECURSED_INTO (x) = true;
6552   result = NULL;
6553
6554   if (var->var_part[0].cur_loc)
6555     {
6556       if (dummy)
6557         {
6558           if (cselib_dummy_expand_value_rtx_cb (var->var_part[0].cur_loc, regs,
6559                                                 max_depth,
6560                                                 vt_expand_loc_callback, data))
6561             result = pc_rtx;
6562         }
6563       else
6564         result = cselib_expand_value_rtx_cb (var->var_part[0].cur_loc, regs,
6565                                              max_depth,
6566                                              vt_expand_loc_callback, data);
6567       if (result)
6568         set_dv_changed (dv, false);
6569     }
6570   if (!result && dv_changed_p (dv))
6571     {
6572       set_dv_changed (dv, false);
6573       for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
6574         if (loc->loc == var->var_part[0].cur_loc)
6575           continue;
6576         else if (dummy)
6577           {
6578             elcd->cur_loc_changed = cur_loc_changed;
6579             if (cselib_dummy_expand_value_rtx_cb (loc->loc, regs, max_depth,
6580                                                   vt_expand_loc_callback,
6581                                                   data))
6582               {
6583                 result = pc_rtx;
6584                 break;
6585               }
6586             else
6587               {
6588                 result = cselib_expand_value_rtx_cb (loc->loc, regs, max_depth,
6589                                                      vt_expand_loc_callback,
6590                                                      data);
6591                 if (result)
6592                   break;
6593               }
6594           }
6595       if (dummy && (result || var->var_part[0].cur_loc))
6596         var->cur_loc_changed = true;
6597       var->var_part[0].cur_loc = loc ? loc->loc : NULL_RTX;
6598     }
6599   if (dummy)
6600     {
6601       if (var->cur_loc_changed)
6602         elcd->cur_loc_changed = true;
6603       else if (!result && var->var_part[0].cur_loc == NULL_RTX)
6604         elcd->cur_loc_changed = cur_loc_changed;
6605     }
6606
6607   VALUE_RECURSED_INTO (x) = false;
6608   if (result)
6609     return result;
6610   else
6611     return xret;
6612 }
6613
6614 /* Expand VALUEs in LOC, using VARS as well as cselib's equivalence
6615    tables.  */
6616
6617 static rtx
6618 vt_expand_loc (rtx loc, htab_t vars)
6619 {
6620   struct expand_loc_callback_data data;
6621
6622   if (!MAY_HAVE_DEBUG_INSNS)
6623     return loc;
6624
6625   data.vars = vars;
6626   data.dummy = false;
6627   data.cur_loc_changed = false;
6628   loc = cselib_expand_value_rtx_cb (loc, scratch_regs, 5,
6629                                     vt_expand_loc_callback, &data);
6630
6631   if (loc && MEM_P (loc))
6632     loc = targetm.delegitimize_address (loc);
6633   return loc;
6634 }
6635
6636 /* Like vt_expand_loc, but only return true/false (whether vt_expand_loc
6637    would succeed or not, without actually allocating new rtxes.  */
6638
6639 static bool
6640 vt_expand_loc_dummy (rtx loc, htab_t vars, bool *pcur_loc_changed)
6641 {
6642   struct expand_loc_callback_data data;
6643   bool ret;
6644
6645   gcc_assert (MAY_HAVE_DEBUG_INSNS);
6646   data.vars = vars;
6647   data.dummy = true;
6648   data.cur_loc_changed = false;
6649   ret = cselib_dummy_expand_value_rtx_cb (loc, scratch_regs, 5,
6650                                           vt_expand_loc_callback, &data);
6651   *pcur_loc_changed = data.cur_loc_changed;
6652   return ret;
6653 }
6654
6655 #ifdef ENABLE_RTL_CHECKING
6656 /* Used to verify that cur_loc_changed updating is safe.  */
6657 static struct pointer_map_t *emitted_notes;
6658 #endif
6659
6660 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
6661    additional parameters: WHERE specifies whether the note shall be emitted
6662    before or after instruction INSN.  */
6663
6664 static int
6665 emit_note_insn_var_location (void **varp, void *data)
6666 {
6667   variable var = (variable) *varp;
6668   rtx insn = ((emit_note_data *)data)->insn;
6669   enum emit_note_where where = ((emit_note_data *)data)->where;
6670   htab_t vars = ((emit_note_data *)data)->vars;
6671   rtx note, note_vl;
6672   int i, j, n_var_parts;
6673   bool complete;
6674   enum var_init_status initialized = VAR_INIT_STATUS_UNINITIALIZED;
6675   HOST_WIDE_INT last_limit;
6676   tree type_size_unit;
6677   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
6678   rtx loc[MAX_VAR_PARTS];
6679   tree decl;
6680   location_chain lc;
6681
6682   if (dv_is_value_p (var->dv))
6683     goto value_or_debug_decl;
6684
6685   decl = dv_as_decl (var->dv);
6686
6687   if (TREE_CODE (decl) == DEBUG_EXPR_DECL)
6688     goto value_or_debug_decl;
6689
6690   complete = true;
6691   last_limit = 0;
6692   n_var_parts = 0;
6693   if (!MAY_HAVE_DEBUG_STMTS)
6694     {
6695       for (i = 0; i < var->n_var_parts; i++)
6696         if (var->var_part[i].cur_loc == NULL && var->var_part[i].loc_chain)
6697           {
6698             var->var_part[i].cur_loc = var->var_part[i].loc_chain->loc;
6699             var->cur_loc_changed = true;
6700           }
6701       if (var->n_var_parts == 0)
6702         var->cur_loc_changed = true;
6703     }
6704 #ifndef ENABLE_RTL_CHECKING
6705   if (!var->cur_loc_changed)
6706     goto clear;
6707 #endif
6708   for (i = 0; i < var->n_var_parts; i++)
6709     {
6710       enum machine_mode mode, wider_mode;
6711       rtx loc2;
6712
6713       if (last_limit < var->var_part[i].offset)
6714         {
6715           complete = false;
6716           break;
6717         }
6718       else if (last_limit > var->var_part[i].offset)
6719         continue;
6720       offsets[n_var_parts] = var->var_part[i].offset;
6721       if (!var->var_part[i].cur_loc)
6722         {
6723           complete = false;
6724           continue;
6725         }
6726       loc2 = vt_expand_loc (var->var_part[i].cur_loc, vars);
6727       if (!loc2)
6728         {
6729           complete = false;
6730           continue;
6731         }
6732       loc[n_var_parts] = loc2;
6733       mode = GET_MODE (var->var_part[i].cur_loc);
6734       for (lc = var->var_part[i].loc_chain; lc; lc = lc->next)
6735         if (var->var_part[i].cur_loc == lc->loc)
6736           {
6737             initialized = lc->init;
6738             break;
6739           }
6740       gcc_assert (lc);
6741       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
6742
6743       /* Attempt to merge adjacent registers or memory.  */
6744       wider_mode = GET_MODE_WIDER_MODE (mode);
6745       for (j = i + 1; j < var->n_var_parts; j++)
6746         if (last_limit <= var->var_part[j].offset)
6747           break;
6748       if (j < var->n_var_parts
6749           && wider_mode != VOIDmode
6750           && var->var_part[j].cur_loc
6751           && mode == GET_MODE (var->var_part[j].cur_loc)
6752           && (REG_P (loc[n_var_parts]) || MEM_P (loc[n_var_parts]))
6753           && last_limit == var->var_part[j].offset
6754           && (loc2 = vt_expand_loc (var->var_part[j].cur_loc, vars))
6755           && GET_CODE (loc[n_var_parts]) == GET_CODE (loc2))
6756         {
6757           rtx new_loc = NULL;
6758
6759           if (REG_P (loc[n_var_parts])
6760               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
6761                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
6762               && end_hard_regno (mode, REGNO (loc[n_var_parts]))
6763                  == REGNO (loc2))
6764             {
6765               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
6766                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
6767                                            mode, 0);
6768               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
6769                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
6770               if (new_loc)
6771                 {
6772                   if (!REG_P (new_loc)
6773                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
6774                     new_loc = NULL;
6775                   else
6776                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
6777                 }
6778             }
6779           else if (MEM_P (loc[n_var_parts])
6780                    && GET_CODE (XEXP (loc2, 0)) == PLUS
6781                    && REG_P (XEXP (XEXP (loc2, 0), 0))
6782                    && CONST_INT_P (XEXP (XEXP (loc2, 0), 1)))
6783             {
6784               if ((REG_P (XEXP (loc[n_var_parts], 0))
6785                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
6786                                    XEXP (XEXP (loc2, 0), 0))
6787                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
6788                       == GET_MODE_SIZE (mode))
6789                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
6790                       && CONST_INT_P (XEXP (XEXP (loc[n_var_parts], 0), 1))
6791                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
6792                                       XEXP (XEXP (loc2, 0), 0))
6793                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
6794                          + GET_MODE_SIZE (mode)
6795                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
6796                 new_loc = adjust_address_nv (loc[n_var_parts],
6797                                              wider_mode, 0);
6798             }
6799
6800           if (new_loc)
6801             {
6802               loc[n_var_parts] = new_loc;
6803               mode = wider_mode;
6804               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
6805               i = j;
6806             }
6807         }
6808       ++n_var_parts;
6809     }
6810   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (decl));
6811   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
6812     complete = false;
6813
6814   if (! flag_var_tracking_uninit)
6815     initialized = VAR_INIT_STATUS_INITIALIZED;
6816
6817   note_vl = NULL_RTX;
6818   if (!complete)
6819     note_vl = gen_rtx_VAR_LOCATION (VOIDmode, decl, NULL_RTX,
6820                                     (int) initialized);
6821   else if (n_var_parts == 1)
6822     {
6823       rtx expr_list
6824         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
6825
6826       note_vl = gen_rtx_VAR_LOCATION (VOIDmode, decl, expr_list,
6827                                       (int) initialized);
6828     }
6829   else if (n_var_parts)
6830     {
6831       rtx parallel;
6832
6833       for (i = 0; i < n_var_parts; i++)
6834         loc[i]
6835           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
6836
6837       parallel = gen_rtx_PARALLEL (VOIDmode,
6838                                    gen_rtvec_v (n_var_parts, loc));
6839       note_vl = gen_rtx_VAR_LOCATION (VOIDmode, decl,
6840                                       parallel, (int) initialized);
6841     }
6842
6843 #ifdef ENABLE_RTL_CHECKING
6844   if (note_vl)
6845     {
6846       void **note_slot = pointer_map_insert (emitted_notes, decl);
6847       rtx pnote = (rtx) *note_slot;
6848       if (!var->cur_loc_changed && (pnote || PAT_VAR_LOCATION_LOC (note_vl)))
6849         {
6850           gcc_assert (pnote);
6851           gcc_assert (rtx_equal_p (PAT_VAR_LOCATION_LOC (pnote),
6852                                    PAT_VAR_LOCATION_LOC (note_vl)));
6853         }
6854       *note_slot = (void *) note_vl;
6855     }
6856   if (!var->cur_loc_changed)
6857     goto clear;
6858 #endif
6859
6860   if (where != EMIT_NOTE_BEFORE_INSN)
6861     {
6862       note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
6863       if (where == EMIT_NOTE_AFTER_CALL_INSN)
6864         NOTE_DURING_CALL_P (note) = true;
6865     }
6866   else
6867     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
6868   NOTE_VAR_LOCATION (note) = note_vl;
6869
6870  clear:
6871   set_dv_changed (var->dv, false);
6872   var->cur_loc_changed = false;
6873   gcc_assert (var->in_changed_variables);
6874   var->in_changed_variables = false;
6875   htab_clear_slot (changed_variables, varp);
6876
6877   /* Continue traversing the hash table.  */
6878   return 1;
6879
6880  value_or_debug_decl:
6881   if (dv_changed_p (var->dv) && var->n_var_parts)
6882     {
6883       location_chain lc;
6884       bool cur_loc_changed;
6885
6886       if (var->var_part[0].cur_loc
6887           && vt_expand_loc_dummy (var->var_part[0].cur_loc, vars,
6888                                   &cur_loc_changed))
6889         goto clear;
6890       for (lc = var->var_part[0].loc_chain; lc; lc = lc->next)
6891         if (lc->loc != var->var_part[0].cur_loc
6892             && vt_expand_loc_dummy (lc->loc, vars, &cur_loc_changed))
6893           break;
6894       var->var_part[0].cur_loc = lc ? lc->loc : NULL_RTX;
6895     }
6896   goto clear;
6897 }
6898
6899 DEF_VEC_P (variable);
6900 DEF_VEC_ALLOC_P (variable, heap);
6901
6902 /* Stack of variable_def pointers that need processing with
6903    check_changed_vars_2.  */
6904
6905 static VEC (variable, heap) *changed_variables_stack;
6906
6907 /* VALUEs with no variables that need set_dv_changed (val, false)
6908    called before check_changed_vars_3.  */
6909
6910 static VEC (rtx, heap) *changed_values_stack;
6911
6912 /* Helper function for check_changed_vars_1 and check_changed_vars_2.  */
6913
6914 static void
6915 check_changed_vars_0 (decl_or_value dv, htab_t htab)
6916 {
6917   value_chain vc
6918     = (value_chain) htab_find_with_hash (value_chains, dv, dv_htab_hash (dv));
6919
6920   if (vc == NULL)
6921     return;
6922   for (vc = vc->next; vc; vc = vc->next)
6923     if (!dv_changed_p (vc->dv))
6924       {
6925         variable vcvar
6926           = (variable) htab_find_with_hash (htab, vc->dv,
6927                                             dv_htab_hash (vc->dv));
6928         if (vcvar)
6929           {
6930             set_dv_changed (vc->dv, true);
6931             VEC_safe_push (variable, heap, changed_variables_stack, vcvar);
6932           }
6933         else if (dv_is_value_p (vc->dv))
6934           {
6935             set_dv_changed (vc->dv, true);
6936             VEC_safe_push (rtx, heap, changed_values_stack,
6937                            dv_as_value (vc->dv));
6938             check_changed_vars_0 (vc->dv, htab);
6939           }
6940       }
6941 }
6942
6943 /* Populate changed_variables_stack with variable_def pointers
6944    that need variable_was_changed called on them.  */
6945
6946 static int
6947 check_changed_vars_1 (void **slot, void *data)
6948 {
6949   variable var = (variable) *slot;
6950   htab_t htab = (htab_t) data;
6951
6952   if (dv_is_value_p (var->dv)
6953       || TREE_CODE (dv_as_decl (var->dv)) == DEBUG_EXPR_DECL)
6954     check_changed_vars_0 (var->dv, htab);
6955   return 1;
6956 }
6957
6958 /* Add VAR to changed_variables and also for VALUEs add recursively
6959    all DVs that aren't in changed_variables yet but reference the
6960    VALUE from its loc_chain.  */
6961
6962 static void
6963 check_changed_vars_2 (variable var, htab_t htab)
6964 {
6965   variable_was_changed (var, NULL);
6966   if (dv_is_value_p (var->dv)
6967       || TREE_CODE (dv_as_decl (var->dv)) == DEBUG_EXPR_DECL)
6968     check_changed_vars_0 (var->dv, htab);
6969 }
6970
6971 /* For each changed decl (except DEBUG_EXPR_DECLs) recompute
6972    cur_loc if needed (and cur_loc of all VALUEs and DEBUG_EXPR_DECLs
6973    it needs and are also in changed variables) and track whether
6974    cur_loc (or anything it uses to compute location) had to change
6975    during the current emit_notes_for_changes call.  */
6976
6977 static int
6978 check_changed_vars_3 (void **slot, void *data)
6979 {
6980   variable var = (variable) *slot;
6981   htab_t vars = (htab_t) data;
6982   int i;
6983   location_chain lc;
6984   bool cur_loc_changed;
6985
6986   if (dv_is_value_p (var->dv)
6987       || TREE_CODE (dv_as_decl (var->dv)) == DEBUG_EXPR_DECL)
6988     return 1;
6989
6990   for (i = 0; i < var->n_var_parts; i++)
6991     {
6992       if (var->var_part[i].cur_loc
6993           && vt_expand_loc_dummy (var->var_part[i].cur_loc, vars,
6994                                   &cur_loc_changed))
6995         {
6996           if (cur_loc_changed)
6997             var->cur_loc_changed = true;
6998           continue;
6999         }
7000       for (lc = var->var_part[i].loc_chain; lc; lc = lc->next)
7001         if (lc->loc != var->var_part[i].cur_loc
7002             && vt_expand_loc_dummy (lc->loc, vars, &cur_loc_changed))
7003           break;
7004       if (lc || var->var_part[i].cur_loc)
7005         var->cur_loc_changed = true;
7006       var->var_part[i].cur_loc = lc ? lc->loc : NULL_RTX;
7007     }
7008   if (var->n_var_parts == 0)
7009     var->cur_loc_changed = true;
7010   return 1;
7011 }
7012
7013 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
7014    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
7015    shall be emitted before of after instruction INSN.  */
7016
7017 static void
7018 emit_notes_for_changes (rtx insn, enum emit_note_where where,
7019                         shared_hash vars)
7020 {
7021   emit_note_data data;
7022   htab_t htab = shared_hash_htab (vars);
7023
7024   if (!htab_elements (changed_variables))
7025     return;
7026
7027   if (MAY_HAVE_DEBUG_INSNS)
7028     {
7029       /* Unfortunately this has to be done in two steps, because
7030          we can't traverse a hashtab into which we are inserting
7031          through variable_was_changed.  */
7032       htab_traverse (changed_variables, check_changed_vars_1, htab);
7033       while (VEC_length (variable, changed_variables_stack) > 0)
7034         check_changed_vars_2 (VEC_pop (variable, changed_variables_stack),
7035                               htab);
7036       while (VEC_length (rtx, changed_values_stack) > 0)
7037         set_dv_changed (dv_from_value (VEC_pop (rtx, changed_values_stack)),
7038                         false);
7039       htab_traverse (changed_variables, check_changed_vars_3, htab);
7040     }
7041
7042   data.insn = insn;
7043   data.where = where;
7044   data.vars = htab;
7045
7046   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
7047 }
7048
7049 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
7050    same variable in hash table DATA or is not there at all.  */
7051
7052 static int
7053 emit_notes_for_differences_1 (void **slot, void *data)
7054 {
7055   htab_t new_vars = (htab_t) data;
7056   variable old_var, new_var;
7057
7058   old_var = (variable) *slot;
7059   new_var = (variable) htab_find_with_hash (new_vars, old_var->dv,
7060                                             dv_htab_hash (old_var->dv));
7061
7062   if (!new_var)
7063     {
7064       /* Variable has disappeared.  */
7065       variable empty_var;
7066
7067       empty_var = (variable) pool_alloc (dv_pool (old_var->dv));
7068       empty_var->dv = old_var->dv;
7069       empty_var->refcount = 0;
7070       empty_var->n_var_parts = 0;
7071       empty_var->cur_loc_changed = false;
7072       empty_var->in_changed_variables = false;
7073       if (dv_onepart_p (old_var->dv))
7074         {
7075           location_chain lc;
7076
7077           gcc_assert (old_var->n_var_parts == 1);
7078           for (lc = old_var->var_part[0].loc_chain; lc; lc = lc->next)
7079             remove_value_chains (old_var->dv, lc->loc);
7080         }
7081       variable_was_changed (empty_var, NULL);
7082       /* Continue traversing the hash table.  */
7083       return 1;
7084     }
7085   if (variable_different_p (old_var, new_var))
7086     {
7087       if (dv_onepart_p (old_var->dv))
7088         {
7089           location_chain lc1, lc2;
7090
7091           gcc_assert (old_var->n_var_parts == 1);
7092           gcc_assert (new_var->n_var_parts == 1);
7093           lc1 = old_var->var_part[0].loc_chain;
7094           lc2 = new_var->var_part[0].loc_chain;
7095           while (lc1
7096                  && lc2
7097                  && ((REG_P (lc1->loc) && REG_P (lc2->loc))
7098                      || rtx_equal_p (lc1->loc, lc2->loc)))
7099             {
7100               lc1 = lc1->next;
7101               lc2 = lc2->next;
7102             }
7103           for (; lc2; lc2 = lc2->next)
7104             add_value_chains (old_var->dv, lc2->loc);
7105           for (; lc1; lc1 = lc1->next)
7106             remove_value_chains (old_var->dv, lc1->loc);
7107         }
7108       variable_was_changed (new_var, NULL);
7109     }
7110   /* Update cur_loc.  */
7111   if (old_var != new_var)
7112     {
7113       int i;
7114       for (i = 0; i < new_var->n_var_parts; i++)
7115         {
7116           new_var->var_part[i].cur_loc = NULL;
7117           if (old_var->n_var_parts != new_var->n_var_parts
7118               || old_var->var_part[i].offset != new_var->var_part[i].offset)
7119             new_var->cur_loc_changed = true;
7120           else if (old_var->var_part[i].cur_loc != NULL)
7121             {
7122               location_chain lc;
7123               rtx cur_loc = old_var->var_part[i].cur_loc;
7124
7125               for (lc = new_var->var_part[i].loc_chain; lc; lc = lc->next)
7126                 if (lc->loc == cur_loc
7127                     || rtx_equal_p (cur_loc, lc->loc))
7128                   {
7129                     new_var->var_part[i].cur_loc = lc->loc;
7130                     break;
7131                   }
7132               if (lc == NULL)
7133                 new_var->cur_loc_changed = true;
7134             }
7135         }
7136     }
7137
7138   /* Continue traversing the hash table.  */
7139   return 1;
7140 }
7141
7142 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
7143    table DATA.  */
7144
7145 static int
7146 emit_notes_for_differences_2 (void **slot, void *data)
7147 {
7148   htab_t old_vars = (htab_t) data;
7149   variable old_var, new_var;
7150
7151   new_var = (variable) *slot;
7152   old_var = (variable) htab_find_with_hash (old_vars, new_var->dv,
7153                                             dv_htab_hash (new_var->dv));
7154   if (!old_var)
7155     {
7156       int i;
7157       /* Variable has appeared.  */
7158       if (dv_onepart_p (new_var->dv))
7159         {
7160           location_chain lc;
7161
7162           gcc_assert (new_var->n_var_parts == 1);
7163           for (lc = new_var->var_part[0].loc_chain; lc; lc = lc->next)
7164             add_value_chains (new_var->dv, lc->loc);
7165         }
7166       for (i = 0; i < new_var->n_var_parts; i++)
7167         new_var->var_part[i].cur_loc = NULL;
7168       variable_was_changed (new_var, NULL);
7169     }
7170
7171   /* Continue traversing the hash table.  */
7172   return 1;
7173 }
7174
7175 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
7176    NEW_SET.  */
7177
7178 static void
7179 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
7180                             dataflow_set *new_set)
7181 {
7182   htab_traverse (shared_hash_htab (old_set->vars),
7183                  emit_notes_for_differences_1,
7184                  shared_hash_htab (new_set->vars));
7185   htab_traverse (shared_hash_htab (new_set->vars),
7186                  emit_notes_for_differences_2,
7187                  shared_hash_htab (old_set->vars));
7188   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, new_set->vars);
7189 }
7190
7191 /* Emit the notes for changes of location parts in the basic block BB.  */
7192
7193 static void
7194 emit_notes_in_bb (basic_block bb, dataflow_set *set)
7195 {
7196   unsigned int i;
7197   micro_operation *mo;
7198
7199   dataflow_set_clear (set);
7200   dataflow_set_copy (set, &VTI (bb)->in);
7201
7202   for (i = 0; VEC_iterate (micro_operation, VTI (bb)->mos, i, mo); i++)
7203     {
7204       rtx insn = mo->insn;
7205
7206       switch (mo->type)
7207         {
7208           case MO_CALL:
7209             dataflow_set_clear_at_call (set);
7210             emit_notes_for_changes (insn, EMIT_NOTE_AFTER_CALL_INSN, set->vars);
7211             break;
7212
7213           case MO_USE:
7214             {
7215               rtx loc = mo->u.loc;
7216
7217               if (REG_P (loc))
7218                 var_reg_set (set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
7219               else
7220                 var_mem_set (set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
7221
7222               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
7223             }
7224             break;
7225
7226           case MO_VAL_LOC:
7227             {
7228               rtx loc = mo->u.loc;
7229               rtx val, vloc;
7230               tree var;
7231
7232               if (GET_CODE (loc) == CONCAT)
7233                 {
7234                   val = XEXP (loc, 0);
7235                   vloc = XEXP (loc, 1);
7236                 }
7237               else
7238                 {
7239                   val = NULL_RTX;
7240                   vloc = loc;
7241                 }
7242
7243               var = PAT_VAR_LOCATION_DECL (vloc);
7244
7245               clobber_variable_part (set, NULL_RTX,
7246                                      dv_from_decl (var), 0, NULL_RTX);
7247               if (val)
7248                 {
7249                   if (VAL_NEEDS_RESOLUTION (loc))
7250                     val_resolve (set, val, PAT_VAR_LOCATION_LOC (vloc), insn);
7251                   set_variable_part (set, val, dv_from_decl (var), 0,
7252                                      VAR_INIT_STATUS_INITIALIZED, NULL_RTX,
7253                                      INSERT);
7254                 }
7255
7256               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
7257             }
7258             break;
7259
7260           case MO_VAL_USE:
7261             {
7262               rtx loc = mo->u.loc;
7263               rtx val, vloc, uloc;
7264
7265               vloc = uloc = XEXP (loc, 1);
7266               val = XEXP (loc, 0);
7267
7268               if (GET_CODE (val) == CONCAT)
7269                 {
7270                   uloc = XEXP (val, 1);
7271                   val = XEXP (val, 0);
7272                 }
7273
7274               if (VAL_NEEDS_RESOLUTION (loc))
7275                 val_resolve (set, val, vloc, insn);
7276               else
7277                 val_store (set, val, uloc, insn, false);
7278
7279               if (VAL_HOLDS_TRACK_EXPR (loc))
7280                 {
7281                   if (GET_CODE (uloc) == REG)
7282                     var_reg_set (set, uloc, VAR_INIT_STATUS_UNINITIALIZED,
7283                                  NULL);
7284                   else if (GET_CODE (uloc) == MEM)
7285                     var_mem_set (set, uloc, VAR_INIT_STATUS_UNINITIALIZED,
7286                                  NULL);
7287                 }
7288
7289               emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, set->vars);
7290             }
7291             break;
7292
7293           case MO_VAL_SET:
7294             {
7295               rtx loc = mo->u.loc;
7296               rtx val, vloc, uloc, reverse = NULL_RTX;
7297
7298               vloc = loc;
7299               if (VAL_EXPR_HAS_REVERSE (loc))
7300                 {
7301                   reverse = XEXP (loc, 1);
7302                   vloc = XEXP (loc, 0);
7303                 }
7304               uloc = XEXP (vloc, 1);
7305               val = XEXP (vloc, 0);
7306               vloc = uloc;
7307
7308               if (GET_CODE (val) == CONCAT)
7309                 {
7310                   vloc = XEXP (val, 1);
7311                   val = XEXP (val, 0);
7312                 }
7313
7314               if (GET_CODE (vloc) == SET)
7315                 {
7316                   rtx vsrc = SET_SRC (vloc);
7317
7318                   gcc_assert (val != vsrc);
7319                   gcc_assert (vloc == uloc || VAL_NEEDS_RESOLUTION (loc));
7320
7321                   vloc = SET_DEST (vloc);
7322
7323                   if (VAL_NEEDS_RESOLUTION (loc))
7324                     val_resolve (set, val, vsrc, insn);
7325                 }
7326               else if (VAL_NEEDS_RESOLUTION (loc))
7327                 {
7328                   gcc_assert (GET_CODE (uloc) == SET
7329                               && GET_CODE (SET_SRC (uloc)) == REG);
7330                   val_resolve (set, val, SET_SRC (uloc), insn);
7331                 }
7332
7333               if (VAL_HOLDS_TRACK_EXPR (loc))
7334                 {
7335                   if (VAL_EXPR_IS_CLOBBERED (loc))
7336                     {
7337                       if (REG_P (uloc))
7338                         var_reg_delete (set, uloc, true);
7339                       else if (MEM_P (uloc))
7340                         var_mem_delete (set, uloc, true);
7341                     }
7342                   else
7343                     {
7344                       bool copied_p = VAL_EXPR_IS_COPIED (loc);
7345                       rtx set_src = NULL;
7346                       enum var_init_status status = VAR_INIT_STATUS_INITIALIZED;
7347
7348                       if (GET_CODE (uloc) == SET)
7349                         {
7350                           set_src = SET_SRC (uloc);
7351                           uloc = SET_DEST (uloc);
7352                         }
7353
7354                       if (copied_p)
7355                         {
7356                           status = find_src_status (set, set_src);
7357
7358                           set_src = find_src_set_src (set, set_src);
7359                         }
7360
7361                       if (REG_P (uloc))
7362                         var_reg_delete_and_set (set, uloc, !copied_p,
7363                                                 status, set_src);
7364                       else if (MEM_P (uloc))
7365                         var_mem_delete_and_set (set, uloc, !copied_p,
7366                                                 status, set_src);
7367                     }
7368                 }
7369               else if (REG_P (uloc))
7370                 var_regno_delete (set, REGNO (uloc));
7371
7372               val_store (set, val, vloc, insn, true);
7373
7374               if (reverse)
7375                 val_store (set, XEXP (reverse, 0), XEXP (reverse, 1),
7376                            insn, false);
7377
7378               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7379                                       set->vars);
7380             }
7381             break;
7382
7383           case MO_SET:
7384             {
7385               rtx loc = mo->u.loc;
7386               rtx set_src = NULL;
7387
7388               if (GET_CODE (loc) == SET)
7389                 {
7390                   set_src = SET_SRC (loc);
7391                   loc = SET_DEST (loc);
7392                 }
7393
7394               if (REG_P (loc))
7395                 var_reg_delete_and_set (set, loc, true, VAR_INIT_STATUS_INITIALIZED,
7396                                         set_src);
7397               else
7398                 var_mem_delete_and_set (set, loc, true, VAR_INIT_STATUS_INITIALIZED,
7399                                         set_src);
7400
7401               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7402                                       set->vars);
7403             }
7404             break;
7405
7406           case MO_COPY:
7407             {
7408               rtx loc = mo->u.loc;
7409               enum var_init_status src_status;
7410               rtx set_src = NULL;
7411
7412               if (GET_CODE (loc) == SET)
7413                 {
7414                   set_src = SET_SRC (loc);
7415                   loc = SET_DEST (loc);
7416                 }
7417
7418               src_status = find_src_status (set, set_src);
7419               set_src = find_src_set_src (set, set_src);
7420
7421               if (REG_P (loc))
7422                 var_reg_delete_and_set (set, loc, false, src_status, set_src);
7423               else
7424                 var_mem_delete_and_set (set, loc, false, src_status, set_src);
7425
7426               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7427                                       set->vars);
7428             }
7429             break;
7430
7431           case MO_USE_NO_VAR:
7432             {
7433               rtx loc = mo->u.loc;
7434
7435               if (REG_P (loc))
7436                 var_reg_delete (set, loc, false);
7437               else
7438                 var_mem_delete (set, loc, false);
7439
7440               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
7441             }
7442             break;
7443
7444           case MO_CLOBBER:
7445             {
7446               rtx loc = mo->u.loc;
7447
7448               if (REG_P (loc))
7449                 var_reg_delete (set, loc, true);
7450               else
7451                 var_mem_delete (set, loc, true);
7452
7453               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7454                                       set->vars);
7455             }
7456             break;
7457
7458           case MO_ADJUST:
7459             set->stack_adjust += mo->u.adjust;
7460             break;
7461         }
7462     }
7463 }
7464
7465 /* Emit notes for the whole function.  */
7466
7467 static void
7468 vt_emit_notes (void)
7469 {
7470   basic_block bb;
7471   dataflow_set cur;
7472
7473 #ifdef ENABLE_RTL_CHECKING
7474   emitted_notes = pointer_map_create ();
7475 #endif
7476   gcc_assert (!htab_elements (changed_variables));
7477
7478   /* Free memory occupied by the out hash tables, as they aren't used
7479      anymore.  */
7480   FOR_EACH_BB (bb)
7481     dataflow_set_clear (&VTI (bb)->out);
7482
7483   /* Enable emitting notes by functions (mainly by set_variable_part and
7484      delete_variable_part).  */
7485   emit_notes = true;
7486
7487   if (MAY_HAVE_DEBUG_INSNS)
7488     {
7489       unsigned int i;
7490       rtx val;
7491
7492       for (i = 0; VEC_iterate (rtx, preserved_values, i, val); i++)
7493         add_cselib_value_chains (dv_from_value (val));
7494       changed_variables_stack = VEC_alloc (variable, heap, 40);
7495       changed_values_stack = VEC_alloc (rtx, heap, 40);
7496     }
7497
7498   dataflow_set_init (&cur);
7499
7500   FOR_EACH_BB (bb)
7501     {
7502       /* Emit the notes for changes of variable locations between two
7503          subsequent basic blocks.  */
7504       emit_notes_for_differences (BB_HEAD (bb), &cur, &VTI (bb)->in);
7505
7506       /* Emit the notes for the changes in the basic block itself.  */
7507       emit_notes_in_bb (bb, &cur);
7508
7509       /* Free memory occupied by the in hash table, we won't need it
7510          again.  */
7511       dataflow_set_clear (&VTI (bb)->in);
7512     }
7513 #ifdef ENABLE_CHECKING
7514   htab_traverse (shared_hash_htab (cur.vars),
7515                  emit_notes_for_differences_1,
7516                  shared_hash_htab (empty_shared_hash));
7517   if (MAY_HAVE_DEBUG_INSNS)
7518     {
7519       unsigned int i;
7520       rtx val;
7521
7522       for (i = 0; VEC_iterate (rtx, preserved_values, i, val); i++)
7523         remove_cselib_value_chains (dv_from_value (val));
7524       gcc_assert (htab_elements (value_chains) == 0);
7525     }
7526 #endif
7527   dataflow_set_destroy (&cur);
7528
7529   if (MAY_HAVE_DEBUG_INSNS)
7530     {
7531       VEC_free (variable, heap, changed_variables_stack);
7532       VEC_free (rtx, heap, changed_values_stack);
7533     }
7534
7535 #ifdef ENABLE_RTL_CHECKING
7536   pointer_map_destroy (emitted_notes);
7537 #endif
7538   emit_notes = false;
7539 }
7540
7541 /* If there is a declaration and offset associated with register/memory RTL
7542    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
7543
7544 static bool
7545 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
7546 {
7547   if (REG_P (rtl))
7548     {
7549       if (REG_ATTRS (rtl))
7550         {
7551           *declp = REG_EXPR (rtl);
7552           *offsetp = REG_OFFSET (rtl);
7553           return true;
7554         }
7555     }
7556   else if (MEM_P (rtl))
7557     {
7558       if (MEM_ATTRS (rtl))
7559         {
7560           *declp = MEM_EXPR (rtl);
7561           *offsetp = INT_MEM_OFFSET (rtl);
7562           return true;
7563         }
7564     }
7565   return false;
7566 }
7567
7568 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
7569
7570 static void
7571 vt_add_function_parameters (void)
7572 {
7573   tree parm;
7574
7575   for (parm = DECL_ARGUMENTS (current_function_decl);
7576        parm; parm = TREE_CHAIN (parm))
7577     {
7578       rtx decl_rtl = DECL_RTL_IF_SET (parm);
7579       rtx incoming = DECL_INCOMING_RTL (parm);
7580       tree decl;
7581       enum machine_mode mode;
7582       HOST_WIDE_INT offset;
7583       dataflow_set *out;
7584       decl_or_value dv;
7585
7586       if (TREE_CODE (parm) != PARM_DECL)
7587         continue;
7588
7589       if (!DECL_NAME (parm))
7590         continue;
7591
7592       if (!decl_rtl || !incoming)
7593         continue;
7594
7595       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
7596         continue;
7597
7598       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
7599         {
7600           if (REG_P (incoming) || MEM_P (incoming))
7601             {
7602               /* This means argument is passed by invisible reference.  */
7603               offset = 0;
7604               decl = parm;
7605               incoming = gen_rtx_MEM (GET_MODE (decl_rtl), incoming);
7606             }
7607           else
7608             {
7609               if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
7610                 continue;
7611               offset += byte_lowpart_offset (GET_MODE (incoming),
7612                                              GET_MODE (decl_rtl));
7613             }
7614         }
7615
7616       if (!decl)
7617         continue;
7618
7619       if (parm != decl)
7620         {
7621           /* Assume that DECL_RTL was a pseudo that got spilled to
7622              memory.  The spill slot sharing code will force the
7623              memory to reference spill_slot_decl (%sfp), so we don't
7624              match above.  That's ok, the pseudo must have referenced
7625              the entire parameter, so just reset OFFSET.  */
7626           gcc_assert (decl == get_spill_slot_decl (false));
7627           offset = 0;
7628         }
7629
7630       if (!track_loc_p (incoming, parm, offset, false, &mode, &offset))
7631         continue;
7632
7633       out = &VTI (ENTRY_BLOCK_PTR)->out;
7634
7635       dv = dv_from_decl (parm);
7636
7637       if (target_for_debug_bind (parm)
7638           /* We can't deal with these right now, because this kind of
7639              variable is single-part.  ??? We could handle parallels
7640              that describe multiple locations for the same single
7641              value, but ATM we don't.  */
7642           && GET_CODE (incoming) != PARALLEL)
7643         {
7644           cselib_val *val;
7645
7646           /* ??? We shouldn't ever hit this, but it may happen because
7647              arguments passed by invisible reference aren't dealt with
7648              above: incoming-rtl will have Pmode rather than the
7649              expected mode for the type.  */
7650           if (offset)
7651             continue;
7652
7653           val = cselib_lookup (var_lowpart (mode, incoming), mode, true);
7654
7655           /* ??? Float-typed values in memory are not handled by
7656              cselib.  */
7657           if (val)
7658             {
7659               preserve_value (val);
7660               set_variable_part (out, val->val_rtx, dv, offset,
7661                                  VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7662               dv = dv_from_value (val->val_rtx);
7663             }
7664         }
7665
7666       if (REG_P (incoming))
7667         {
7668           incoming = var_lowpart (mode, incoming);
7669           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
7670           attrs_list_insert (&out->regs[REGNO (incoming)], dv, offset,
7671                              incoming);
7672           set_variable_part (out, incoming, dv, offset,
7673                              VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7674         }
7675       else if (MEM_P (incoming))
7676         {
7677           incoming = var_lowpart (mode, incoming);
7678           set_variable_part (out, incoming, dv, offset,
7679                              VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7680         }
7681     }
7682
7683   if (MAY_HAVE_DEBUG_INSNS)
7684     {
7685       cselib_preserve_only_values ();
7686       cselib_reset_table (cselib_get_next_uid ());
7687     }
7688
7689 }
7690
7691 /* Allocate and initialize the data structures for variable tracking
7692    and parse the RTL to get the micro operations.  */
7693
7694 static void
7695 vt_initialize (void)
7696 {
7697   basic_block bb;
7698
7699   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
7700
7701   if (MAY_HAVE_DEBUG_INSNS)
7702     {
7703       cselib_init (true);
7704       scratch_regs = BITMAP_ALLOC (NULL);
7705       valvar_pool = create_alloc_pool ("small variable_def pool",
7706                                        sizeof (struct variable_def), 256);
7707       preserved_values = VEC_alloc (rtx, heap, 256);
7708     }
7709   else
7710     {
7711       scratch_regs = NULL;
7712       valvar_pool = NULL;
7713     }
7714
7715   FOR_EACH_BB (bb)
7716     {
7717       rtx insn;
7718       HOST_WIDE_INT pre, post = 0;
7719       basic_block first_bb, last_bb;
7720
7721       if (MAY_HAVE_DEBUG_INSNS)
7722         {
7723           cselib_record_sets_hook = add_with_sets;
7724           if (dump_file && (dump_flags & TDF_DETAILS))
7725             fprintf (dump_file, "first value: %i\n",
7726                      cselib_get_next_uid ());
7727         }
7728
7729       first_bb = bb;
7730       for (;;)
7731         {
7732           edge e;
7733           if (bb->next_bb == EXIT_BLOCK_PTR
7734               || ! single_pred_p (bb->next_bb))
7735             break;
7736           e = find_edge (bb, bb->next_bb);
7737           if (! e || (e->flags & EDGE_FALLTHRU) == 0)
7738             break;
7739           bb = bb->next_bb;
7740         }
7741       last_bb = bb;
7742
7743       /* Add the micro-operations to the vector.  */
7744       FOR_BB_BETWEEN (bb, first_bb, last_bb->next_bb, next_bb)
7745         {
7746           for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
7747                insn = NEXT_INSN (insn))
7748             {
7749               if (INSN_P (insn))
7750                 {
7751                   if (!frame_pointer_needed)
7752                     {
7753                       insn_stack_adjust_offset_pre_post (insn, &pre, &post);
7754                       if (pre)
7755                         {
7756                           micro_operation mo;
7757                           mo.type = MO_ADJUST;
7758                           mo.u.adjust = pre;
7759                           mo.insn = insn;
7760                           VEC_safe_push (micro_operation, heap, VTI (bb)->mos,
7761                                          &mo);
7762
7763                           if (dump_file && (dump_flags & TDF_DETAILS))
7764                             log_op_type (PATTERN (insn), bb, insn,
7765                                          MO_ADJUST, dump_file);
7766                         }
7767                     }
7768
7769                   cselib_hook_called = false;
7770                   if (MAY_HAVE_DEBUG_INSNS)
7771                     {
7772                       cselib_process_insn (insn);
7773                       if (dump_file && (dump_flags & TDF_DETAILS))
7774                         {
7775                           print_rtl_single (dump_file, insn);
7776                           dump_cselib_table (dump_file);
7777                         }
7778                     }
7779                   if (!cselib_hook_called)
7780                     add_with_sets (insn, 0, 0);
7781
7782                   if (!frame_pointer_needed && post)
7783                     {
7784                       micro_operation mo;
7785                       mo.type = MO_ADJUST;
7786                       mo.u.adjust = post;
7787                       mo.insn = insn;
7788                       VEC_safe_push (micro_operation, heap, VTI (bb)->mos,
7789                                      &mo);
7790
7791                       if (dump_file && (dump_flags & TDF_DETAILS))
7792                         log_op_type (PATTERN (insn), bb, insn,
7793                                      MO_ADJUST, dump_file);
7794                     }
7795                 }
7796             }
7797         }
7798
7799       bb = last_bb;
7800
7801       if (MAY_HAVE_DEBUG_INSNS)
7802         {
7803           cselib_preserve_only_values ();
7804           cselib_reset_table (cselib_get_next_uid ());
7805           cselib_record_sets_hook = NULL;
7806         }
7807     }
7808
7809   attrs_pool = create_alloc_pool ("attrs_def pool",
7810                                   sizeof (struct attrs_def), 1024);
7811   var_pool = create_alloc_pool ("variable_def pool",
7812                                 sizeof (struct variable_def)
7813                                 + (MAX_VAR_PARTS - 1)
7814                                 * sizeof (((variable)NULL)->var_part[0]), 64);
7815   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
7816                                       sizeof (struct location_chain_def),
7817                                       1024);
7818   shared_hash_pool = create_alloc_pool ("shared_hash_def pool",
7819                                         sizeof (struct shared_hash_def), 256);
7820   empty_shared_hash = (shared_hash) pool_alloc (shared_hash_pool);
7821   empty_shared_hash->refcount = 1;
7822   empty_shared_hash->htab
7823     = htab_create (1, variable_htab_hash, variable_htab_eq,
7824                    variable_htab_free);
7825   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
7826                                    variable_htab_free);
7827   if (MAY_HAVE_DEBUG_INSNS)
7828     {
7829       value_chain_pool = create_alloc_pool ("value_chain_def pool",
7830                                             sizeof (struct value_chain_def),
7831                                             1024);
7832       value_chains = htab_create (32, value_chain_htab_hash,
7833                                   value_chain_htab_eq, NULL);
7834     }
7835
7836   /* Init the IN and OUT sets.  */
7837   FOR_ALL_BB (bb)
7838     {
7839       VTI (bb)->visited = false;
7840       VTI (bb)->flooded = false;
7841       dataflow_set_init (&VTI (bb)->in);
7842       dataflow_set_init (&VTI (bb)->out);
7843       VTI (bb)->permp = NULL;
7844     }
7845
7846   VTI (ENTRY_BLOCK_PTR)->flooded = true;
7847   vt_add_function_parameters ();
7848 }
7849
7850 /* Get rid of all debug insns from the insn stream.  */
7851
7852 static void
7853 delete_debug_insns (void)
7854 {
7855   basic_block bb;
7856   rtx insn, next;
7857
7858   if (!MAY_HAVE_DEBUG_INSNS)
7859     return;
7860
7861   FOR_EACH_BB (bb)
7862     {
7863       FOR_BB_INSNS_SAFE (bb, insn, next)
7864         if (DEBUG_INSN_P (insn))
7865           delete_insn (insn);
7866     }
7867 }
7868
7869 /* Run a fast, BB-local only version of var tracking, to take care of
7870    information that we don't do global analysis on, such that not all
7871    information is lost.  If SKIPPED holds, we're skipping the global
7872    pass entirely, so we should try to use information it would have
7873    handled as well..  */
7874
7875 static void
7876 vt_debug_insns_local (bool skipped ATTRIBUTE_UNUSED)
7877 {
7878   /* ??? Just skip it all for now.  */
7879   delete_debug_insns ();
7880 }
7881
7882 /* Free the data structures needed for variable tracking.  */
7883
7884 static void
7885 vt_finalize (void)
7886 {
7887   basic_block bb;
7888
7889   FOR_EACH_BB (bb)
7890     {
7891       VEC_free (micro_operation, heap, VTI (bb)->mos);
7892     }
7893
7894   FOR_ALL_BB (bb)
7895     {
7896       dataflow_set_destroy (&VTI (bb)->in);
7897       dataflow_set_destroy (&VTI (bb)->out);
7898       if (VTI (bb)->permp)
7899         {
7900           dataflow_set_destroy (VTI (bb)->permp);
7901           XDELETE (VTI (bb)->permp);
7902         }
7903     }
7904   free_aux_for_blocks ();
7905   htab_delete (empty_shared_hash->htab);
7906   htab_delete (changed_variables);
7907   free_alloc_pool (attrs_pool);
7908   free_alloc_pool (var_pool);
7909   free_alloc_pool (loc_chain_pool);
7910   free_alloc_pool (shared_hash_pool);
7911
7912   if (MAY_HAVE_DEBUG_INSNS)
7913     {
7914       htab_delete (value_chains);
7915       free_alloc_pool (value_chain_pool);
7916       free_alloc_pool (valvar_pool);
7917       VEC_free (rtx, heap, preserved_values);
7918       cselib_finish ();
7919       BITMAP_FREE (scratch_regs);
7920       scratch_regs = NULL;
7921     }
7922
7923   if (vui_vec)
7924     XDELETEVEC (vui_vec);
7925   vui_vec = NULL;
7926   vui_allocated = 0;
7927 }
7928
7929 /* The entry point to variable tracking pass.  */
7930
7931 static inline unsigned int
7932 variable_tracking_main_1 (void)
7933 {
7934   bool success;
7935
7936   if (flag_var_tracking_assignments < 0)
7937     {
7938       delete_debug_insns ();
7939       return 0;
7940     }
7941
7942   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
7943     {
7944       vt_debug_insns_local (true);
7945       return 0;
7946     }
7947
7948   mark_dfs_back_edges ();
7949   vt_initialize ();
7950   if (!frame_pointer_needed)
7951     {
7952       if (!vt_stack_adjustments ())
7953         {
7954           vt_finalize ();
7955           vt_debug_insns_local (true);
7956           return 0;
7957         }
7958     }
7959
7960   success = vt_find_locations ();
7961
7962   if (!success && flag_var_tracking_assignments > 0)
7963     {
7964       vt_finalize ();
7965
7966       delete_debug_insns ();
7967
7968       /* This is later restored by our caller.  */
7969       flag_var_tracking_assignments = 0;
7970
7971       vt_initialize ();
7972
7973       if (!frame_pointer_needed && !vt_stack_adjustments ())
7974         gcc_unreachable ();
7975
7976       success = vt_find_locations ();
7977     }
7978
7979   if (!success)
7980     {
7981       vt_finalize ();
7982       vt_debug_insns_local (false);
7983       return 0;
7984     }
7985
7986   if (dump_file && (dump_flags & TDF_DETAILS))
7987     {
7988       dump_dataflow_sets ();
7989       dump_flow_info (dump_file, dump_flags);
7990     }
7991
7992   vt_emit_notes ();
7993
7994   vt_finalize ();
7995   vt_debug_insns_local (false);
7996   return 0;
7997 }
7998
7999 unsigned int
8000 variable_tracking_main (void)
8001 {
8002   unsigned int ret;
8003   int save = flag_var_tracking_assignments;
8004
8005   ret = variable_tracking_main_1 ();
8006
8007   flag_var_tracking_assignments = save;
8008
8009   return ret;
8010 }
8011 \f
8012 static bool
8013 gate_handle_var_tracking (void)
8014 {
8015   return (flag_var_tracking);
8016 }
8017
8018
8019
8020 struct rtl_opt_pass pass_variable_tracking =
8021 {
8022  {
8023   RTL_PASS,
8024   "vartrack",                           /* name */
8025   gate_handle_var_tracking,             /* gate */
8026   variable_tracking_main,               /* execute */
8027   NULL,                                 /* sub */
8028   NULL,                                 /* next */
8029   0,                                    /* static_pass_number */
8030   TV_VAR_TRACKING,                      /* tv_id */
8031   0,                                    /* properties_required */
8032   0,                                    /* properties_provided */
8033   0,                                    /* properties_destroyed */
8034   0,                                    /* todo_flags_start */
8035   TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */
8036  }
8037 };