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
 115 /* var-tracking.c assumes that tree code with the same value as VALUE rtx code
 116    has no chance to appear in REG_EXPR/MEM_EXPRs and isn't a decl.
 117    Currently the value is the same as IDENTIFIER_NODE, which has such
 118    a property.  If this compile time assertion ever fails, make sure that
 119    the new tree code that equals (int) VALUE has the same property.  */
 120 extern char check_value_val[(int) VALUE == (int) IDENTIFIER_NODE ? 1 : -1];
 121
 122 /* Type of micro operation.  */
 123 enum micro_operation_type
 124 {
 125   MO_USE,       /* Use location (REG or MEM).  */
 126   MO_USE_NO_VAR,/* Use location which is not associated with a variable
 127                    or the variable is not trackable.  */
 128   MO_VAL_USE,   /* Use location which is associated with a value.  */
 129   MO_VAL_LOC,   /* Use location which appears in a debug insn.  */
 130   MO_VAL_SET,   /* Set location associated with a value.  */
 131   MO_SET,       /* Set location.  */
 132   MO_COPY,      /* Copy the same portion of a variable from one
 133                    location to another.  */
 134   MO_CLOBBER,   /* Clobber location.  */
 135   MO_CALL,      /* Call insn.  */
 136   MO_ADJUST     /* Adjust stack pointer.  */
 137
 138 };
 139
 140 static const char * const ATTRIBUTE_UNUSED
 141 micro_operation_type_name[] = {
 142   "MO_USE",
 143   "MO_USE_NO_VAR",
 144   "MO_VAL_USE",
 145   "MO_VAL_LOC",
 146   "MO_VAL_SET",
 147   "MO_SET",
 148   "MO_COPY",
 149   "MO_CLOBBER",
 150   "MO_CALL",
 151   "MO_ADJUST"
 152 };
 153
 154 /* Where shall the note be emitted?  BEFORE or AFTER the instruction.
 155    Notes emitted as AFTER_CALL are to take effect during the call,
 156    rather than after the call.  */
 157 enum emit_note_where
 158 {
 159   EMIT_NOTE_BEFORE_INSN,
 160   EMIT_NOTE_AFTER_INSN,
 161   EMIT_NOTE_AFTER_CALL_INSN
 162 };
 163
 164 /* Structure holding information about micro operation.  */
 165 typedef struct micro_operation_def
 166 {
 167   /* Type of micro operation.  */
 168   enum micro_operation_type type;
 169
 170   union {
 171     /* Location.  For MO_SET and MO_COPY, this is the SET that
 172        performs the assignment, if known, otherwise it is the target
 173        of the assignment.  For MO_VAL_USE and MO_VAL_SET, it is a
 174        CONCAT of the VALUE and the LOC associated with it.  For
 175        MO_VAL_LOC, it is a CONCAT of the VALUE and the VAR_LOCATION
 176        associated with it.  */
 177     rtx loc;
 178
 179     /* Stack adjustment.  */
 180     HOST_WIDE_INT adjust;
 181   } u;
 182
 183   /* The instruction which the micro operation is in, for MO_USE,
 184      MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent
 185      instruction or note in the original flow (before any var-tracking
 186      notes are inserted, to simplify emission of notes), for MO_SET
 187      and MO_CLOBBER.  */
 188   rtx insn;
 189 } micro_operation;
 190
 191 /* A declaration of a variable, or an RTL value being handled like a
 192    declaration.  */
 193 typedef void *decl_or_value;
 194
 195 /* Structure for passing some other parameters to function
 196    emit_note_insn_var_location.  */
 197 typedef struct emit_note_data_def
 198 {
 199   /* The instruction which the note will be emitted before/after.  */
 200   rtx insn;
 201
 202   /* Where the note will be emitted (before/after insn)?  */
 203   enum emit_note_where where;
 204
 205   /* The variables and values active at this point.  */
 206   htab_t vars;
 207 } emit_note_data;
 208
 209 /* Description of location of a part of a variable.  The content of a physical
 210    register is described by a chain of these structures.
 211    The chains are pretty short (usually 1 or 2 elements) and thus
 212    chain is the best data structure.  */
 213 typedef struct attrs_def
 214 {
 215   /* Pointer to next member of the list.  */
 216   struct attrs_def *next;
 217
 218   /* The rtx of register.  */
 219   rtx loc;
 220
 221   /* The declaration corresponding to LOC.  */
 222   decl_or_value dv;
 223
 224   /* Offset from start of DECL.  */
 225   HOST_WIDE_INT offset;
 226 } *attrs;
 227
 228 /* Structure holding a refcounted hash table.  If refcount > 1,
 229    it must be first unshared before modified.  */
 230 typedef struct shared_hash_def
 231 {
 232   /* Reference count.  */
 233   int refcount;
 234
 235   /* Actual hash table.  */
 236   htab_t htab;
 237 } *shared_hash;
 238
 239 /* Structure holding the IN or OUT set for a basic block.  */
 240 typedef struct dataflow_set_def
 241 {
 242   /* Adjustment of stack offset.  */
 243   HOST_WIDE_INT stack_adjust;
 244
 245   /* Attributes for registers (lists of attrs).  */
 246   attrs regs[FIRST_PSEUDO_REGISTER];
 247
 248   /* Variable locations.  */
 249   shared_hash vars;
 250
 251   /* Vars that is being traversed.  */
 252   shared_hash traversed_vars;
 253 } dataflow_set;
 254
 255 /* The structure (one for each basic block) containing the information
 256    needed for variable tracking.  */
 257 typedef struct variable_tracking_info_def
 258 {
 259   /* Number of micro operations stored in the MOS array.  */
 260   int n_mos;
 261
 262   /* The array of micro operations.  */
 263   micro_operation *mos;
 264
 265   /* The IN and OUT set for dataflow analysis.  */
 266   dataflow_set in;
 267   dataflow_set out;
 268
 269   /* The permanent-in dataflow set for this block.  This is used to
 270      hold values for which we had to compute entry values.  ??? This
 271      should probably be dynamically allocated, to avoid using more
 272      memory in non-debug builds.  */
 273   dataflow_set *permp;
 274
 275   /* Has the block been visited in DFS?  */
 276   bool visited;
 277
 278   /* Has the block been flooded in VTA?  */
 279   bool flooded;
 280
 281 } *variable_tracking_info;
 282
 283 /* Structure for chaining the locations.  */
 284 typedef struct location_chain_def
 285 {
 286   /* Next element in the chain.  */
 287   struct location_chain_def *next;
 288
 289   /* The location (REG, MEM or VALUE).  */
 290   rtx loc;
 291
 292   /* The "value" stored in this location.  */
 293   rtx set_src;
 294
 295   /* Initialized? */
 296   enum var_init_status init;
 297 } *location_chain;
 298
 299 /* Structure describing one part of variable.  */
 300 typedef struct variable_part_def
 301 {
 302   /* Chain of locations of the part.  */
 303   location_chain loc_chain;
 304
 305   /* Location which was last emitted to location list.  */
 306   rtx cur_loc;
 307
 308   /* The offset in the variable.  */
 309   HOST_WIDE_INT offset;
 310 } variable_part;
 311
 312 /* Maximum number of location parts.  */
 313 #define MAX_VAR_PARTS 16
 314
 315 /* Structure describing where the variable is located.  */
 316 typedef struct variable_def
 317 {
 318   /* The declaration of the variable, or an RTL value being handled
 319      like a declaration.  */
 320   decl_or_value dv;
 321
 322   /* Reference count.  */
 323   int refcount;
 324
 325   /* Number of variable parts.  */
 326   int n_var_parts;
 327
 328   /* The variable parts.  */
 329   variable_part var_part[1];
 330 } *variable;
 331 typedef const struct variable_def *const_variable;
 332
 333 /* Structure for chaining backlinks from referenced VALUEs to
 334    DVs that are referencing them.  */
 335 typedef struct value_chain_def
 336 {
 337   /* Next value_chain entry.  */
 338   struct value_chain_def *next;
 339
 340   /* The declaration of the variable, or an RTL value
 341      being handled like a declaration, whose var_parts[0].loc_chain
 342      references the VALUE owning this value_chain.  */
 343   decl_or_value dv;
 344
 345   /* Reference count.  */
 346   int refcount;
 347 } *value_chain;
 348 typedef const struct value_chain_def *const_value_chain;
 349
 350 /* Pointer to the BB's information specific to variable tracking pass.  */
 351 #define VTI(BB) ((variable_tracking_info) (BB)->aux)
 352
 353 /* Macro to access MEM_OFFSET as an HOST_WIDE_INT.  Evaluates MEM twice.  */
 354 #define INT_MEM_OFFSET(mem) (MEM_OFFSET (mem) ? INTVAL (MEM_OFFSET (mem)) : 0)
 355
 356 /* Alloc pool for struct attrs_def.  */
 357 static alloc_pool attrs_pool;
 358
 359 /* Alloc pool for struct variable_def with MAX_VAR_PARTS entries.  */
 360 static alloc_pool var_pool;
 361
 362 /* Alloc pool for struct variable_def with a single var_part entry.  */
 363 static alloc_pool valvar_pool;
 364
 365 /* Alloc pool for struct location_chain_def.  */
 366 static alloc_pool loc_chain_pool;
 367
 368 /* Alloc pool for struct shared_hash_def.  */
 369 static alloc_pool shared_hash_pool;
 370
 371 /* Alloc pool for struct value_chain_def.  */
 372 static alloc_pool value_chain_pool;
 373
 374 /* Changed variables, notes will be emitted for them.  */
 375 static htab_t changed_variables;
 376
 377 /* Links from VALUEs to DVs referencing them in their current loc_chains.  */
 378 static htab_t value_chains;
 379
 380 /* Shall notes be emitted?  */
 381 static bool emit_notes;
 382
 383 /* Empty shared hashtable.  */
 384 static shared_hash empty_shared_hash;
 385
 386 /* Scratch register bitmap used by cselib_expand_value_rtx.  */
 387 static bitmap scratch_regs = NULL;
 388
 389 /* Variable used to tell whether cselib_process_insn called our hook.  */
 390 static bool cselib_hook_called;
 391
 392 /* Local function prototypes.  */
 393 static void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
 394                                           HOST_WIDE_INT *);
 395 static void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
 396                                                HOST_WIDE_INT *);
 397 static void bb_stack_adjust_offset (basic_block);
 398 static bool vt_stack_adjustments (void);
 399 static rtx adjust_stack_reference (rtx, HOST_WIDE_INT);
 400 static hashval_t variable_htab_hash (const void *);
 401 static int variable_htab_eq (const void *, const void *);
 402 static void variable_htab_free (void *);
 403
 404 static void init_attrs_list_set (attrs *);
 405 static void attrs_list_clear (attrs *);
 406 static attrs attrs_list_member (attrs, decl_or_value, HOST_WIDE_INT);
 407 static void attrs_list_insert (attrs *, decl_or_value, HOST_WIDE_INT, rtx);
 408 static void attrs_list_copy (attrs *, attrs);
 409 static void attrs_list_union (attrs *, attrs);
 410
 411 static void **unshare_variable (dataflow_set *set, void **slot, variable var,
 412                                 enum var_init_status);
 413 static int vars_copy_1 (void **, void *);
 414 static void vars_copy (htab_t, htab_t);
 415 static tree var_debug_decl (tree);
 416 static void var_reg_set (dataflow_set *, rtx, enum var_init_status, rtx);
 417 static void var_reg_delete_and_set (dataflow_set *, rtx, bool,
 418                                     enum var_init_status, rtx);
 419 static void var_reg_delete (dataflow_set *, rtx, bool);
 420 static void var_regno_delete (dataflow_set *, int);
 421 static void var_mem_set (dataflow_set *, rtx, enum var_init_status, rtx);
 422 static void var_mem_delete_and_set (dataflow_set *, rtx, bool,
 423                                     enum var_init_status, rtx);
 424 static void var_mem_delete (dataflow_set *, rtx, bool);
 425
 426 static void dataflow_set_init (dataflow_set *);
 427 static void dataflow_set_clear (dataflow_set *);
 428 static void dataflow_set_copy (dataflow_set *, dataflow_set *);
 429 static int variable_union_info_cmp_pos (const void *, const void *);
 430 static int variable_union (void **, void *);
 431 static int variable_canonicalize (void **, void *);
 432 static void dataflow_set_union (dataflow_set *, dataflow_set *);
 433 static location_chain find_loc_in_1pdv (rtx, variable, htab_t);
 434 static bool canon_value_cmp (rtx, rtx);
 435 static int loc_cmp (rtx, rtx);
 436 static bool variable_part_different_p (variable_part *, variable_part *);
 437 static bool onepart_variable_different_p (variable, variable);
 438 static bool variable_different_p (variable, variable, bool);
 439 static int dataflow_set_different_1 (void **, void *);
 440 static bool dataflow_set_different (dataflow_set *, dataflow_set *);
 441 static void dataflow_set_destroy (dataflow_set *);
 442
 443 static bool contains_symbol_ref (rtx);
 444 static bool track_expr_p (tree, bool);
 445 static bool same_variable_part_p (rtx, tree, HOST_WIDE_INT);
 446 static int count_uses (rtx *, void *);
 447 static void count_uses_1 (rtx *, void *);
 448 static void count_stores (rtx, const_rtx, void *);
 449 static int add_uses (rtx *, void *);
 450 static void add_uses_1 (rtx *, void *);
 451 static void add_stores (rtx, const_rtx, void *);
 452 static bool compute_bb_dataflow (basic_block);
 453 static bool vt_find_locations (void);
 454
 455 static void dump_attrs_list (attrs);
 456 static int dump_var_slot (void **, void *);
 457 static void dump_var (variable);
 458 static void dump_vars (htab_t);
 459 static void dump_dataflow_set (dataflow_set *);
 460 static void dump_dataflow_sets (void);
 461
 462 static void variable_was_changed (variable, dataflow_set *);
 463 static void **set_slot_part (dataflow_set *, rtx, void **,
 464                              decl_or_value, HOST_WIDE_INT,
 465                              enum var_init_status, rtx);
 466 static void set_variable_part (dataflow_set *, rtx,
 467                                decl_or_value, HOST_WIDE_INT,
 468                                enum var_init_status, rtx, enum insert_option);
 469 static void **clobber_slot_part (dataflow_set *, rtx,
 470                                  void **, HOST_WIDE_INT, rtx);
 471 static void clobber_variable_part (dataflow_set *, rtx,
 472                                    decl_or_value, HOST_WIDE_INT, rtx);
 473 static void **delete_slot_part (dataflow_set *, rtx, void **, HOST_WIDE_INT);
 474 static void delete_variable_part (dataflow_set *, rtx,
 475                                   decl_or_value, HOST_WIDE_INT);
 476 static int emit_note_insn_var_location (void **, void *);
 477 static void emit_notes_for_changes (rtx, enum emit_note_where, shared_hash);
 478 static int emit_notes_for_differences_1 (void **, void *);
 479 static int emit_notes_for_differences_2 (void **, void *);
 480 static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
 481 static void emit_notes_in_bb (basic_block, dataflow_set *);
 482 static void vt_emit_notes (void);
 483
 484 static bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *);
 485 static void vt_add_function_parameters (void);
 486 static void vt_initialize (void);
 487 static void vt_finalize (void);
 488
 489 /* Given a SET, calculate the amount of stack adjustment it contains
 490    PRE- and POST-modifying stack pointer.
 491    This function is similar to stack_adjust_offset.  */
 492
 493 static void
 494 stack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre,
 495                               HOST_WIDE_INT *post)
 496 {
 497   rtx src = SET_SRC (pattern);
 498   rtx dest = SET_DEST (pattern);
 499   enum rtx_code code;
 500
 501   if (dest == stack_pointer_rtx)
 502     {
 503       /* (set (reg sp) (plus (reg sp) (const_int))) */
 504       code = GET_CODE (src);
 505       if (! (code == PLUS || code == MINUS)
 506           || XEXP (src, 0) != stack_pointer_rtx
 507           || !CONST_INT_P (XEXP (src, 1)))
 508         return;
 509
 510       if (code == MINUS)
 511         *post += INTVAL (XEXP (src, 1));
 512       else
 513         *post -= INTVAL (XEXP (src, 1));
 514     }
 515   else if (MEM_P (dest))
 516     {
 517       /* (set (mem (pre_dec (reg sp))) (foo)) */
 518       src = XEXP (dest, 0);
 519       code = GET_CODE (src);
 520
 521       switch (code)
 522         {
 523         case PRE_MODIFY:
 524         case POST_MODIFY:
 525           if (XEXP (src, 0) == stack_pointer_rtx)
 526             {
 527               rtx val = XEXP (XEXP (src, 1), 1);
 528               /* We handle only adjustments by constant amount.  */
 529               gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS &&
 530                           CONST_INT_P (val));
 531
 532               if (code == PRE_MODIFY)
 533                 *pre -= INTVAL (val);
 534               else
 535                 *post -= INTVAL (val);
 536               break;
 537             }
 538           return;
 539
 540         case PRE_DEC:
 541           if (XEXP (src, 0) == stack_pointer_rtx)
 542             {
 543               *pre += GET_MODE_SIZE (GET_MODE (dest));
 544               break;
 545             }
 546           return;
 547
 548         case POST_DEC:
 549           if (XEXP (src, 0) == stack_pointer_rtx)
 550             {
 551               *post += GET_MODE_SIZE (GET_MODE (dest));
 552               break;
 553             }
 554           return;
 555
 556         case PRE_INC:
 557           if (XEXP (src, 0) == stack_pointer_rtx)
 558             {
 559               *pre -= GET_MODE_SIZE (GET_MODE (dest));
 560               break;
 561             }
 562           return;
 563
 564         case POST_INC:
 565           if (XEXP (src, 0) == stack_pointer_rtx)
 566             {
 567               *post -= GET_MODE_SIZE (GET_MODE (dest));
 568               break;
 569             }
 570           return;
 571
 572         default:
 573           return;
 574         }
 575     }
 576 }
 577
 578 /* Given an INSN, calculate the amount of stack adjustment it contains
 579    PRE- and POST-modifying stack pointer.  */
 580
 581 static void
 582 insn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre,
 583                                    HOST_WIDE_INT *post)
 584 {
 585   rtx pattern;
 586
 587   *pre = 0;
 588   *post = 0;
 589
 590   pattern = PATTERN (insn);
 591   if (RTX_FRAME_RELATED_P (insn))
 592     {
 593       rtx expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
 594       if (expr)
 595         pattern = XEXP (expr, 0);
 596     }
 597
 598   if (GET_CODE (pattern) == SET)
 599     stack_adjust_offset_pre_post (pattern, pre, post);
 600   else if (GET_CODE (pattern) == PARALLEL
 601            || GET_CODE (pattern) == SEQUENCE)
 602     {
 603       int i;
 604
 605       /* There may be stack adjustments inside compound insns.  Search
 606          for them.  */
 607       for ( i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
 608         if (GET_CODE (XVECEXP (pattern, 0, i)) == SET)
 609           stack_adjust_offset_pre_post (XVECEXP (pattern, 0, i), pre, post);
 610     }
 611 }
 612
 613 /* Compute stack adjustment in basic block BB.  */
 614
 615 static void
 616 bb_stack_adjust_offset (basic_block bb)
 617 {
 618   HOST_WIDE_INT offset;
 619   int i;
 620
 621   offset = VTI (bb)->in.stack_adjust;
 622   for (i = 0; i < VTI (bb)->n_mos; i++)
 623     {
 624       if (VTI (bb)->mos[i].type == MO_ADJUST)
 625         offset += VTI (bb)->mos[i].u.adjust;
 626       else if (VTI (bb)->mos[i].type != MO_CALL)
 627         {
 628           if (MEM_P (VTI (bb)->mos[i].u.loc))
 629             {
 630               VTI (bb)->mos[i].u.loc
 631                 = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset);
 632             }
 633         }
 634     }
 635   VTI (bb)->out.stack_adjust = offset;
 636 }
 637
 638 /* Compute stack adjustments for all blocks by traversing DFS tree.
 639    Return true when the adjustments on all incoming edges are consistent.
 640    Heavily borrowed from pre_and_rev_post_order_compute.  */
 641
 642 static bool
 643 vt_stack_adjustments (void)
 644 {
 645   edge_iterator *stack;
 646   int sp;
 647
 648   /* Initialize entry block.  */
 649   VTI (ENTRY_BLOCK_PTR)->visited = true;
 650   VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET;
 651
 652   /* Allocate stack for back-tracking up CFG.  */
 653   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 654   sp = 0;
 655
 656   /* Push the first edge on to the stack.  */
 657   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 658
 659   while (sp)
 660     {
 661       edge_iterator ei;
 662       basic_block src;
 663       basic_block dest;
 664
 665       /* Look at the edge on the top of the stack.  */
 666       ei = stack[sp - 1];
 667       src = ei_edge (ei)->src;
 668       dest = ei_edge (ei)->dest;
 669
 670       /* Check if the edge destination has been visited yet.  */
 671       if (!VTI (dest)->visited)
 672         {
 673           VTI (dest)->visited = true;
 674           VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust;
 675           bb_stack_adjust_offset (dest);
 676
 677           if (EDGE_COUNT (dest->succs) > 0)
 678             /* Since the DEST node has been visited for the first
 679                time, check its successors.  */
 680             stack[sp++] = ei_start (dest->succs);
 681         }
 682       else
 683         {
 684           /* Check whether the adjustments on the edges are the same.  */
 685           if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust)
 686             {
 687               free (stack);
 688               return false;
 689             }
 690
 691           if (! ei_one_before_end_p (ei))
 692             /* Go to the next edge.  */
 693             ei_next (&stack[sp - 1]);
 694           else
 695             /* Return to previous level if there are no more edges.  */
 696             sp--;
 697         }
 698     }
 699
 700   free (stack);
 701   return true;
 702 }
 703
 704 /* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative
 705    to the argument pointer.  Return the new rtx.  */
 706
 707 static rtx
 708 adjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment)
 709 {
 710   rtx addr, cfa, tmp;
 711
 712 #ifdef FRAME_POINTER_CFA_OFFSET
 713   adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl);
 714   cfa = plus_constant (frame_pointer_rtx, adjustment);
 715 #else
 716   adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl);
 717   cfa = plus_constant (arg_pointer_rtx, adjustment);
 718 #endif
 719
 720   addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa);
 721   tmp = simplify_rtx (addr);
 722   if (tmp)
 723     addr = tmp;
 724
 725   return replace_equiv_address_nv (mem, addr);
 726 }
 727
 728 /* Return true if a decl_or_value DV is a DECL or NULL.  */
 729 static inline bool
 730 dv_is_decl_p (decl_or_value dv)
 731 {
 732   return !dv || (int) TREE_CODE ((tree) dv) != (int) VALUE;
 733 }
 734
 735 /* Return true if a decl_or_value is a VALUE rtl.  */
 736 static inline bool
 737 dv_is_value_p (decl_or_value dv)
 738 {
 739   return dv && !dv_is_decl_p (dv);
 740 }
 741
 742 /* Return the decl in the decl_or_value.  */
 743 static inline tree
 744 dv_as_decl (decl_or_value dv)
 745 {
 746 #ifdef ENABLE_CHECKING
 747   gcc_assert (dv_is_decl_p (dv));
 748 #endif
 749   return (tree) dv;
 750 }
 751
 752 /* Return the value in the decl_or_value.  */
 753 static inline rtx
 754 dv_as_value (decl_or_value dv)
 755 {
 756 #ifdef ENABLE_CHECKING
 757   gcc_assert (dv_is_value_p (dv));
 758 #endif
 759   return (rtx)dv;
 760 }
 761
 762 /* Return the opaque pointer in the decl_or_value.  */
 763 static inline void *
 764 dv_as_opaque (decl_or_value dv)
 765 {
 766   return dv;
 767 }
 768
 769 /* Return true if a decl_or_value must not have more than one variable
 770    part.  */
 771 static inline bool
 772 dv_onepart_p (decl_or_value dv)
 773 {
 774   tree decl;
 775
 776   if (!MAY_HAVE_DEBUG_INSNS)
 777     return false;
 778
 779   if (dv_is_value_p (dv))
 780     return true;
 781
 782   decl = dv_as_decl (dv);
 783
 784   if (!decl)
 785     return true;
 786
 787   return (target_for_debug_bind (decl) != NULL_TREE);
 788 }
 789
 790 /* Return the variable pool to be used for dv, depending on whether it
 791    can have multiple parts or not.  */
 792 static inline alloc_pool
 793 dv_pool (decl_or_value dv)
 794 {
 795   return dv_onepart_p (dv) ? valvar_pool : var_pool;
 796 }
 797
 798 /* Build a decl_or_value out of a decl.  */
 799 static inline decl_or_value
 800 dv_from_decl (tree decl)
 801 {
 802   decl_or_value dv;
 803   dv = decl;
 804 #ifdef ENABLE_CHECKING
 805   gcc_assert (dv_is_decl_p (dv));
 806 #endif
 807   return dv;
 808 }
 809
 810 /* Build a decl_or_value out of a value.  */
 811 static inline decl_or_value
 812 dv_from_value (rtx value)
 813 {
 814   decl_or_value dv;
 815   dv = value;
 816 #ifdef ENABLE_CHECKING
 817   gcc_assert (dv_is_value_p (dv));
 818 #endif
 819   return dv;
 820 }
 821
 822 typedef unsigned int dvuid;
 823
 824 /* Return the uid of DV.  */
 825
 826 static inline dvuid
 827 dv_uid (decl_or_value dv)
 828 {
 829   if (dv_is_value_p (dv))
 830     return CSELIB_VAL_PTR (dv_as_value (dv))->uid;
 831   else
 832     return DECL_UID (dv_as_decl (dv));
 833 }
 834
 835 /* Compute the hash from the uid.  */
 836
 837 static inline hashval_t
 838 dv_uid2hash (dvuid uid)
 839 {
 840   return uid;
 841 }
 842
 843 /* The hash function for a mask table in a shared_htab chain.  */
 844
 845 static inline hashval_t
 846 dv_htab_hash (decl_or_value dv)
 847 {
 848   return dv_uid2hash (dv_uid (dv));
 849 }
 850
 851 /* The hash function for variable_htab, computes the hash value
 852    from the declaration of variable X.  */
 853
 854 static hashval_t
 855 variable_htab_hash (const void *x)
 856 {
 857   const_variable const v = (const_variable) x;
 858
 859   return dv_htab_hash (v->dv);
 860 }
 861
 862 /* Compare the declaration of variable X with declaration Y.  */
 863
 864 static int
 865 variable_htab_eq (const void *x, const void *y)
 866 {
 867   const_variable const v = (const_variable) x;
 868   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
 869
 870   return (dv_as_opaque (v->dv) == dv_as_opaque (dv));
 871 }
 872
 873 /* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
 874
 875 static void
 876 variable_htab_free (void *elem)
 877 {
 878   int i;
 879   variable var = (variable) elem;
 880   location_chain node, next;
 881
 882   gcc_assert (var->refcount > 0);
 883
 884   var->refcount--;
 885   if (var->refcount > 0)
 886     return;
 887
 888   for (i = 0; i < var->n_var_parts; i++)
 889     {
 890       for (node = var->var_part[i].loc_chain; node; node = next)
 891         {
 892           next = node->next;
 893           pool_free (loc_chain_pool, node);
 894         }
 895       var->var_part[i].loc_chain = NULL;
 896     }
 897   pool_free (dv_pool (var->dv), var);
 898 }
 899
 900 /* The hash function for value_chains htab, computes the hash value
 901    from the VALUE.  */
 902
 903 static hashval_t
 904 value_chain_htab_hash (const void *x)
 905 {
 906   const_value_chain const v = (const_value_chain) x;
 907
 908   return dv_htab_hash (v->dv);
 909 }
 910
 911 /* Compare the VALUE X with VALUE Y.  */
 912
 913 static int
 914 value_chain_htab_eq (const void *x, const void *y)
 915 {
 916   const_value_chain const v = (const_value_chain) x;
 917   decl_or_value dv = CONST_CAST2 (decl_or_value, const void *, y);
 918
 919   return dv_as_opaque (v->dv) == dv_as_opaque (dv);
 920 }
 921
 922 /* Initialize the set (array) SET of attrs to empty lists.  */
 923
 924 static void
 925 init_attrs_list_set (attrs *set)
 926 {
 927   int i;
 928
 929   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 930     set[i] = NULL;
 931 }
 932
 933 /* Make the list *LISTP empty.  */
 934
 935 static void
 936 attrs_list_clear (attrs *listp)
 937 {
 938   attrs list, next;
 939
 940   for (list = *listp; list; list = next)
 941     {
 942       next = list->next;
 943       pool_free (attrs_pool, list);
 944     }
 945   *listp = NULL;
 946 }
 947
 948 /* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
 949
 950 static attrs
 951 attrs_list_member (attrs list, decl_or_value dv, HOST_WIDE_INT offset)
 952 {
 953   for (; list; list = list->next)
 954     if (dv_as_opaque (list->dv) == dv_as_opaque (dv) && list->offset == offset)
 955       return list;
 956   return NULL;
 957 }
 958
 959 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
 960
 961 static void
 962 attrs_list_insert (attrs *listp, decl_or_value dv,
 963                    HOST_WIDE_INT offset, rtx loc)
 964 {
 965   attrs list;
 966
 967   list = (attrs) pool_alloc (attrs_pool);
 968   list->loc = loc;
 969   list->dv = dv;
 970   list->offset = offset;
 971   list->next = *listp;
 972   *listp = list;
 973 }
 974
 975 /* Copy all nodes from SRC and create a list *DSTP of the copies.  */
 976
 977 static void
 978 attrs_list_copy (attrs *dstp, attrs src)
 979 {
 980   attrs n;
 981
 982   attrs_list_clear (dstp);
 983   for (; src; src = src->next)
 984     {
 985       n = (attrs) pool_alloc (attrs_pool);
 986       n->loc = src->loc;
 987       n->dv = src->dv;
 988       n->offset = src->offset;
 989       n->next = *dstp;
 990       *dstp = n;
 991     }
 992 }
 993
 994 /* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
 995
 996 static void
 997 attrs_list_union (attrs *dstp, attrs src)
 998 {
 999   for (; src; src = src->next)
1000     {
1001       if (!attrs_list_member (*dstp, src->dv, src->offset))
1002         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1003     }
1004 }
1005
1006 /* Combine nodes that are not onepart nodes from SRC and SRC2 into
1007    *DSTP.  */
1008
1009 static void
1010 attrs_list_mpdv_union (attrs *dstp, attrs src, attrs src2)
1011 {
1012   gcc_assert (!*dstp);
1013   for (; src; src = src->next)
1014     {
1015       if (!dv_onepart_p (src->dv))
1016         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1017     }
1018   for (src = src2; src; src = src->next)
1019     {
1020       if (!dv_onepart_p (src->dv)
1021           && !attrs_list_member (*dstp, src->dv, src->offset))
1022         attrs_list_insert (dstp, src->dv, src->offset, src->loc);
1023     }
1024 }
1025
1026 /* Shared hashtable support.  */
1027
1028 /* Return true if VARS is shared.  */
1029
1030 static inline bool
1031 shared_hash_shared (shared_hash vars)
1032 {
1033   return vars->refcount > 1;
1034 }
1035
1036 /* Return the hash table for VARS.  */
1037
1038 static inline htab_t
1039 shared_hash_htab (shared_hash vars)
1040 {
1041   return vars->htab;
1042 }
1043
1044 /* Copy variables into a new hash table.  */
1045
1046 static shared_hash
1047 shared_hash_unshare (shared_hash vars)
1048 {
1049   shared_hash new_vars = (shared_hash) pool_alloc (shared_hash_pool);
1050   gcc_assert (vars->refcount > 1);
1051   new_vars->refcount = 1;
1052   new_vars->htab
1053     = htab_create (htab_elements (vars->htab) + 3, variable_htab_hash,
1054                    variable_htab_eq, variable_htab_free);
1055   vars_copy (new_vars->htab, vars->htab);
1056   vars->refcount--;
1057   return new_vars;
1058 }
1059
1060 /* Increment reference counter on VARS and return it.  */
1061
1062 static inline shared_hash
1063 shared_hash_copy (shared_hash vars)
1064 {
1065   vars->refcount++;
1066   return vars;
1067 }
1068
1069 /* Decrement reference counter and destroy hash table if not shared
1070    anymore.  */
1071
1072 static void
1073 shared_hash_destroy (shared_hash vars)
1074 {
1075   gcc_assert (vars->refcount > 0);
1076   if (--vars->refcount == 0)
1077     {
1078       htab_delete (vars->htab);
1079       pool_free (shared_hash_pool, vars);
1080     }
1081 }
1082
1083 /* Unshare *PVARS if shared and return slot for DV.  If INS is
1084    INSERT, insert it if not already present.  */
1085
1086 static inline void **
1087 shared_hash_find_slot_unshare_1 (shared_hash *pvars, decl_or_value dv,
1088                                  hashval_t dvhash, enum insert_option ins)
1089 {
1090   if (shared_hash_shared (*pvars))
1091     *pvars = shared_hash_unshare (*pvars);
1092   return htab_find_slot_with_hash (shared_hash_htab (*pvars), dv, dvhash, ins);
1093 }
1094
1095 static inline void **
1096 shared_hash_find_slot_unshare (shared_hash *pvars, decl_or_value dv,
1097                                enum insert_option ins)
1098 {
1099   return shared_hash_find_slot_unshare_1 (pvars, dv, dv_htab_hash (dv), ins);
1100 }
1101
1102 /* Return slot for DV, if it is already present in the hash table.
1103    If it is not present, insert it only VARS is not shared, otherwise
1104    return NULL.  */
1105
1106 static inline void **
1107 shared_hash_find_slot_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1108 {
1109   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1110                                    shared_hash_shared (vars)
1111                                    ? NO_INSERT : INSERT);
1112 }
1113
1114 static inline void **
1115 shared_hash_find_slot (shared_hash vars, decl_or_value dv)
1116 {
1117   return shared_hash_find_slot_1 (vars, dv, dv_htab_hash (dv));
1118 }
1119
1120 /* Return slot for DV only if it is already present in the hash table.  */
1121
1122 static inline void **
1123 shared_hash_find_slot_noinsert_1 (shared_hash vars, decl_or_value dv,
1124                                   hashval_t dvhash)
1125 {
1126   return htab_find_slot_with_hash (shared_hash_htab (vars), dv, dvhash,
1127                                    NO_INSERT);
1128 }
1129
1130 static inline void **
1131 shared_hash_find_slot_noinsert (shared_hash vars, decl_or_value dv)
1132 {
1133   return shared_hash_find_slot_noinsert_1 (vars, dv, dv_htab_hash (dv));
1134 }
1135
1136 /* Return variable for DV or NULL if not already present in the hash
1137    table.  */
1138
1139 static inline variable
1140 shared_hash_find_1 (shared_hash vars, decl_or_value dv, hashval_t dvhash)
1141 {
1142   return (variable) htab_find_with_hash (shared_hash_htab (vars), dv, dvhash);
1143 }
1144
1145 static inline variable
1146 shared_hash_find (shared_hash vars, decl_or_value dv)
1147 {
1148   return shared_hash_find_1 (vars, dv, dv_htab_hash (dv));
1149 }
1150
1151 /* Return true if TVAL is better than CVAL as a canonival value.  We
1152    choose lowest-numbered VALUEs, using the RTX address as a
1153    tie-breaker.  The idea is to arrange them into a star topology,
1154    such that all of them are at most one step away from the canonical
1155    value, and the canonical value has backlinks to all of them, in
1156    addition to all the actual locations.  We don't enforce this
1157    topology throughout the entire dataflow analysis, though.
1158  */
1159
1160 static inline bool
1161 canon_value_cmp (rtx tval, rtx cval)
1162 {
1163   return !cval
1164     || CSELIB_VAL_PTR (tval)->uid < CSELIB_VAL_PTR (cval)->uid;
1165 }
1166
1167 static bool dst_can_be_shared;
1168
1169 /* Return a copy of a variable VAR and insert it to dataflow set SET.  */
1170
1171 static void **
1172 unshare_variable (dataflow_set *set, void **slot, variable var,
1173                   enum var_init_status initialized)
1174 {
1175   variable new_var;
1176   int i;
1177
1178   new_var = (variable) pool_alloc (dv_pool (var->dv));
1179   new_var->dv = var->dv;
1180   new_var->refcount = 1;
1181   var->refcount--;
1182   new_var->n_var_parts = var->n_var_parts;
1183
1184   if (! flag_var_tracking_uninit)
1185     initialized = VAR_INIT_STATUS_INITIALIZED;
1186
1187   for (i = 0; i < var->n_var_parts; i++)
1188     {
1189       location_chain node;
1190       location_chain *nextp;
1191
1192       new_var->var_part[i].offset = var->var_part[i].offset;
1193       nextp = &new_var->var_part[i].loc_chain;
1194       for (node = var->var_part[i].loc_chain; node; node = node->next)
1195         {
1196           location_chain new_lc;
1197
1198           new_lc = (location_chain) pool_alloc (loc_chain_pool);
1199           new_lc->next = NULL;
1200           if (node->init > initialized)
1201             new_lc->init = node->init;
1202           else
1203             new_lc->init = initialized;
1204           if (node->set_src && !(MEM_P (node->set_src)))
1205             new_lc->set_src = node->set_src;
1206           else
1207             new_lc->set_src = NULL;
1208           new_lc->loc = node->loc;
1209
1210           *nextp = new_lc;
1211           nextp = &new_lc->next;
1212         }
1213
1214       /* We are at the basic block boundary when copying variable description
1215          so set the CUR_LOC to be the first element of the chain.  */
1216       if (new_var->var_part[i].loc_chain)
1217         new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
1218       else
1219         new_var->var_part[i].cur_loc = NULL;
1220     }
1221
1222   dst_can_be_shared = false;
1223   if (shared_hash_shared (set->vars))
1224     slot = shared_hash_find_slot_unshare (&set->vars, var->dv, NO_INSERT);
1225   else if (set->traversed_vars && set->vars != set->traversed_vars)
1226     slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
1227   *slot = new_var;
1228   return slot;
1229 }
1230
1231 /* Add a variable from *SLOT to hash table DATA and increase its reference
1232    count.  */
1233
1234 static int
1235 vars_copy_1 (void **slot, void *data)
1236 {
1237   htab_t dst = (htab_t) data;
1238   variable src;
1239   void **dstp;
1240
1241   src = (variable) *slot;
1242   src->refcount++;
1243
1244   dstp = htab_find_slot_with_hash (dst, src->dv,
1245                                    dv_htab_hash (src->dv),
1246                                    INSERT);
1247   *dstp = src;
1248
1249   /* Continue traversing the hash table.  */
1250   return 1;
1251 }
1252
1253 /* Copy all variables from hash table SRC to hash table DST.  */
1254
1255 static void
1256 vars_copy (htab_t dst, htab_t src)
1257 {
1258   htab_traverse_noresize (src, vars_copy_1, dst);
1259 }
1260
1261 /* Map a decl to its main debug decl.  */
1262
1263 static inline tree
1264 var_debug_decl (tree decl)
1265 {
1266   if (decl && DECL_P (decl)
1267       && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl)
1268       && DECL_P (DECL_DEBUG_EXPR (decl)))
1269     decl = DECL_DEBUG_EXPR (decl);
1270
1271   return decl;
1272 }
1273
1274 /* Set the register LOC to contain DV, OFFSET.  */
1275
1276 static void
1277 var_reg_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1278                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1279                   enum insert_option iopt)
1280 {
1281   attrs node;
1282   bool decl_p = dv_is_decl_p (dv);
1283
1284   if (decl_p)
1285     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1286
1287   for (node = set->regs[REGNO (loc)]; node; node = node->next)
1288     if (dv_as_opaque (node->dv) == dv_as_opaque (dv)
1289         && node->offset == offset)
1290       break;
1291   if (!node)
1292     attrs_list_insert (&set->regs[REGNO (loc)], dv, offset, loc);
1293   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1294 }
1295
1296 /* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
1297
1298 static void
1299 var_reg_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1300              rtx set_src)
1301 {
1302   tree decl = REG_EXPR (loc);
1303   HOST_WIDE_INT offset = REG_OFFSET (loc);
1304
1305   var_reg_decl_set (set, loc, initialized,
1306                     dv_from_decl (decl), offset, set_src, INSERT);
1307 }
1308
1309 static enum var_init_status
1310 get_init_value (dataflow_set *set, rtx loc, decl_or_value dv)
1311 {
1312   variable var;
1313   int i;
1314   enum var_init_status ret_val = VAR_INIT_STATUS_UNKNOWN;
1315
1316   if (! flag_var_tracking_uninit)
1317     return VAR_INIT_STATUS_INITIALIZED;
1318
1319   var = shared_hash_find (set->vars, dv);
1320   if (var)
1321     {
1322       for (i = 0; i < var->n_var_parts && ret_val == VAR_INIT_STATUS_UNKNOWN; i++)
1323         {
1324           location_chain nextp;
1325           for (nextp = var->var_part[i].loc_chain; nextp; nextp = nextp->next)
1326             if (rtx_equal_p (nextp->loc, loc))
1327               {
1328                 ret_val = nextp->init;
1329                 break;
1330               }
1331         }
1332     }
1333
1334   return ret_val;
1335 }
1336
1337 /* Delete current content of register LOC in dataflow set SET and set
1338    the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  If
1339    MODIFY is true, any other live copies of the same variable part are
1340    also deleted from the dataflow set, otherwise the variable part is
1341    assumed to be copied from another location holding the same
1342    part.  */
1343
1344 static void
1345 var_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify,
1346                         enum var_init_status initialized, rtx set_src)
1347 {
1348   tree decl = REG_EXPR (loc);
1349   HOST_WIDE_INT offset = REG_OFFSET (loc);
1350   attrs node, next;
1351   attrs *nextp;
1352
1353   decl = var_debug_decl (decl);
1354
1355   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1356     initialized = get_init_value (set, loc, dv_from_decl (decl));
1357
1358   nextp = &set->regs[REGNO (loc)];
1359   for (node = *nextp; node; node = next)
1360     {
1361       next = node->next;
1362       if (dv_as_opaque (node->dv) != decl || node->offset != offset)
1363         {
1364           delete_variable_part (set, node->loc, node->dv, node->offset);
1365           pool_free (attrs_pool, node);
1366           *nextp = next;
1367         }
1368       else
1369         {
1370           node->loc = loc;
1371           nextp = &node->next;
1372         }
1373     }
1374   if (modify)
1375     clobber_variable_part (set, loc, dv_from_decl (decl), offset, set_src);
1376   var_reg_set (set, loc, initialized, set_src);
1377 }
1378
1379 /* Delete the association of register LOC in dataflow set SET with any
1380    variables that aren't onepart.  If CLOBBER is true, also delete any
1381    other live copies of the same variable part, and delete the
1382    association with onepart dvs too.  */
1383
1384 static void
1385 var_reg_delete (dataflow_set *set, rtx loc, bool clobber)
1386 {
1387   attrs *nextp = &set->regs[REGNO (loc)];
1388   attrs node, next;
1389
1390   if (clobber)
1391     {
1392       tree decl = REG_EXPR (loc);
1393       HOST_WIDE_INT offset = REG_OFFSET (loc);
1394
1395       decl = var_debug_decl (decl);
1396
1397       clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1398     }
1399
1400   for (node = *nextp; node; node = next)
1401     {
1402       next = node->next;
1403       if (clobber || !dv_onepart_p (node->dv))
1404         {
1405           delete_variable_part (set, node->loc, node->dv, node->offset);
1406           pool_free (attrs_pool, node);
1407           *nextp = next;
1408         }
1409       else
1410         nextp = &node->next;
1411     }
1412 }
1413
1414 /* Delete content of register with number REGNO in dataflow set SET.  */
1415
1416 static void
1417 var_regno_delete (dataflow_set *set, int regno)
1418 {
1419   attrs *reg = &set->regs[regno];
1420   attrs node, next;
1421
1422   for (node = *reg; node; node = next)
1423     {
1424       next = node->next;
1425       delete_variable_part (set, node->loc, node->dv, node->offset);
1426       pool_free (attrs_pool, node);
1427     }
1428   *reg = NULL;
1429 }
1430
1431 /* Set the location of DV, OFFSET as the MEM LOC.  */
1432
1433 static void
1434 var_mem_decl_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1435                   decl_or_value dv, HOST_WIDE_INT offset, rtx set_src,
1436                   enum insert_option iopt)
1437 {
1438   if (dv_is_decl_p (dv))
1439     dv = dv_from_decl (var_debug_decl (dv_as_decl (dv)));
1440
1441   set_variable_part (set, loc, dv, offset, initialized, set_src, iopt);
1442 }
1443
1444 /* Set the location part of variable MEM_EXPR (LOC) in dataflow set
1445    SET to LOC.
1446    Adjust the address first if it is stack pointer based.  */
1447
1448 static void
1449 var_mem_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1450              rtx set_src)
1451 {
1452   tree decl = MEM_EXPR (loc);
1453   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1454
1455   var_mem_decl_set (set, loc, initialized,
1456                     dv_from_decl (decl), offset, set_src, INSERT);
1457 }
1458
1459 /* Delete and set the location part of variable MEM_EXPR (LOC) in
1460    dataflow set SET to LOC.  If MODIFY is true, any other live copies
1461    of the same variable part are also deleted from the dataflow set,
1462    otherwise the variable part is assumed to be copied from another
1463    location holding the same part.
1464    Adjust the address first if it is stack pointer based.  */
1465
1466 static void
1467 var_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify,
1468                         enum var_init_status initialized, rtx set_src)
1469 {
1470   tree decl = MEM_EXPR (loc);
1471   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1472
1473   decl = var_debug_decl (decl);
1474
1475   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1476     initialized = get_init_value (set, loc, dv_from_decl (decl));
1477
1478   if (modify)
1479     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, set_src);
1480   var_mem_set (set, loc, initialized, set_src);
1481 }
1482
1483 /* Delete the location part LOC from dataflow set SET.  If CLOBBER is
1484    true, also delete any other live copies of the same variable part.
1485    Adjust the address first if it is stack pointer based.  */
1486
1487 static void
1488 var_mem_delete (dataflow_set *set, rtx loc, bool clobber)
1489 {
1490   tree decl = MEM_EXPR (loc);
1491   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1492
1493   decl = var_debug_decl (decl);
1494   if (clobber)
1495     clobber_variable_part (set, NULL, dv_from_decl (decl), offset, NULL);
1496   delete_variable_part (set, loc, dv_from_decl (decl), offset);
1497 }
1498
1499 /* Bind a value to a location it was just stored in.  If MODIFIED
1500    holds, assume the location was modified, detaching it from any
1501    values bound to it.  */
1502
1503 static void
1504 val_store (dataflow_set *set, rtx val, rtx loc, rtx insn, bool modified)
1505 {
1506   cselib_val *v = CSELIB_VAL_PTR (val);
1507
1508   gcc_assert (cselib_preserved_value_p (v));
1509
1510   if (dump_file)
1511     {
1512       fprintf (dump_file, "%i: ", INSN_UID (insn));
1513       print_inline_rtx (dump_file, val, 0);
1514       fprintf (dump_file, " stored in ");
1515       print_inline_rtx (dump_file, loc, 0);
1516       if (v->locs)
1517         {
1518           struct elt_loc_list *l;
1519           for (l = v->locs; l; l = l->next)
1520             {
1521               fprintf (dump_file, "\n%i: ", INSN_UID (l->setting_insn));
1522               print_inline_rtx (dump_file, l->loc, 0);
1523             }
1524         }
1525       fprintf (dump_file, "\n");
1526     }
1527
1528   if (REG_P (loc))
1529     {
1530       if (modified)
1531         var_regno_delete (set, REGNO (loc));
1532       var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1533                         dv_from_value (val), 0, NULL_RTX, INSERT);
1534     }
1535   else if (MEM_P (loc))
1536     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1537                       dv_from_value (val), 0, NULL_RTX, INSERT);
1538   else
1539     set_variable_part (set, loc, dv_from_value (val), 0,
1540                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1541 }
1542
1543 /* Reset this node, detaching all its equivalences.  Return the slot
1544    in the variable hash table that holds dv, if there is one.  */
1545
1546 static void
1547 val_reset (dataflow_set *set, decl_or_value dv)
1548 {
1549   variable var = shared_hash_find (set->vars, dv) ;
1550   location_chain node;
1551   rtx cval;
1552
1553   if (!var || !var->n_var_parts)
1554     return;
1555
1556   gcc_assert (var->n_var_parts == 1);
1557
1558   cval = NULL;
1559   for (node = var->var_part[0].loc_chain; node; node = node->next)
1560     if (GET_CODE (node->loc) == VALUE
1561         && canon_value_cmp (node->loc, cval))
1562       cval = node->loc;
1563
1564   for (node = var->var_part[0].loc_chain; node; node = node->next)
1565     if (GET_CODE (node->loc) == VALUE && cval != node->loc)
1566       {
1567         /* Redirect the equivalence link to the new canonical
1568            value, or simply remove it if it would point at
1569            itself.  */
1570         if (cval)
1571           set_variable_part (set, cval, dv_from_value (node->loc),
1572                              0, node->init, node->set_src, NO_INSERT);
1573         delete_variable_part (set, dv_as_value (dv),
1574                               dv_from_value (node->loc), 0);
1575       }
1576
1577   if (cval)
1578     {
1579       decl_or_value cdv = dv_from_value (cval);
1580
1581       /* Keep the remaining values connected, accummulating links
1582          in the canonical value.  */
1583       for (node = var->var_part[0].loc_chain; node; node = node->next)
1584         {
1585           if (node->loc == cval)
1586             continue;
1587           else if (GET_CODE (node->loc) == REG)
1588             var_reg_decl_set (set, node->loc, node->init, cdv, 0,
1589                               node->set_src, NO_INSERT);
1590           else if (GET_CODE (node->loc) == MEM)
1591             var_mem_decl_set (set, node->loc, node->init, cdv, 0,
1592                               node->set_src, NO_INSERT);
1593           else
1594             set_variable_part (set, node->loc, cdv, 0,
1595                                node->init, node->set_src, NO_INSERT);
1596         }
1597     }
1598
1599   /* We remove this last, to make sure that the canonical value is not
1600      removed to the point of requiring reinsertion.  */
1601   if (cval)
1602     delete_variable_part (set, dv_as_value (dv), dv_from_value (cval), 0);
1603
1604   clobber_variable_part (set, NULL, dv, 0, NULL);
1605
1606   /* ??? Should we make sure there aren't other available values or
1607      variables whose values involve this one other than by
1608      equivalence?  E.g., at the very least we should reset MEMs, those
1609      shouldn't be too hard to find cselib-looking up the value as an
1610      address, then locating the resulting value in our own hash
1611      table.  */
1612 }
1613
1614 /* Find the values in a given location and map the val to another
1615    value, if it is unique, or add the location as one holding the
1616    value.  */
1617
1618 static void
1619 val_resolve (dataflow_set *set, rtx val, rtx loc, rtx insn)
1620 {
1621   decl_or_value dv = dv_from_value (val);
1622
1623   if (dump_file && (dump_flags & TDF_DETAILS))
1624     {
1625       if (insn)
1626         fprintf (dump_file, "%i: ", INSN_UID (insn));
1627       else
1628         fprintf (dump_file, "head: ");
1629       print_inline_rtx (dump_file, val, 0);
1630       fputs (" is at ", dump_file);
1631       print_inline_rtx (dump_file, loc, 0);
1632       fputc ('\n', dump_file);
1633     }
1634
1635   val_reset (set, dv);
1636
1637   if (REG_P (loc))
1638     {
1639       attrs node, found = NULL;
1640
1641       for (node = set->regs[REGNO (loc)]; node; node = node->next)
1642         if (dv_is_value_p (node->dv)
1643             && GET_MODE (dv_as_value (node->dv)) == GET_MODE (loc))
1644           {
1645             found = node;
1646
1647             /* Map incoming equivalences.  ??? Wouldn't it be nice if
1648              we just started sharing the location lists?  Maybe a
1649              circular list ending at the value itself or some
1650              such.  */
1651             set_variable_part (set, dv_as_value (node->dv),
1652                                dv_from_value (val), node->offset,
1653                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1654             set_variable_part (set, val, node->dv, node->offset,
1655                                VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1656           }
1657
1658       /* If we didn't find any equivalence, we need to remember that
1659          this value is held in the named register.  */
1660       if (!found)
1661         var_reg_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1662                           dv_from_value (val), 0, NULL_RTX, INSERT);
1663     }
1664   else if (MEM_P (loc))
1665     /* ??? Merge equivalent MEMs.  */
1666     var_mem_decl_set (set, loc, VAR_INIT_STATUS_INITIALIZED,
1667                       dv_from_value (val), 0, NULL_RTX, INSERT);
1668   else
1669     /* ??? Merge equivalent expressions.  */
1670     set_variable_part (set, loc, dv_from_value (val), 0,
1671                        VAR_INIT_STATUS_INITIALIZED, NULL_RTX, INSERT);
1672 }
1673
1674 /* Initialize dataflow set SET to be empty.
1675    VARS_SIZE is the initial size of hash table VARS.  */
1676
1677 static void
1678 dataflow_set_init (dataflow_set *set)
1679 {
1680   init_attrs_list_set (set->regs);
1681   set->vars = shared_hash_copy (empty_shared_hash);
1682   set->stack_adjust = 0;
1683   set->traversed_vars = NULL;
1684 }
1685
1686 /* Delete the contents of dataflow set SET.  */
1687
1688 static void
1689 dataflow_set_clear (dataflow_set *set)
1690 {
1691   int i;
1692
1693   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1694     attrs_list_clear (&set->regs[i]);
1695
1696   shared_hash_destroy (set->vars);
1697   set->vars = shared_hash_copy (empty_shared_hash);
1698 }
1699
1700 /* Copy the contents of dataflow set SRC to DST.  */
1701
1702 static void
1703 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
1704 {
1705   int i;
1706
1707   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1708     attrs_list_copy (&dst->regs[i], src->regs[i]);
1709
1710   shared_hash_destroy (dst->vars);
1711   dst->vars = shared_hash_copy (src->vars);
1712   dst->stack_adjust = src->stack_adjust;
1713 }
1714
1715 /* Information for merging lists of locations for a given offset of variable.
1716  */
1717 struct variable_union_info
1718 {
1719   /* Node of the location chain.  */
1720   location_chain lc;
1721
1722   /* The sum of positions in the input chains.  */
1723   int pos;
1724
1725   /* The position in the chain of DST dataflow set.  */
1726   int pos_dst;
1727 };
1728
1729 /* Buffer for location list sorting and its allocated size.  */
1730 static struct variable_union_info *vui_vec;
1731 static int vui_allocated;
1732
1733 /* Compare function for qsort, order the structures by POS element.  */
1734
1735 static int
1736 variable_union_info_cmp_pos (const void *n1, const void *n2)
1737 {
1738   const struct variable_union_info *const i1 =
1739     (const struct variable_union_info *) n1;
1740   const struct variable_union_info *const i2 =
1741     ( const struct variable_union_info *) n2;
1742
1743   if (i1->pos != i2->pos)
1744     return i1->pos - i2->pos;
1745
1746   return (i1->pos_dst - i2->pos_dst);
1747 }
1748
1749 /* Compute union of location parts of variable *SLOT and the same variable
1750    from hash table DATA.  Compute "sorted" union of the location chains
1751    for common offsets, i.e. the locations of a variable part are sorted by
1752    a priority where the priority is the sum of the positions in the 2 chains
1753    (if a location is only in one list the position in the second list is
1754    defined to be larger than the length of the chains).
1755    When we are updating the location parts the newest location is in the
1756    beginning of the chain, so when we do the described "sorted" union
1757    we keep the newest locations in the beginning.  */
1758
1759 static int
1760 variable_union (void **slot, void *data)
1761 {
1762   variable src, dst;
1763   void **dstp;
1764   dataflow_set *set = (dataflow_set *) data;
1765   int i, j, k;
1766
1767   src = (variable) *slot;
1768   dstp = shared_hash_find_slot (set->vars, src->dv);
1769   if (!dstp || !*dstp)
1770     {
1771       src->refcount++;
1772
1773       dst_can_be_shared = false;
1774       if (!dstp)
1775         dstp = shared_hash_find_slot_unshare (&set->vars, src->dv, INSERT);
1776
1777       *dstp = src;
1778
1779       /* If CUR_LOC of some variable part is not the first element of
1780          the location chain we are going to change it so we have to make
1781          a copy of the variable.  */
1782       for (k = 0; k < src->n_var_parts; k++)
1783         {
1784           gcc_assert (!src->var_part[k].loc_chain
1785                       == !src->var_part[k].cur_loc);
1786           if (src->var_part[k].loc_chain)
1787             {
1788               gcc_assert (src->var_part[k].cur_loc);
1789               if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1790                 break;
1791             }
1792         }
1793       if (k < src->n_var_parts)
1794         dstp = unshare_variable (set, dstp, src, VAR_INIT_STATUS_UNKNOWN);
1795
1796       /* Continue traversing the hash table.  */
1797       return 1;
1798     }
1799   else
1800     dst = (variable) *dstp;
1801
1802   gcc_assert (src->n_var_parts);
1803
1804   /* We can combine one-part variables very efficiently, because their
1805      entries are in canonical order.  */
1806   if (dv_onepart_p (src->dv))
1807     {
1808       location_chain *nodep, dnode, snode;
1809
1810       gcc_assert (src->n_var_parts == 1);
1811       gcc_assert (dst->n_var_parts == 1);
1812
1813       snode = src->var_part[0].loc_chain;
1814       gcc_assert (snode);
1815
1816     restart_onepart_unshared:
1817       nodep = &dst->var_part[0].loc_chain;
1818       dnode = *nodep;
1819       gcc_assert (dnode);
1820
1821       while (snode)
1822         {
1823           int r = dnode ? loc_cmp (dnode->loc, snode->loc) : 1;
1824
1825           if (r > 0)
1826             {
1827               location_chain nnode;
1828
1829               if (dst->refcount != 1 || shared_hash_shared (set->vars))
1830                 {
1831                   dstp = unshare_variable (set, dstp, dst,
1832                                            VAR_INIT_STATUS_INITIALIZED);
1833                   dst = (variable)*dstp;
1834                   goto restart_onepart_unshared;
1835                 }
1836
1837               *nodep = nnode = (location_chain) pool_alloc (loc_chain_pool);
1838               nnode->loc = snode->loc;
1839               nnode->init = snode->init;
1840               if (!snode->set_src || MEM_P (snode->set_src))
1841                 nnode->set_src = NULL;
1842               else
1843                 nnode->set_src = snode->set_src;
1844               nnode->next = dnode;
1845               dnode = nnode;
1846             }
1847 #ifdef ENABLE_CHECKING
1848           else if (r == 0)
1849             gcc_assert (rtx_equal_p (dnode->loc, snode->loc));
1850 #endif
1851
1852           if (r >= 0)
1853             snode = snode->next;
1854
1855           nodep = &dnode->next;
1856           dnode = *nodep;
1857         }
1858
1859       dst->var_part[0].cur_loc = dst->var_part[0].loc_chain->loc;
1860
1861       return 1;
1862     }
1863
1864   /* Count the number of location parts, result is K.  */
1865   for (i = 0, j = 0, k = 0;
1866        i < src->n_var_parts && j < dst->n_var_parts; k++)
1867     {
1868       if (src->var_part[i].offset == dst->var_part[j].offset)
1869         {
1870           i++;
1871           j++;
1872         }
1873       else if (src->var_part[i].offset < dst->var_part[j].offset)
1874         i++;
1875       else
1876         j++;
1877     }
1878   k += src->n_var_parts - i;
1879   k += dst->n_var_parts - j;
1880
1881   /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1882      thus there are at most MAX_VAR_PARTS different offsets.  */
1883   gcc_assert (dv_onepart_p (dst->dv) ? k == 1 : k <= MAX_VAR_PARTS);
1884
1885   if ((dst->refcount > 1 || shared_hash_shared (set->vars))
1886       && dst->n_var_parts != k)
1887     {
1888       dstp = unshare_variable (set, dstp, dst, VAR_INIT_STATUS_UNKNOWN);
1889       dst = (variable)*dstp;
1890     }
1891
1892   i = src->n_var_parts - 1;
1893   j = dst->n_var_parts - 1;
1894   dst->n_var_parts = k;
1895
1896   for (k--; k >= 0; k--)
1897     {
1898       location_chain node, node2;
1899
1900       if (i >= 0 && j >= 0
1901           && src->var_part[i].offset == dst->var_part[j].offset)
1902         {
1903           /* Compute the "sorted" union of the chains, i.e. the locations which
1904              are in both chains go first, they are sorted by the sum of
1905              positions in the chains.  */
1906           int dst_l, src_l;
1907           int ii, jj, n;
1908           struct variable_union_info *vui;
1909
1910           /* If DST is shared compare the location chains.
1911              If they are different we will modify the chain in DST with
1912              high probability so make a copy of DST.  */
1913           if (dst->refcount > 1 || shared_hash_shared (set->vars))
1914             {
1915               for (node = src->var_part[i].loc_chain,
1916                    node2 = dst->var_part[j].loc_chain; node && node2;
1917                    node = node->next, node2 = node2->next)
1918                 {
1919                   if (!((REG_P (node2->loc)
1920                          && REG_P (node->loc)
1921                          && REGNO (node2->loc) == REGNO (node->loc))
1922                         || rtx_equal_p (node2->loc, node->loc)))
1923                     {
1924                       if (node2->init < node->init)
1925                         node2->init = node->init;
1926                       break;
1927                     }
1928                 }
1929               if (node || node2)
1930                 {
1931                   dstp = unshare_variable (set, dstp, dst,
1932                                            VAR_INIT_STATUS_UNKNOWN);
1933                   dst = (variable)*dstp;
1934                 }
1935             }
1936
1937           src_l = 0;
1938           for (node = src->var_part[i].loc_chain; node; node = node->next)
1939             src_l++;
1940           dst_l = 0;
1941           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1942             dst_l++;
1943
1944           if (dst_l == 1)
1945             {
1946               /* The most common case, much simpler, no qsort is needed.  */
1947               location_chain dstnode = dst->var_part[j].loc_chain;
1948               dst->var_part[k].loc_chain = dstnode;
1949               dst->var_part[k].offset = dst->var_part[j].offset;
1950               node2 = dstnode;
1951               for (node = src->var_part[i].loc_chain; node; node = node->next)
1952                 if (!((REG_P (dstnode->loc)
1953                        && REG_P (node->loc)
1954                        && REGNO (dstnode->loc) == REGNO (node->loc))
1955                       || rtx_equal_p (dstnode->loc, node->loc)))
1956                   {
1957                     location_chain new_node;
1958
1959                     /* Copy the location from SRC.  */
1960                     new_node = (location_chain) pool_alloc (loc_chain_pool);
1961                     new_node->loc = node->loc;
1962                     new_node->init = node->init;
1963                     if (!node->set_src || MEM_P (node->set_src))
1964                       new_node->set_src = NULL;
1965                     else
1966                       new_node->set_src = node->set_src;
1967                     node2->next = new_node;
1968                     node2 = new_node;
1969                   }
1970               node2->next = NULL;
1971             }
1972           else
1973             {
1974               if (src_l + dst_l > vui_allocated)
1975                 {
1976                   vui_allocated = MAX (vui_allocated * 2, src_l + dst_l);
1977                   vui_vec = XRESIZEVEC (struct variable_union_info, vui_vec,
1978                                         vui_allocated);
1979                 }
1980               vui = vui_vec;
1981
1982               /* Fill in the locations from DST.  */
1983               for (node = dst->var_part[j].loc_chain, jj = 0; node;
1984                    node = node->next, jj++)
1985                 {
1986                   vui[jj].lc = node;
1987                   vui[jj].pos_dst = jj;
1988
1989                   /* Pos plus value larger than a sum of 2 valid positions.  */
1990                   vui[jj].pos = jj + src_l + dst_l;
1991                 }
1992
1993               /* Fill in the locations from SRC.  */
1994               n = dst_l;
1995               for (node = src->var_part[i].loc_chain, ii = 0; node;
1996                    node = node->next, ii++)
1997                 {
1998                   /* Find location from NODE.  */
1999                   for (jj = 0; jj < dst_l; jj++)
2000                     {
2001                       if ((REG_P (vui[jj].lc->loc)
2002                            && REG_P (node->loc)
2003                            && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
2004                           || rtx_equal_p (vui[jj].lc->loc, node->loc))
2005                         {
2006                           vui[jj].pos = jj + ii;
2007                           break;
2008                         }
2009                     }
2010                   if (jj >= dst_l)      /* The location has not been found.  */
2011                     {
2012                       location_chain new_node;
2013
2014                       /* Copy the location from SRC.  */
2015                       new_node = (location_chain) pool_alloc (loc_chain_pool);
2016                       new_node->loc = node->loc;
2017                       new_node->init = node->init;
2018                       if (!node->set_src || MEM_P (node->set_src))
2019                         new_node->set_src = NULL;
2020                       else
2021                         new_node->set_src = node->set_src;
2022                       vui[n].lc = new_node;
2023                       vui[n].pos_dst = src_l + dst_l;
2024                       vui[n].pos = ii + src_l + dst_l;
2025                       n++;
2026                     }
2027                 }
2028
2029               if (dst_l == 2)
2030                 {
2031                   /* Special case still very common case.  For dst_l == 2
2032                      all entries dst_l ... n-1 are sorted, with for i >= dst_l
2033                      vui[i].pos == i + src_l + dst_l.  */
2034                   if (vui[0].pos > vui[1].pos)
2035                     {
2036                       /* Order should be 1, 0, 2... */
2037                       dst->var_part[k].loc_chain = vui[1].lc;
2038                       vui[1].lc->next = vui[0].lc;
2039                       if (n >= 3)
2040                         {
2041                           vui[0].lc->next = vui[2].lc;
2042                           vui[n - 1].lc->next = NULL;
2043                         }
2044                       else
2045                         vui[0].lc->next = NULL;
2046                       ii = 3;
2047                     }
2048                   else
2049                     {
2050                       dst->var_part[k].loc_chain = vui[0].lc;
2051                       if (n >= 3 && vui[2].pos < vui[1].pos)
2052                         {
2053                           /* Order should be 0, 2, 1, 3... */
2054                           vui[0].lc->next = vui[2].lc;
2055                           vui[2].lc->next = vui[1].lc;
2056                           if (n >= 4)
2057                             {
2058                               vui[1].lc->next = vui[3].lc;
2059                               vui[n - 1].lc->next = NULL;
2060                             }
2061                           else
2062                             vui[1].lc->next = NULL;
2063                           ii = 4;
2064                         }
2065                       else
2066                         {
2067                           /* Order should be 0, 1, 2... */
2068                           ii = 1;
2069                           vui[n - 1].lc->next = NULL;
2070                         }
2071                     }
2072                   for (; ii < n; ii++)
2073                     vui[ii - 1].lc->next = vui[ii].lc;
2074                 }
2075               else
2076                 {
2077                   qsort (vui, n, sizeof (struct variable_union_info),
2078                          variable_union_info_cmp_pos);
2079
2080                   /* Reconnect the nodes in sorted order.  */
2081                   for (ii = 1; ii < n; ii++)
2082                     vui[ii - 1].lc->next = vui[ii].lc;
2083                   vui[n - 1].lc->next = NULL;
2084                   dst->var_part[k].loc_chain = vui[0].lc;
2085                 }
2086
2087               dst->var_part[k].offset = dst->var_part[j].offset;
2088             }
2089           i--;
2090           j--;
2091         }
2092       else if ((i >= 0 && j >= 0
2093                 && src->var_part[i].offset < dst->var_part[j].offset)
2094                || i < 0)
2095         {
2096           dst->var_part[k] = dst->var_part[j];
2097           j--;
2098         }
2099       else if ((i >= 0 && j >= 0
2100                 && src->var_part[i].offset > dst->var_part[j].offset)
2101                || j < 0)
2102         {
2103           location_chain *nextp;
2104
2105           /* Copy the chain from SRC.  */
2106           nextp = &dst->var_part[k].loc_chain;
2107           for (node = src->var_part[i].loc_chain; node; node = node->next)
2108             {
2109               location_chain new_lc;
2110
2111               new_lc = (location_chain) pool_alloc (loc_chain_pool);
2112               new_lc->next = NULL;
2113               new_lc->init = node->init;
2114               if (!node->set_src || MEM_P (node->set_src))
2115                 new_lc->set_src = NULL;
2116               else
2117                 new_lc->set_src = node->set_src;
2118               new_lc->loc = node->loc;
2119
2120               *nextp = new_lc;
2121               nextp = &new_lc->next;
2122             }
2123
2124           dst->var_part[k].offset = src->var_part[i].offset;
2125           i--;
2126         }
2127
2128       /* We are at the basic block boundary when computing union
2129          so set the CUR_LOC to be the first element of the chain.  */
2130       if (dst->var_part[k].loc_chain)
2131         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
2132       else
2133         dst->var_part[k].cur_loc = NULL;
2134     }
2135
2136   if (flag_var_tracking_uninit)
2137     for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++)
2138       {
2139         location_chain node, node2;
2140         for (node = src->var_part[i].loc_chain; node; node = node->next)
2141           for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next)
2142             if (rtx_equal_p (node->loc, node2->loc))
2143               {
2144                 if (node->init > node2->init)
2145                   node2->init = node->init;
2146               }
2147       }
2148
2149   /* Continue traversing the hash table.  */
2150   return 1;
2151 }
2152
2153 /* Like variable_union, but only used when doing dataflow_set_union
2154    into an empty hashtab.  To allow sharing, dst is initially shared
2155    with src (so all variables are "copied" from src to dst hashtab),
2156    so only unshare_variable for variables that need canonicalization
2157    are needed.  */
2158
2159 static int
2160 variable_canonicalize (void **slot, void *data)
2161 {
2162   variable src;
2163   dataflow_set *set = (dataflow_set *) data;
2164   int k;
2165
2166   src = *(variable *) slot;
2167
2168   /* If CUR_LOC of some variable part is not the first element of
2169      the location chain we are going to change it so we have to make
2170      a copy of the variable.  */
2171   for (k = 0; k < src->n_var_parts; k++)
2172     {
2173       gcc_assert (!src->var_part[k].loc_chain == !src->var_part[k].cur_loc);
2174       if (src->var_part[k].loc_chain)
2175         {
2176           gcc_assert (src->var_part[k].cur_loc);
2177           if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
2178             break;
2179         }
2180     }
2181   if (k < src->n_var_parts)
2182     slot = unshare_variable (set, slot, src, VAR_INIT_STATUS_UNKNOWN);
2183   return 1;
2184 }
2185
2186 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
2187
2188 static void
2189 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
2190 {
2191   int i;
2192
2193   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2194     attrs_list_union (&dst->regs[i], src->regs[i]);
2195
2196   if (dst->vars == empty_shared_hash)
2197     {
2198       shared_hash_destroy (dst->vars);
2199       dst->vars = shared_hash_copy (src->vars);
2200       dst->traversed_vars = dst->vars;
2201       htab_traverse (shared_hash_htab (dst->vars), variable_canonicalize, dst);
2202       dst->traversed_vars = NULL;
2203     }
2204   else
2205     htab_traverse (shared_hash_htab (src->vars), variable_union, dst);
2206 }
2207
2208 /* Whether the value is currently being expanded.  */
2209 #define VALUE_RECURSED_INTO(x) \
2210   (RTL_FLAG_CHECK2 ("VALUE_RECURSED_INTO", (x), VALUE, DEBUG_EXPR)->used)
2211 /* Whether the value is in changed_variables hash table.  */
2212 #define VALUE_CHANGED(x) \
2213   (RTL_FLAG_CHECK1 ("VALUE_CHANGED", (x), VALUE)->frame_related)
2214 /* Whether the decl is in changed_variables hash table.  */
2215 #define DECL_CHANGED(x) TREE_VISITED (x)
2216
2217 /* Record that DV has been added into resp. removed from changed_variables
2218    hashtable.  */
2219
2220 static inline void
2221 set_dv_changed (decl_or_value dv, bool newv)
2222 {
2223   if (dv_is_value_p (dv))
2224     VALUE_CHANGED (dv_as_value (dv)) = newv;
2225   else
2226     DECL_CHANGED (dv_as_decl (dv)) = newv;
2227 }
2228
2229 /* Return true if DV is present in changed_variables hash table.  */
2230
2231 static inline bool
2232 dv_changed_p (decl_or_value dv)
2233 {
2234   return (dv_is_value_p (dv)
2235           ? VALUE_CHANGED (dv_as_value (dv))
2236           : DECL_CHANGED (dv_as_decl (dv)));
2237 }
2238
2239 /* Vector of VALUEs that should have VALUE_RECURSED_INTO bit cleared
2240    at the end of find_loc_in_1pdv.  Not a static variable in find_loc_in_1pdv
2241    to avoid constant allocation/freeing of it.  */
2242 static VEC(rtx, heap) *values_to_unmark;
2243
2244 /* Helper function for find_loc_in_1pdv.
2245    Return a location list node whose loc is rtx_equal to LOC, in the
2246    location list of a one-part variable or value VAR, or in that of
2247    any values recursively mentioned in the location lists.  */
2248
2249 static location_chain
2250 find_loc_in_1pdv_1 (rtx loc, variable var, htab_t vars)
2251 {
2252   location_chain node;
2253
2254   if (!var)
2255     return NULL;
2256
2257   gcc_assert (dv_onepart_p (var->dv));
2258
2259   if (!var->n_var_parts)
2260     return NULL;
2261
2262   gcc_assert (var->var_part[0].offset == 0);
2263
2264   for (node = var->var_part[0].loc_chain; node; node = node->next)
2265     if (rtx_equal_p (loc, node->loc))
2266       return node;
2267     else if (GET_CODE (node->loc) == VALUE
2268              && !VALUE_RECURSED_INTO (node->loc))
2269       {
2270         decl_or_value dv = dv_from_value (node->loc);
2271         variable var = (variable)
2272                        htab_find_with_hash (vars, dv, dv_htab_hash (dv));
2273
2274         if (var)
2275           {
2276             location_chain where;
2277             VALUE_RECURSED_INTO (node->loc) = true;
2278             VEC_safe_push (rtx, heap, values_to_unmark, node->loc);
2279             if ((where = find_loc_in_1pdv_1 (loc, var, vars)))
2280               return where;
2281           }
2282       }
2283
2284   return NULL;
2285 }
2286
2287 /* Return a location list node whose loc is rtx_equal to LOC, in the
2288    location list of a one-part variable or value VAR, or in that of
2289    any values recursively mentioned in the location lists.  */
2290
2291 static location_chain
2292 find_loc_in_1pdv (rtx loc, variable var, htab_t vars)
2293 {
2294   location_chain ret;
2295   unsigned int i;
2296   rtx value;
2297
2298   ret = find_loc_in_1pdv_1 (loc, var, vars);
2299   for (i = 0; VEC_iterate (rtx, values_to_unmark, i, value); i++)
2300     VALUE_RECURSED_INTO (value) = false;
2301   VEC_truncate (rtx, values_to_unmark, 0);
2302   return ret;
2303 }
2304
2305 /* Hash table iteration argument passed to variable_merge.  */
2306 struct dfset_merge
2307 {
2308   /* The set in which the merge is to be inserted.  */
2309   dataflow_set *dst;
2310   /* The set that we're iterating in.  */
2311   dataflow_set *cur;
2312   /* The set that may contain the other dv we are to merge with.  */
2313   dataflow_set *src;
2314   /* Number of onepart dvs in src.  */
2315   int src_onepart_cnt;
2316 };
2317
2318 /* Insert LOC in *DNODE, if it's not there yet.  The list must be in
2319    loc_cmp order, and it is maintained as such.  */
2320
2321 static void
2322 insert_into_intersection (location_chain *nodep, rtx loc,
2323                           enum var_init_status status)
2324 {
2325   location_chain node;
2326   int r;
2327
2328   for (node = *nodep; node; nodep = &node->next, node = *nodep)
2329     if ((r = loc_cmp (node->loc, loc)) == 0)
2330       {
2331         node->init = MIN (node->init, status);
2332         return;
2333       }
2334     else if (r > 0)
2335       break;
2336
2337   node = (location_chain) pool_alloc (loc_chain_pool);
2338
2339   node->loc = loc;
2340   node->set_src = NULL;
2341   node->init = status;
2342   node->next = *nodep;
2343   *nodep = node;
2344 }
2345
2346 /* Insert in DEST the intersection the locations present in both
2347    S1NODE and S2VAR, directly or indirectly.  S1NODE is from a
2348    variable in DSM->cur, whereas S2VAR is from DSM->src.  dvar is in
2349    DSM->dst.  */
2350
2351 static void
2352 intersect_loc_chains (rtx val, location_chain *dest, struct dfset_merge *dsm,
2353                       location_chain s1node, variable s2var)
2354 {
2355   dataflow_set *s1set = dsm->cur;
2356   dataflow_set *s2set = dsm->src;
2357   location_chain found;
2358
2359   for (; s1node; s1node = s1node->next)
2360     {
2361       if (s1node->loc == val)
2362         continue;
2363
2364       if ((found = find_loc_in_1pdv (s1node->loc, s2var,
2365                                      shared_hash_htab (s2set->vars))))
2366         {
2367           insert_into_intersection (dest, s1node->loc,
2368                                     MIN (s1node->init, found->init));
2369           continue;
2370         }
2371
2372       if (GET_CODE (s1node->loc) == VALUE
2373           && !VALUE_RECURSED_INTO (s1node->loc))
2374         {
2375           decl_or_value dv = dv_from_value (s1node->loc);
2376           variable svar = shared_hash_find (s1set->vars, dv);
2377           if (svar)
2378             {
2379               if (svar->n_var_parts == 1)
2380                 {
2381                   VALUE_RECURSED_INTO (s1node->loc) = true;
2382                   intersect_loc_chains (val, dest, dsm,
2383                                         svar->var_part[0].loc_chain,
2384                                         s2var);
2385                   VALUE_RECURSED_INTO (s1node->loc) = false;
2386                 }
2387             }
2388         }
2389
2390       /* ??? if the location is equivalent to any location in src,
2391          searched recursively
2392
2393            add to dst the values needed to represent the equivalence
2394
2395      telling whether locations S is equivalent to another dv's
2396      location list:
2397
2398        for each location D in the list
2399
2400          if S and D satisfy rtx_equal_p, then it is present
2401
2402          else if D is a value, recurse without cycles
2403
2404          else if S and D have the same CODE and MODE
2405
2406            for each operand oS and the corresponding oD
2407
2408              if oS and oD are not equivalent, then S an D are not equivalent
2409
2410              else if they are RTX vectors
2411
2412                if any vector oS element is not equivalent to its respective oD,
2413                then S and D are not equivalent
2414
2415    */
2416
2417
2418     }
2419 }
2420
2421 /* Return -1 if X should be before Y in a location list for a 1-part
2422    variable, 1 if Y should be before X, and 0 if they're equivalent
2423    and should not appear in the list.  */
2424
2425 static int
2426 loc_cmp (rtx x, rtx y)
2427 {
2428   int i, j, r;
2429   RTX_CODE code = GET_CODE (x);
2430   const char *fmt;
2431
2432   if (x == y)
2433     return 0;
2434
2435   if (REG_P (x))
2436     {
2437       if (!REG_P (y))
2438         return -1;
2439       gcc_assert (GET_MODE (x) == GET_MODE (y));
2440       if (REGNO (x) == REGNO (y))
2441         return 0;
2442       else if (REGNO (x) < REGNO (y))
2443         return -1;
2444       else
2445         return 1;
2446     }
2447
2448   if (REG_P (y))
2449     return 1;
2450
2451   if (MEM_P (x))
2452     {
2453       if (!MEM_P (y))
2454         return -1;
2455       gcc_assert (GET_MODE (x) == GET_MODE (y));
2456       return loc_cmp (XEXP (x, 0), XEXP (y, 0));
2457     }
2458
2459   if (MEM_P (y))
2460     return 1;
2461
2462   if (GET_CODE (x) == VALUE)
2463     {
2464       if (GET_CODE (y) != VALUE)
2465         return -1;
2466       gcc_assert (GET_MODE (x) == GET_MODE (y));
2467       if (canon_value_cmp (x, y))
2468         return -1;
2469       else
2470         return 1;
2471     }
2472
2473   if (GET_CODE (y) == VALUE)
2474     return 1;
2475
2476   if (GET_CODE (x) == GET_CODE (y))
2477     /* Compare operands below.  */;
2478   else if (GET_CODE (x) < GET_CODE (y))
2479     return -1;
2480   else
2481     return 1;
2482
2483   gcc_assert (GET_MODE (x) == GET_MODE (y));
2484
2485   fmt = GET_RTX_FORMAT (code);
2486   for (i = 0; i < GET_RTX_LENGTH (code); i++)
2487     switch (fmt[i])
2488       {
2489       case 'w':
2490         if (XWINT (x, i) == XWINT (y, i))
2491           break;
2492         else if (XWINT (x, i) < XWINT (y, i))
2493           return -1;
2494         else
2495           return 1;
2496
2497       case 'n':
2498       case 'i':
2499         if (XINT (x, i) == XINT (y, i))
2500           break;
2501         else if (XINT (x, i) < XINT (y, i))
2502           return -1;
2503         else
2504           return 1;
2505
2506       case 'V':
2507       case 'E':
2508         /* Compare the vector length first.  */
2509         if (XVECLEN (x, i) == XVECLEN (y, i))
2510           /* Compare the vectors elements.  */;
2511         else if (XVECLEN (x, i) < XVECLEN (y, i))
2512           return -1;
2513         else
2514           return 1;
2515
2516         for (j = 0; j < XVECLEN (x, i); j++)
2517           if ((r = loc_cmp (XVECEXP (x, i, j),
2518                             XVECEXP (y, i, j))))
2519             return r;
2520         break;
2521
2522       case 'e':
2523         if ((r = loc_cmp (XEXP (x, i), XEXP (y, i))))
2524           return r;
2525         break;
2526
2527       case 'S':
2528       case 's':
2529         if (XSTR (x, i) == XSTR (y, i))
2530           break;
2531         if (!XSTR (x, i))
2532           return -1;
2533         if (!XSTR (y, i))
2534           return 1;
2535         if ((r = strcmp (XSTR (x, i), XSTR (y, i))) == 0)
2536           break;
2537         else if (r < 0)
2538           return -1;
2539         else
2540           return 1;
2541
2542       case 'u':
2543         /* These are just backpointers, so they don't matter.  */
2544         break;
2545
2546       case '0':
2547       case 't':
2548         break;
2549
2550         /* It is believed that rtx's at this level will never
2551            contain anything but integers and other rtx's,
2552            except for within LABEL_REFs and SYMBOL_REFs.  */
2553       default:
2554         gcc_unreachable ();
2555       }
2556
2557   return 0;
2558 }
2559
2560 /* If decl or value DVP refers to VALUE from *LOC, add backlinks
2561    from VALUE to DVP.  */
2562
2563 static int
2564 add_value_chain (rtx *loc, void *dvp)
2565 {
2566   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2567     {
2568       decl_or_value dv = (decl_or_value) dvp;
2569       decl_or_value ldv = dv_from_value (*loc);
2570       value_chain vc, nvc;
2571       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2572                                               dv_htab_hash (ldv), INSERT);
2573       if (!*slot)
2574         {
2575           vc = (value_chain) pool_alloc (value_chain_pool);
2576           vc->dv = ldv;
2577           vc->next = NULL;
2578           vc->refcount = 0;
2579           *slot = (void *) vc;
2580         }
2581       else
2582         {
2583           for (vc = ((value_chain) *slot)->next; vc; vc = vc->next)
2584             if (dv_as_opaque (vc->dv) == dv_as_opaque (dv))
2585               break;
2586           if (vc)
2587             {
2588               vc->refcount++;
2589               return 0;
2590             }
2591         }
2592       vc = (value_chain) *slot;
2593       nvc = (value_chain) pool_alloc (value_chain_pool);
2594       nvc->dv = dv;
2595       nvc->next = vc->next;
2596       nvc->refcount = 1;
2597       vc->next = nvc;
2598     }
2599   return 0;
2600 }
2601
2602 /* If decl or value DVP refers to VALUEs from within LOC, add backlinks
2603    from those VALUEs to DVP.  */
2604
2605 static void
2606 add_value_chains (decl_or_value dv, rtx loc)
2607 {
2608   if (GET_CODE (loc) == VALUE)
2609     {
2610       add_value_chain (&loc, dv_as_opaque (dv));
2611       return;
2612     }
2613   if (REG_P (loc))
2614     return;
2615   if (MEM_P (loc))
2616     loc = XEXP (loc, 0);
2617   for_each_rtx (&loc, add_value_chain, dv_as_opaque (dv));
2618 }
2619
2620 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, add backlinks from those
2621    VALUEs to DV.  */
2622
2623 static void
2624 add_cselib_value_chains (decl_or_value dv)
2625 {
2626   struct elt_loc_list *l;
2627
2628   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2629     for_each_rtx (&l->loc, add_value_chain, dv_as_opaque (dv));
2630 }
2631
2632 /* If decl or value DVP refers to VALUE from *LOC, remove backlinks
2633    from VALUE to DVP.  */
2634
2635 static int
2636 remove_value_chain (rtx *loc, void *dvp)
2637 {
2638   if (GET_CODE (*loc) == VALUE && (void *) *loc != dvp)
2639     {
2640       decl_or_value dv = (decl_or_value) dvp;
2641       decl_or_value ldv = dv_from_value (*loc);
2642       value_chain vc, dvc = NULL;
2643       void **slot = htab_find_slot_with_hash (value_chains, ldv,
2644                                               dv_htab_hash (ldv), NO_INSERT);
2645       for (vc = (value_chain) *slot; vc->next; vc = vc->next)
2646         if (dv_as_opaque (vc->next->dv) == dv_as_opaque (dv))
2647           {
2648             dvc = vc->next;
2649             gcc_assert (dvc->refcount > 0);
2650             if (--dvc->refcount == 0)
2651               {
2652                 vc->next = dvc->next;
2653                 pool_free (value_chain_pool, dvc);
2654                 if (vc->next == NULL && vc == (value_chain) *slot)
2655                   {
2656                     pool_free (value_chain_pool, vc);
2657                     htab_clear_slot (value_chains, slot);
2658                   }
2659               }
2660             return 0;
2661           }
2662       gcc_unreachable ();
2663     }
2664   return 0;
2665 }
2666
2667 /* If decl or value DVP refers to VALUEs from within LOC, remove backlinks
2668    from those VALUEs to DVP.  */
2669
2670 static void
2671 remove_value_chains (decl_or_value dv, rtx loc)
2672 {
2673   if (GET_CODE (loc) == VALUE)
2674     {
2675       remove_value_chain (&loc, dv_as_opaque (dv));
2676       return;
2677     }
2678   if (REG_P (loc))
2679     return;
2680   if (MEM_P (loc))
2681     loc = XEXP (loc, 0);
2682   for_each_rtx (&loc, remove_value_chain, dv_as_opaque (dv));
2683 }
2684
2685 /* If CSELIB_VAL_PTR of value DV refer to VALUEs, remove backlinks from those
2686    VALUEs to DV.  */
2687
2688 static void
2689 remove_cselib_value_chains (decl_or_value dv)
2690 {
2691   struct elt_loc_list *l;
2692
2693   for (l = CSELIB_VAL_PTR (dv_as_value (dv))->locs; l; l = l->next)
2694     for_each_rtx (&l->loc, remove_value_chain, dv_as_opaque (dv));
2695 }
2696
2697 #if ENABLE_CHECKING
2698 /* Check the order of entries in one-part variables.   */
2699
2700 static int
2701 canonicalize_loc_order_check (void **slot, void *data ATTRIBUTE_UNUSED)
2702 {
2703   variable var = (variable) *slot;
2704   decl_or_value dv = var->dv;
2705   location_chain node, next;
2706
2707   if (!dv_onepart_p (dv))
2708     return 1;
2709
2710   gcc_assert (var->n_var_parts == 1);
2711   node = var->var_part[0].loc_chain;
2712   gcc_assert (node);
2713
2714   while ((next = node->next))
2715     {
2716       gcc_assert (loc_cmp (node->loc, next->loc) < 0);
2717       node = next;
2718     }
2719
2720   return 1;
2721 }
2722 #endif
2723
2724 /* Mark with VALUE_RECURSED_INTO values that have neighbors that are
2725    more likely to be chosen as canonical for an equivalence set.
2726    Ensure less likely values can reach more likely neighbors, making
2727    the connections bidirectional.  */
2728
2729 static int
2730 canonicalize_values_mark (void **slot, void *data)
2731 {
2732   dataflow_set *set = (dataflow_set *)data;
2733   variable var = (variable) *slot;
2734   decl_or_value dv = var->dv;
2735   rtx val;
2736   location_chain node;
2737
2738   if (!dv_is_value_p (dv))
2739     return 1;
2740
2741   gcc_assert (var->n_var_parts == 1);
2742
2743   val = dv_as_value (dv);
2744
2745   for (node = var->var_part[0].loc_chain; node; node = node->next)
2746     if (GET_CODE (node->loc) == VALUE)
2747       {
2748         if (canon_value_cmp (node->loc, val))
2749           VALUE_RECURSED_INTO (val) = true;
2750         else
2751           {
2752             decl_or_value odv = dv_from_value (node->loc);
2753             void **oslot = shared_hash_find_slot_noinsert (set->vars, odv);
2754
2755             oslot = set_slot_part (set, val, oslot, odv, 0,
2756                                    node->init, NULL_RTX);
2757
2758             VALUE_RECURSED_INTO (node->loc) = true;
2759           }
2760       }
2761
2762   return 1;
2763 }
2764
2765 /* Remove redundant entries from equivalence lists in onepart
2766    variables, canonicalizing equivalence sets into star shapes.  */
2767
2768 static int
2769 canonicalize_values_star (void **slot, void *data)
2770 {
2771   dataflow_set *set = (dataflow_set *)data;
2772   variable var = (variable) *slot;
2773   decl_or_value dv = var->dv;
2774   location_chain node;
2775   decl_or_value cdv;
2776   rtx val, cval;
2777   void **cslot;
2778   bool has_value;
2779   bool has_marks;
2780
2781   if (!dv_onepart_p (dv))
2782     return 1;
2783
2784   gcc_assert (var->n_var_parts == 1);
2785
2786   if (dv_is_value_p (dv))
2787     {
2788       cval = dv_as_value (dv);
2789       if (!VALUE_RECURSED_INTO (cval))
2790         return 1;
2791       VALUE_RECURSED_INTO (cval) = false;
2792     }
2793   else
2794     cval = NULL_RTX;
2795
2796  restart:
2797   val = cval;
2798   has_value = false;
2799   has_marks = false;
2800
2801   gcc_assert (var->n_var_parts == 1);
2802
2803   for (node = var->var_part[0].loc_chain; node; node = node->next)
2804     if (GET_CODE (node->loc) == VALUE)
2805       {
2806         has_value = true;
2807         if (VALUE_RECURSED_INTO (node->loc))
2808           has_marks = true;
2809         if (canon_value_cmp (node->loc, cval))
2810           cval = node->loc;
2811       }
2812
2813   if (!has_value)
2814     return 1;
2815
2816   if (cval == val)
2817     {
2818       if (!has_marks || dv_is_decl_p (dv))
2819         return 1;
2820
2821       /* Keep it marked so that we revisit it, either after visiting a
2822          child node, or after visiting a new parent that might be
2823          found out.  */
2824       VALUE_RECURSED_INTO (val) = true;
2825
2826       for (node = var->var_part[0].loc_chain; node; node = node->next)
2827         if (GET_CODE (node->loc) == VALUE
2828             && VALUE_RECURSED_INTO (node->loc))
2829           {
2830             cval = node->loc;
2831           restart_with_cval:
2832             VALUE_RECURSED_INTO (cval) = false;
2833             dv = dv_from_value (cval);
2834             slot = shared_hash_find_slot_noinsert (set->vars, dv);
2835             if (!slot)
2836               {
2837                 gcc_assert (dv_is_decl_p (var->dv));
2838                 /* The canonical value was reset and dropped.
2839                    Remove it.  */
2840                 clobber_variable_part (set, NULL, var->dv, 0, NULL);
2841                 return 1;
2842               }
2843             var = (variable)*slot;
2844             gcc_assert (dv_is_value_p (var->dv));
2845             if (var->n_var_parts == 0)
2846               return 1;
2847             gcc_assert (var->n_var_parts == 1);
2848             goto restart;
2849           }
2850
2851       VALUE_RECURSED_INTO (val) = false;
2852
2853       return 1;
2854     }
2855
2856   /* Push values to the canonical one.  */
2857   cdv = dv_from_value (cval);
2858   cslot = shared_hash_find_slot_noinsert (set->vars, cdv);
2859
2860   for (node = var->var_part[0].loc_chain; node; node = node->next)
2861     if (node->loc != cval)
2862       {
2863         cslot = set_slot_part (set, node->loc, cslot, cdv, 0,
2864                                node->init, NULL_RTX);
2865         if (GET_CODE (node->loc) == VALUE)
2866           {
2867             decl_or_value ndv = dv_from_value (node->loc);
2868
2869             set_variable_part (set, cval, ndv, 0, node->init, NULL_RTX,
2870                                NO_INSERT);
2871
2872             if (canon_value_cmp (node->loc, val))
2873               {
2874                 /* If it could have been a local minimum, it's not any more,
2875                    since it's now neighbor to cval, so it may have to push
2876                    to it.  Conversely, if it wouldn't have prevailed over
2877                    val, then whatever mark it has is fine: if it was to
2878                    push, it will now push to a more canonical node, but if
2879                    it wasn't, then it has already pushed any values it might
2880                    have to.  */
2881                 VALUE_RECURSED_INTO (node->loc) = true;
2882                 /* Make sure we visit node->loc by ensuring we cval is
2883                    visited too.  */
2884                 VALUE_RECURSED_INTO (cval) = true;
2885               }
2886             else if (!VALUE_RECURSED_INTO (node->loc))
2887               /* If we have no need to "recurse" into this node, it's
2888                  already "canonicalized", so drop the link to the old
2889                  parent.  */
2890               clobber_variable_part (set, cval, ndv, 0, NULL);
2891           }
2892         else if (GET_CODE (node->loc) == REG)
2893           {
2894             attrs list = set->regs[REGNO (node->loc)], *listp;
2895
2896             /* Change an existing attribute referring to dv so that it
2897                refers to cdv, removing any duplicate this might
2898                introduce, and checking that no previous duplicates
2899                existed, all in a single pass.  */
2900
2901             while (list)
2902               {
2903                 if (list->offset == 0
2904                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2905                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2906                   break;
2907
2908                 list = list->next;
2909               }
2910
2911             gcc_assert (list);
2912             if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2913               {
2914                 list->dv = cdv;
2915                 for (listp = &list->next; (list = *listp); listp = &list->next)
2916                   {
2917                     if (list->offset)
2918                       continue;
2919
2920                     if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2921                       {
2922                         *listp = list->next;
2923                         pool_free (attrs_pool, list);
2924                         list = *listp;
2925                         break;
2926                       }
2927
2928                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (dv));
2929                   }
2930               }
2931             else if (dv_as_opaque (list->dv) == dv_as_opaque (cdv))
2932               {
2933                 for (listp = &list->next; (list = *listp); listp = &list->next)
2934                   {
2935                     if (list->offset)
2936                       continue;
2937
2938                     if (dv_as_opaque (list->dv) == dv_as_opaque (dv))
2939                       {
2940                         *listp = list->next;
2941                         pool_free (attrs_pool, list);
2942                         list = *listp;
2943                         break;
2944                       }
2945
2946                     gcc_assert (dv_as_opaque (list->dv) != dv_as_opaque (cdv));
2947                   }
2948               }
2949             else
2950               gcc_unreachable ();
2951
2952 #if ENABLE_CHECKING
2953             while (list)
2954               {
2955                 if (list->offset == 0
2956                     && (dv_as_opaque (list->dv) == dv_as_opaque (dv)
2957                         || dv_as_opaque (list->dv) == dv_as_opaque (cdv)))
2958                   gcc_unreachable ();
2959
2960                 list = list->next;
2961               }
2962 #endif
2963           }
2964       }
2965
2966   if (val)
2967     cslot = set_slot_part (set, val, cslot, cdv, 0,
2968                            VAR_INIT_STATUS_INITIALIZED, NULL_RTX);
2969
2970   slot = clobber_slot_part (set, cval, slot, 0, NULL);
2971
2972   /* Variable may have been unshared.  */
2973   var = (variable)*slot;
2974   gcc_assert (var->n_var_parts && var->var_part[0].loc_chain->loc == cval
2975               && var->var_part[0].loc_chain->next == NULL);
2976
2977   if (VALUE_RECURSED_INTO (cval))
2978     goto restart_with_cval;
2979
2980   return 1;
2981 }
2982
2983 /* Combine variable or value in *S1SLOT (in DSM->cur) with the
2984    corresponding entry in DSM->src.  Multi-part variables are combined
2985    with variable_union, whereas onepart dvs are combined with
2986    intersection.  */
2987
2988 static int
2989 variable_merge_over_cur (void **s1slot, void *data)
2990 {
2991   struct dfset_merge *dsm = (struct dfset_merge *)data;
2992   dataflow_set *dst = dsm->dst;
2993   void **dstslot;
2994   variable s1var = (variable) *s1slot;
2995   variable s2var, dvar = NULL;
2996   decl_or_value dv = s1var->dv;
2997   bool onepart = dv_onepart_p (dv);
2998   rtx val;
2999   hashval_t dvhash;
3000   location_chain node, *nodep;
3001
3002   /* If the incoming onepart variable has an empty location list, then
3003      the intersection will be just as empty.  For other variables,
3004      it's always union.  */
3005   gcc_assert (s1var->n_var_parts);
3006   gcc_assert (s1var->var_part[0].loc_chain);
3007
3008   if (!onepart)
3009     return variable_union (s1slot, dst);
3010
3011   gcc_assert (s1var->n_var_parts == 1);
3012   gcc_assert (s1var->var_part[0].offset == 0);
3013
3014   dvhash = dv_htab_hash (dv);
3015   if (dv_is_value_p (dv))
3016     val = dv_as_value (dv);
3017   else
3018     val = NULL;
3019
3020   s2var = shared_hash_find_1 (dsm->src->vars, dv, dvhash);
3021   if (!s2var)
3022     {
3023       dst_can_be_shared = false;
3024       return 1;
3025     }
3026
3027   dsm->src_onepart_cnt--;
3028   gcc_assert (s2var->var_part[0].loc_chain);
3029   gcc_assert (s2var->n_var_parts == 1);
3030   gcc_assert (s2var->var_part[0].offset == 0);
3031
3032   dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3033   if (dstslot)
3034     {
3035       dvar = (variable)*dstslot;
3036       gcc_assert (dvar->refcount == 1);
3037       gcc_assert (dvar->n_var_parts == 1);
3038       gcc_assert (dvar->var_part[0].offset == 0);
3039       nodep = &dvar->var_part[0].loc_chain;
3040     }
3041   else
3042     {
3043       nodep = &node;
3044       node = NULL;
3045     }
3046
3047   if (!dstslot && !onepart_variable_different_p (s1var, s2var))
3048     {
3049       dstslot = shared_hash_find_slot_unshare_1 (&dst->vars, dv,
3050                                                  dvhash, INSERT);
3051       *dstslot = dvar = s2var;
3052       dvar->refcount++;
3053     }
3054   else
3055     {
3056       dst_can_be_shared = false;
3057
3058       intersect_loc_chains (val, nodep, dsm,
3059                             s1var->var_part[0].loc_chain, s2var);
3060
3061       if (!dstslot)
3062         {
3063           if (node)
3064             {
3065               dvar = (variable) pool_alloc (dv_pool (dv));
3066               dvar->dv = dv;
3067               dvar->refcount = 1;
3068               dvar->n_var_parts = 1;
3069               dvar->var_part[0].offset = 0;
3070               dvar->var_part[0].loc_chain = node;
3071               dvar->var_part[0].cur_loc = node->loc;
3072
3073               dstslot
3074                 = shared_hash_find_slot_unshare_1 (&dst->vars, dv, dvhash,
3075                                                    INSERT);
3076               gcc_assert (!*dstslot);
3077               *dstslot = dvar;
3078             }
3079           else
3080             return 1;
3081         }
3082     }
3083
3084   nodep = &dvar->var_part[0].loc_chain;
3085   while ((node = *nodep))
3086     {
3087       location_chain *nextp = &node->next;
3088
3089       if (GET_CODE (node->loc) == REG)
3090         {
3091           attrs list;
3092
3093           for (list = dst->regs[REGNO (node->loc)]; list; list = list->next)
3094             if (GET_MODE (node->loc) == GET_MODE (list->loc)
3095                 && dv_is_value_p (list->dv))
3096               break;
3097
3098           if (!list)
3099             attrs_list_insert (&dst->regs[REGNO (node->loc)],
3100                                dv, 0, node->loc);
3101           /* If this value became canonical for another value that had
3102              this register, we want to leave it alone.  */
3103           else if (dv_as_value (list->dv) != val)
3104             {
3105               dstslot = set_slot_part (dst, dv_as_value (list->dv),
3106                                        dstslot, dv, 0,
3107                                        node->init, NULL_RTX);
3108               dstslot = delete_slot_part (dst, node->loc, dstslot, 0);
3109
3110               /* Since nextp points into the removed node, we can't
3111                  use it.  The pointer to the next node moved to nodep.
3112                  However, if the variable we're walking is unshared
3113                  during our walk, we'll keep walking the location list
3114                  of the previously-shared variable, in which case the
3115                  node won't have been removed, and we'll want to skip
3116                  it.  That's why we test *nodep here.  */
3117               if (*nodep != node)
3118                 nextp = nodep;
3119             }
3120         }
3121       else
3122         /* Canonicalization puts registers first, so we don't have to
3123            walk it all.  */
3124         break;
3125       nodep = nextp;
3126     }
3127
3128   if (dvar != (variable)*dstslot)
3129     dvar = (variable)*dstslot;
3130   nodep = &dvar->var_part[0].loc_chain;
3131
3132   if (val)
3133     {
3134       /* Mark all referenced nodes for canonicalization, and make sure
3135          we have mutual equivalence links.  */
3136       VALUE_RECURSED_INTO (val) = true;
3137       for (node = *nodep; node; node = node->next)
3138         if (GET_CODE (node->loc) == VALUE)
3139           {
3140             VALUE_RECURSED_INTO (node->loc) = true;
3141             set_variable_part (dst, val, dv_from_value (node->loc), 0,
3142                                node->init, NULL, INSERT);
3143           }
3144
3145       dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3146       gcc_assert (*dstslot == dvar);
3147       canonicalize_values_star (dstslot, dst);
3148 #ifdef ENABLE_CHECKING
3149       gcc_assert (dstslot
3150                   == shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash));
3151 #endif
3152       dvar = (variable)*dstslot;
3153     }
3154   else
3155     {
3156       bool has_value = false, has_other = false;
3157
3158       /* If we have one value and anything else, we're going to
3159          canonicalize this, so make sure all values have an entry in
3160          the table and are marked for canonicalization.  */
3161       for (node = *nodep; node; node = node->next)
3162         {
3163           if (GET_CODE (node->loc) == VALUE)
3164             {
3165               /* If this was marked during register canonicalization,
3166                  we know we have to canonicalize values.  */
3167               if (has_value)
3168                 has_other = true;
3169               has_value = true;
3170               if (has_other)
3171                 break;
3172             }
3173           else
3174             {
3175               has_other = true;
3176               if (has_value)
3177                 break;
3178             }
3179         }
3180
3181       if (has_value && has_other)
3182         {
3183           for (node = *nodep; node; node = node->next)
3184             {
3185               if (GET_CODE (node->loc) == VALUE)
3186                 {
3187                   decl_or_value dv = dv_from_value (node->loc);
3188                   void **slot = NULL;
3189
3190                   if (shared_hash_shared (dst->vars))
3191                     slot = shared_hash_find_slot_noinsert (dst->vars, dv);
3192                   if (!slot)
3193                     slot = shared_hash_find_slot_unshare (&dst->vars, dv,
3194                                                           INSERT);
3195                   if (!*slot)
3196                     {
3197                       variable var = (variable) pool_alloc (dv_pool (dv));
3198                       var->dv = dv;
3199                       var->refcount = 1;
3200                       var->n_var_parts = 1;
3201                       var->var_part[0].offset = 0;
3202                       var->var_part[0].loc_chain = NULL;
3203                       var->var_part[0].cur_loc = NULL;
3204                       *slot = var;
3205                     }
3206
3207                   VALUE_RECURSED_INTO (node->loc) = true;
3208                 }
3209             }
3210
3211           dstslot = shared_hash_find_slot_noinsert_1 (dst->vars, dv, dvhash);
3212           gcc_assert (*dstslot == dvar);
3213           canonicalize_values_star (dstslot, dst);
3214 #ifdef ENABLE_CHECKING
3215           gcc_assert (dstslot
3216                       == shared_hash_find_slot_noinsert_1 (dst->vars,
3217                                                            dv, dvhash));
3218 #endif
3219           dvar = (variable)*dstslot;
3220         }
3221     }
3222
3223   if (!onepart_variable_different_p (dvar, s2var))
3224     {
3225       variable_htab_free (dvar);
3226       *dstslot = dvar = s2var;
3227       dvar->refcount++;
3228     }
3229   else if (s2var != s1var && !onepart_variable_different_p (dvar, s1var))
3230     {
3231       variable_htab_free (dvar);
3232       *dstslot = dvar = s1var;
3233       dvar->refcount++;
3234       dst_can_be_shared = false;
3235     }
3236   else
3237     {
3238       if (dvar->refcount == 1)
3239         dvar->var_part[0].cur_loc = dvar->var_part[0].loc_chain->loc;
3240       dst_can_be_shared = false;
3241     }
3242
3243   return 1;
3244 }
3245
3246 /* Combine variable in *S1SLOT (in DSM->src) with the corresponding
3247    entry in DSM->src.  Only multi-part variables are combined, using
3248    variable_union.  onepart dvs were already combined with
3249    intersection in variable_merge_over_cur().  */
3250
3251 static int
3252 variable_merge_over_src (void **s2slot, void *data)
3253 {
3254   struct dfset_merge *dsm = (struct dfset_merge *)data;
3255   dataflow_set *dst = dsm->dst;
3256   variable s2var = (variable) *s2slot;
3257   decl_or_value dv = s2var->dv;
3258   bool onepart = dv_onepart_p (dv);
3259
3260   if (!onepart)
3261     {
3262       void **dstp = shared_hash_find_slot (dst->vars, dv);
3263       *dstp = s2var;
3264       s2var->refcount++;
3265       return variable_canonicalize (dstp, dst);
3266     }
3267
3268   dsm->src_onepart_cnt++;
3269   return 1;
3270 }
3271
3272 /* Combine dataflow set information from SRC into DST, using PDST
3273    to carry over information across passes.  */
3274
3275 static void
3276 dataflow_set_merge (dataflow_set *dst, dataflow_set *src)
3277 {
3278   dataflow_set src2 = *dst;
3279   struct dfset_merge dsm;
3280   int i;
3281   size_t src_elems, dst_elems;
3282
3283   src_elems = htab_elements (shared_hash_htab (src->vars));
3284   dst_elems = htab_elements (shared_hash_htab (src2.vars));
3285   dataflow_set_init (dst);
3286   dst->stack_adjust = src2.stack_adjust;
3287   shared_hash_destroy (dst->vars);
3288   dst->vars = (shared_hash) pool_alloc (shared_hash_pool);
3289   dst->vars->refcount = 1;
3290   dst->vars->htab
3291     = htab_create (MAX (src_elems, dst_elems), variable_htab_hash,
3292                    variable_htab_eq, variable_htab_free);
3293
3294   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3295     attrs_list_mpdv_union (&dst->regs[i], src->regs[i], src2.regs[i]);
3296
3297   dsm.dst = dst;
3298   dsm.src = &src2;
3299   dsm.cur = src;
3300   dsm.src_onepart_cnt = 0;
3301
3302   htab_traverse (shared_hash_htab (dsm.src->vars), variable_merge_over_src,
3303                  &dsm);
3304   htab_traverse (shared_hash_htab (dsm.cur->vars), variable_merge_over_cur,
3305                  &dsm);
3306
3307   if (dsm.src_onepart_cnt)
3308     dst_can_be_shared = false;
3309
3310   dataflow_set_destroy (&src2);
3311 }
3312
3313 /* Mark register equivalences.  */
3314
3315 static void
3316 dataflow_set_equiv_regs (dataflow_set *set)
3317 {
3318   int i;
3319   attrs list, *listp;
3320
3321   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3322     {
3323       rtx canon[NUM_MACHINE_MODES];
3324
3325       memset (canon, 0, sizeof (canon));
3326
3327       for (list = set->regs[i]; list; list = list->next)
3328         if (list->offset == 0 && dv_is_value_p (list->dv))
3329           {
3330             rtx val = dv_as_value (list->dv);
3331             rtx *cvalp = &canon[(int)GET_MODE (val)];
3332             rtx cval = *cvalp;
3333
3334             if (canon_value_cmp (val, cval))
3335               *cvalp = val;
3336           }
3337
3338       for (list = set->regs[i]; list; list = list->next)
3339         if (list->offset == 0 && dv_onepart_p (list->dv))
3340           {
3341             rtx cval = canon[(int)GET_MODE (list->loc)];
3342
3343             if (!cval)
3344               continue;
3345
3346             if (dv_is_value_p (list->dv))
3347               {
3348                 rtx val = dv_as_value (list->dv);
3349
3350                 if (val == cval)
3351                   continue;
3352
3353                 VALUE_RECURSED_INTO (val) = true;
3354                 set_variable_part (set, val, dv_from_value (cval), 0,
3355                                    VAR_INIT_STATUS_INITIALIZED,
3356                                    NULL, NO_INSERT);
3357               }
3358
3359             VALUE_RECURSED_INTO (cval) = true;
3360             set_variable_part (set, cval, list->dv, 0,
3361                                VAR_INIT_STATUS_INITIALIZED, NULL, NO_INSERT);
3362           }
3363
3364       for (listp = &set->regs[i]; (list = *listp);
3365            listp = list ? &list->next : listp)
3366         if (list->offset == 0 && dv_onepart_p (list->dv))
3367           {
3368             rtx cval = canon[(int)GET_MODE (list->loc)];
3369             void **slot;
3370
3371             if (!cval)
3372               continue;
3373
3374             if (dv_is_value_p (list->dv))
3375               {
3376                 rtx val = dv_as_value (list->dv);
3377                 if (!VALUE_RECURSED_INTO (val))
3378                   continue;
3379               }
3380
3381             slot = shared_hash_find_slot_noinsert (set->vars, list->dv);
3382             canonicalize_values_star (slot, set);
3383             if (*listp != list)
3384               list = NULL;
3385           }
3386     }
3387 }
3388
3389 /* Remove any redundant values in the location list of VAR, which must
3390    be unshared and 1-part.  */
3391
3392 static void
3393 remove_duplicate_values (variable var)
3394 {
3395   location_chain node, *nodep;
3396
3397   gcc_assert (dv_onepart_p (var->dv));
3398   gcc_assert (var->n_var_parts == 1);
3399   gcc_assert (var->refcount == 1);
3400
3401   for (nodep = &var->var_part[0].loc_chain; (node = *nodep); )
3402     {
3403       if (GET_CODE (node->loc) == VALUE)
3404         {
3405           if (VALUE_RECURSED_INTO (node->loc))
3406             {
3407               /* Remove duplicate value node.  */
3408               *nodep = node->next;
3409               pool_free (loc_chain_pool, node);
3410               continue;
3411             }
3412           else
3413             VALUE_RECURSED_INTO (node->loc) = true;
3414         }
3415       nodep = &node->next;
3416     }
3417
3418   for (node = var->var_part[0].loc_chain; node; node = node->next)
3419     if (GET_CODE (node->loc) == VALUE)
3420       {
3421         gcc_assert (VALUE_RECURSED_INTO (node->loc));
3422         VALUE_RECURSED_INTO (node->loc) = false;
3423       }
3424 }
3425
3426
3427 /* Hash table iteration argument passed to variable_post_merge.  */
3428 struct dfset_post_merge
3429 {
3430   /* The new input set for the current block.  */
3431   dataflow_set *set;
3432   /* Pointer to the permanent input set for the current block, or
3433      NULL.  */
3434   dataflow_set **permp;
3435 };
3436
3437 /* Create values for incoming expressions associated with one-part
3438    variables that don't have value numbers for them.  */
3439
3440 static int
3441 variable_post_merge_new_vals (void **slot, void *info)
3442 {
3443   struct dfset_post_merge *dfpm = (struct dfset_post_merge *)info;
3444   dataflow_set *set = dfpm->set;
3445   variable var = (variable)*slot;
3446   location_chain node;
3447
3448   if (!dv_onepart_p (var->dv) || !var->n_var_parts)
3449     return 1;
3450
3451   gcc_assert (var->n_var_parts == 1);
3452
3453   if (dv_is_decl_p (var->dv))
3454     {
3455       bool check_dupes = false;
3456
3457     restart:
3458       for (node = var->var_part[0].loc_chain; node; node = node->next)
3459         {
3460           if (GET_CODE (node->loc) == VALUE)
3461             gcc_assert (!VALUE_RECURSED_INTO (node->loc));
3462           else if (GET_CODE (node->loc) == REG)
3463             {
3464               attrs att, *attp, *curp = NULL;
3465
3466               if (var->refcount != 1)
3467                 {
3468                   slot = unshare_variable (set, slot, var,
3469                                            VAR_INIT_STATUS_INITIALIZED);
3470                   var = (variable)*slot;
3471                   goto restart;
3472                 }
3473
3474               for (attp = &set->regs[REGNO (node->loc)]; (att = *attp);
3475                    attp = &att->next)
3476                 if (att->offset == 0
3477                     && GET_MODE (att->loc) == GET_MODE (node->loc))
3478                   {
3479                     if (dv_is_value_p (att->dv))
3480                       {
3481                         rtx cval = dv_as_value (att->dv);
3482                         node->loc = cval;
3483                         check_dupes = true;
3484                         break;
3485                       }
3486                     else if (dv_as_opaque (att->dv) == dv_as_opaque (var->dv))
3487                       curp = attp;
3488                   }
3489
3490               if (!curp)
3491                 {
3492                   curp = attp;
3493                   while (*curp)
3494                     if ((*curp)->offset == 0
3495                         && GET_MODE ((*curp)->loc) == GET_MODE (node->loc)
3496                         && dv_as_opaque ((*curp)->dv) == dv_as_opaque (var->dv))
3497                       break;
3498                     else
3499                       curp = &(*curp)->next;
3500                   gcc_assert (*curp);
3501                 }
3502
3503               if (!att)
3504                 {
3505                   decl_or_value cdv;
3506                   rtx cval;
3507
3508                   if (!*dfpm->permp)
3509                     {
3510                       *dfpm->permp = XNEW (dataflow_set);
3511                       dataflow_set_init (*dfpm->permp);
3512                     }
3513
3514                   for (att = (*dfpm->permp)->regs[REGNO (node->loc)];
3515                        att; att = att->next)
3516                     if (GET_MODE (att->loc) == GET_MODE (node->loc))
3517                       {
3518                         gcc_assert (att->offset == 0);
3519                         gcc_assert (dv_is_value_p (att->dv));
3520                         val_reset (set, att->dv);
3521                         break;
3522                       }
3523
3524                   if (att)
3525                     {
3526                       cdv = att->dv;
3527                       cval = dv_as_value (cdv);
3528                     }
3529                   else
3530                     {
3531                       /* Create a unique value to hold this register,
3532                          that ought to be found and reused in
3533                          subsequent rounds.  */
3534                       cselib_val *v;
3535                       gcc_assert (!cselib_lookup (node->loc,
3536                                                   GET_MODE (node->loc), 0));
3537                       v = cselib_lookup (node->loc, GET_MODE (node->loc), 1);
3538                       cselib_preserve_value (v);
3539                       cselib_invalidate_rtx (node->loc);
3540                       cval = v->val_rtx;
3541                       cdv = dv_from_value (cval);
3542                       if (dump_file)
3543                         fprintf (dump_file,
3544                                  "Created new value %u:%u for reg %i\n",
3545                                  v->uid, v->hash, REGNO (node->loc));
3546                     }
3547
3548                   var_reg_decl_set (*dfpm->permp, node->loc,
3549                                     VAR_INIT_STATUS_INITIALIZED,
3550                                     cdv, 0, NULL, INSERT);
3551
3552                   node->loc = cval;
3553                   check_dupes = true;
3554                 }
3555
3556               /* Remove attribute referring to the decl, which now
3557                  uses the value for the register, already existing or
3558                  to be added when we bring perm in.  */
3559               att = *curp;
3560               *curp = att->next;
3561               pool_free (attrs_pool, att);
3562             }
3563         }
3564
3565       if (check_dupes)
3566         remove_duplicate_values (var);
3567     }
3568
3569   return 1;
3570 }
3571
3572 /* Reset values in the permanent set that are not associated with the
3573    chosen expression.  */
3574
3575 static int
3576 variable_post_merge_perm_vals (void **pslot, void *info)
3577 {
3578   struct dfset_post_merge *dfpm = (struct dfset_post_merge *)info;
3579   dataflow_set *set = dfpm->set;
3580   variable pvar = (variable)*pslot, var;
3581   location_chain pnode;
3582   decl_or_value dv;
3583   attrs att;
3584
3585   gcc_assert (dv_is_value_p (pvar->dv));
3586   gcc_assert (pvar->n_var_parts == 1);
3587   pnode = pvar->var_part[0].loc_chain;
3588   gcc_assert (pnode);
3589   gcc_assert (!pnode->next);
3590   gcc_assert (REG_P (pnode->loc));
3591
3592   dv = pvar->dv;
3593
3594   var = shared_hash_find (set->vars, dv);
3595   if (var)
3596     {
3597       if (find_loc_in_1pdv (pnode->loc, var, shared_hash_htab (set->vars)))
3598         return 1;
3599       val_reset (set, dv);
3600     }
3601
3602   for (att = set->regs[REGNO (pnode->loc)]; att; att = att->next)
3603     if (att->offset == 0
3604         && GET_MODE (att->loc) == GET_MODE (pnode->loc)
3605         && dv_is_value_p (att->dv))
3606       break;
3607
3608   /* If there is a value associated with this register already, create
3609      an equivalence.  */
3610   if (att && dv_as_value (att->dv) != dv_as_value (dv))
3611     {
3612       rtx cval = dv_as_value (att->dv);
3613       set_variable_part (set, cval, dv, 0, pnode->init, NULL, INSERT);
3614       set_variable_part (set, dv_as_value (dv), att->dv, 0, pnode->init,
3615                          NULL, INSERT);
3616     }
3617   else if (!att)
3618     {
3619       attrs_list_insert (&set->regs[REGNO (pnode->loc)],
3620                          dv, 0, pnode->loc);
3621       variable_union (pslot, set);
3622     }
3623
3624   return 1;
3625 }
3626
3627 /* Just checking stuff and registering register attributes for
3628    now.  */
3629
3630 static void
3631 dataflow_post_merge_adjust (dataflow_set *set, dataflow_set **permp)
3632 {
3633   struct dfset_post_merge dfpm;
3634
3635   dfpm.set = set;
3636   dfpm.permp = permp;
3637
3638   htab_traverse (shared_hash_htab (set->vars), variable_post_merge_new_vals,
3639                  &dfpm);
3640   if (*permp)
3641     htab_traverse (shared_hash_htab ((*permp)->vars),
3642                    variable_post_merge_perm_vals, &dfpm);
3643   htab_traverse (shared_hash_htab (set->vars), canonicalize_values_star, set);
3644 }
3645
3646 /* Return a node whose loc is a MEM that refers to EXPR in the
3647    location list of a one-part variable or value VAR, or in that of
3648    any values recursively mentioned in the location lists.  */
3649
3650 static location_chain
3651 find_mem_expr_in_1pdv (tree expr, rtx val, htab_t vars)
3652 {
3653   location_chain node;
3654   decl_or_value dv;
3655   variable var;
3656   location_chain where = NULL;
3657
3658   if (!val)
3659     return NULL;
3660
3661   gcc_assert (GET_CODE (val) == VALUE);
3662
3663   gcc_assert (!VALUE_RECURSED_INTO (val));
3664
3665   dv = dv_from_value (val);
3666   var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
3667
3668   if (!var)
3669     return NULL;
3670
3671   gcc_assert (dv_onepart_p (var->dv));
3672
3673   if (!var->n_var_parts)
3674     return NULL;
3675
3676   gcc_assert (var->var_part[0].offset == 0);
3677
3678   VALUE_RECURSED_INTO (val) = true;
3679
3680   for (node = var->var_part[0].loc_chain; node; node = node->next)
3681     if (MEM_P (node->loc) && MEM_EXPR (node->loc) == expr
3682         && MEM_OFFSET (node->loc) == 0)
3683       {
3684         where = node;
3685         break;
3686       }
3687     else if (GET_CODE (node->loc) == VALUE
3688              && !VALUE_RECURSED_INTO (node->loc)
3689              && (where = find_mem_expr_in_1pdv (expr, node->loc, vars)))
3690       break;
3691
3692   VALUE_RECURSED_INTO (val) = false;
3693
3694   return where;
3695 }
3696
3697 /* Return TRUE if the value of MEM may vary across a call.  */
3698
3699 static bool
3700 mem_dies_at_call (rtx mem)
3701 {
3702   tree expr = MEM_EXPR (mem);
3703   tree decl;
3704
3705   if (!expr)
3706     return true;
3707
3708   decl = get_base_address (expr);
3709
3710   if (!decl)
3711     return true;
3712
3713   if (!DECL_P (decl))
3714     return true;
3715
3716   return (may_be_aliased (decl)
3717           || (!TREE_READONLY (decl) && is_global_var (decl)));
3718 }
3719
3720 /* Remove all MEMs from the location list of a hash table entry for a
3721    one-part variable, except those whose MEM attributes map back to
3722    the variable itself, directly or within a VALUE.  */
3723
3724 static int
3725 dataflow_set_preserve_mem_locs (void **slot, void *data)
3726 {
3727   dataflow_set *set = (dataflow_set *) data;
3728   variable var = (variable) *slot;
3729
3730   if (dv_is_decl_p (var->dv) && dv_onepart_p (var->dv))
3731     {
3732       tree decl = dv_as_decl (var->dv);
3733       location_chain loc, *locp;
3734
3735       if (!var->n_var_parts)
3736         return 1;
3737
3738       gcc_assert (var->n_var_parts == 1);
3739
3740       if (var->refcount > 1 || shared_hash_shared (set->vars))
3741         {
3742           for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
3743             {
3744               /* We want to remove dying MEMs that doesn't refer to
3745                  DECL.  */
3746               if (GET_CODE (loc->loc) == MEM
3747                   && (MEM_EXPR (loc->loc) != decl
3748                       || MEM_OFFSET (loc->loc))
3749                   && !mem_dies_at_call (loc->loc))
3750                 break;
3751               /* We want to move here MEMs that do refer to DECL.  */
3752               else if (GET_CODE (loc->loc) == VALUE
3753                        && find_mem_expr_in_1pdv (decl, loc->loc,
3754                                                  shared_hash_htab (set->vars)))
3755                 break;
3756             }
3757
3758           if (!loc)
3759             return 1;
3760
3761           slot = unshare_variable (set, slot, var, VAR_INIT_STATUS_UNKNOWN);
3762           var = (variable)*slot;
3763           gcc_assert (var->n_var_parts == 1);
3764         }
3765
3766       for (locp = &var->var_part[0].loc_chain, loc = *locp;
3767            loc; loc = *locp)
3768         {
3769           rtx old_loc = loc->loc;
3770           if (GET_CODE (old_loc) == VALUE)
3771             {
3772               location_chain mem_node
3773                 = find_mem_expr_in_1pdv (decl, loc->loc,
3774                                          shared_hash_htab (set->vars));
3775
3776               /* ??? This picks up only one out of multiple MEMs that
3777                  refer to the same variable.  Do we ever need to be
3778                  concerned about dealing with more than one, or, given
3779                  that they should all map to the same variable
3780                  location, their addresses will have been merged and
3781                  they will be regarded as equivalent?  */
3782               if (mem_node)
3783                 {
3784                   loc->loc = mem_node->loc;
3785                   loc->set_src = mem_node->set_src;
3786                   loc->init = MIN (loc->init, mem_node->init);
3787                 }
3788             }
3789
3790           if (GET_CODE (loc->loc) != MEM
3791               || (MEM_EXPR (loc->loc) == decl
3792                   && MEM_OFFSET (loc->loc) == 0)
3793               || !mem_dies_at_call (loc->loc))
3794             {
3795               if (old_loc != loc->loc && emit_notes)
3796                 {
3797                   add_value_chains (var->dv, loc->loc);
3798                   remove_value_chains (var->dv, old_loc);
3799                 }
3800               locp = &loc->next;
3801               continue;
3802             }
3803
3804           if (emit_notes)
3805             remove_value_chains (var->dv, old_loc);
3806           *locp = loc->next;
3807           pool_free (loc_chain_pool, loc);
3808         }
3809
3810       if (!var->var_part[0].loc_chain)
3811         {
3812           var->n_var_parts--;
3813           if (emit_notes && dv_is_value_p (var->dv))
3814             remove_cselib_value_chains (var->dv);
3815           variable_was_changed (var, set);
3816         }
3817     }
3818
3819   return 1;
3820 }
3821
3822 /* Remove all MEMs from the location list of a hash table entry for a
3823    value.  */
3824
3825 static int
3826 dataflow_set_remove_mem_locs (void **slot, void *data)
3827 {
3828   dataflow_set *set = (dataflow_set *) data;
3829   variable var = (variable) *slot;
3830
3831   if (dv_is_value_p (var->dv))
3832     {
3833       location_chain loc, *locp;
3834       bool changed = false;
3835
3836       gcc_assert (var->n_var_parts == 1);
3837
3838       if (var->refcount > 1 || shared_hash_shared (set->vars))
3839         {
3840           for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
3841             if (GET_CODE (loc->loc) == MEM
3842                 && mem_dies_at_call (loc->loc))
3843               break;
3844
3845           if (!loc)
3846             return 1;
3847
3848           slot = unshare_variable (set, slot, var, VAR_INIT_STATUS_UNKNOWN);
3849           var = (variable)*slot;
3850           gcc_assert (var->n_var_parts == 1);
3851         }
3852
3853       for (locp = &var->var_part[0].loc_chain, loc = *locp;
3854            loc; loc = *locp)
3855         {
3856           if (GET_CODE (loc->loc) != MEM
3857               || !mem_dies_at_call (loc->loc))
3858             {
3859               locp = &loc->next;
3860               continue;
3861             }
3862
3863           if (emit_notes)
3864             remove_value_chains (var->dv, loc->loc);
3865           *locp = loc->next;
3866           /* If we have deleted the location which was last emitted
3867              we have to emit new location so add the variable to set
3868              of changed variables.  */
3869           if (var->var_part[0].cur_loc
3870               && rtx_equal_p (loc->loc, var->var_part[0].cur_loc))
3871             changed = true;
3872           pool_free (loc_chain_pool, loc);
3873         }
3874
3875       if (!var->var_part[0].loc_chain)
3876         {
3877           var->n_var_parts--;
3878           if (emit_notes && dv_is_value_p (var->dv))
3879             remove_cselib_value_chains (var->dv);
3880           gcc_assert (changed);
3881         }
3882       if (changed)
3883         {
3884           if (var->n_var_parts && var->var_part[0].loc_chain)
3885             var->var_part[0].cur_loc = var->var_part[0].loc_chain->loc;
3886           variable_was_changed (var, set);
3887         }
3888     }
3889
3890   return 1;
3891 }
3892
3893 /* Remove all variable-location information about call-clobbered
3894    registers, as well as associations between MEMs and VALUEs.  */
3895
3896 static void
3897 dataflow_set_clear_at_call (dataflow_set *set)
3898 {
3899   int r;
3900
3901   for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
3902     if (TEST_HARD_REG_BIT (call_used_reg_set, r))
3903       var_regno_delete (set, r);
3904
3905   if (MAY_HAVE_DEBUG_INSNS)
3906     {
3907       set->traversed_vars = set->vars;
3908       htab_traverse (shared_hash_htab (set->vars),
3909                      dataflow_set_preserve_mem_locs, set);
3910       set->traversed_vars = set->vars;
3911       htab_traverse (shared_hash_htab (set->vars), dataflow_set_remove_mem_locs,
3912                      set);
3913       set->traversed_vars = NULL;
3914     }
3915 }
3916
3917 /* Flag whether two dataflow sets being compared contain different data.  */
3918 static bool
3919 dataflow_set_different_value;
3920
3921 static bool
3922 variable_part_different_p (variable_part *vp1, variable_part *vp2)
3923 {
3924   location_chain lc1, lc2;
3925
3926   for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
3927     {
3928       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
3929         {
3930           if (REG_P (lc1->loc) && REG_P (lc2->loc))
3931             {
3932               if (REGNO (lc1->loc) == REGNO (lc2->loc))
3933                 break;
3934             }
3935           if (rtx_equal_p (lc1->loc, lc2->loc))
3936             break;
3937         }
3938       if (!lc2)
3939         return true;
3940     }
3941   return false;
3942 }
3943
3944 /* Return true if one-part variables VAR1 and VAR2 are different.
3945    They must be in canonical order.  */
3946
3947 static bool
3948 onepart_variable_different_p (variable var1, variable var2)
3949 {
3950   location_chain lc1, lc2;
3951
3952   if (var1 == var2)
3953     return false;
3954
3955   gcc_assert (var1->n_var_parts == 1);
3956   gcc_assert (var2->n_var_parts == 1);
3957
3958   lc1 = var1->var_part[0].loc_chain;
3959   lc2 = var2->var_part[0].loc_chain;
3960
3961   gcc_assert (lc1);
3962   gcc_assert (lc2);
3963
3964   while (lc1 && lc2)
3965     {
3966       if (loc_cmp (lc1->loc, lc2->loc))
3967         return true;
3968       lc1 = lc1->next;
3969       lc2 = lc2->next;
3970     }
3971
3972   return lc1 != lc2;
3973 }
3974
3975 /* Return true if variables VAR1 and VAR2 are different.
3976    If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
3977    variable part.  */
3978
3979 static bool
3980 variable_different_p (variable var1, variable var2,
3981                       bool compare_current_location)
3982 {
3983   int i;
3984
3985   if (var1 == var2)
3986     return false;
3987
3988   if (var1->n_var_parts != var2->n_var_parts)
3989     return true;
3990
3991   for (i = 0; i < var1->n_var_parts; i++)
3992     {
3993       if (var1->var_part[i].offset != var2->var_part[i].offset)
3994         return true;
3995       if (compare_current_location)
3996         {
3997           if (!((REG_P (var1->var_part[i].cur_loc)
3998                  && REG_P (var2->var_part[i].cur_loc)
3999                  && (REGNO (var1->var_part[i].cur_loc)
4000                      == REGNO (var2->var_part[i].cur_loc)))
4001                 || rtx_equal_p (var1->var_part[i].cur_loc,
4002                                 var2->var_part[i].cur_loc)))
4003             return true;
4004         }
4005       /* One-part values have locations in a canonical order.  */
4006       if (i == 0 && var1->var_part[i].offset == 0 && dv_onepart_p (var1->dv))
4007         {
4008           gcc_assert (var1->n_var_parts == 1);
4009           gcc_assert (dv_as_opaque (var1->dv) == dv_as_opaque (var2->dv));
4010           return onepart_variable_different_p (var1, var2);
4011         }
4012       if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
4013         return true;
4014       if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
4015         return true;
4016     }
4017   return false;
4018 }
4019
4020 /* Compare variable *SLOT with the same variable in hash table DATA
4021    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
4022
4023 static int
4024 dataflow_set_different_1 (void **slot, void *data)
4025 {
4026   htab_t htab = (htab_t) data;
4027   variable var1, var2;
4028
4029   var1 = (variable) *slot;
4030   var2 = (variable) htab_find_with_hash (htab, var1->dv,
4031                                          dv_htab_hash (var1->dv));
4032   if (!var2)
4033     {
4034       dataflow_set_different_value = true;
4035
4036       if (dump_file && (dump_flags & TDF_DETAILS))
4037         {
4038           fprintf (dump_file, "dataflow difference found: removal of:\n");
4039           dump_var (var1);
4040         }
4041
4042       /* Stop traversing the hash table.  */
4043       return 0;
4044     }
4045
4046   if (variable_different_p (var1, var2, false))
4047     {
4048       dataflow_set_different_value = true;
4049
4050       if (dump_file && (dump_flags & TDF_DETAILS))
4051         {
4052           fprintf (dump_file, "dataflow difference found: old and new follow:\n");
4053           dump_var (var1);
4054           dump_var (var2);
4055         }
4056
4057       /* Stop traversing the hash table.  */
4058       return 0;
4059     }
4060
4061   /* Continue traversing the hash table.  */
4062   return 1;
4063 }
4064
4065 /* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
4066
4067 static bool
4068 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
4069 {
4070   if (old_set->vars == new_set->vars)
4071     return false;
4072
4073   if (htab_elements (shared_hash_htab (old_set->vars))
4074       != htab_elements (shared_hash_htab (new_set->vars)))
4075     return true;
4076
4077   dataflow_set_different_value = false;
4078
4079   htab_traverse (shared_hash_htab (old_set->vars), dataflow_set_different_1,
4080                  shared_hash_htab (new_set->vars));
4081   /* No need to traverse the second hashtab, if both have the same number
4082      of elements and the second one had all entries found in the first one,
4083      then it can't have any extra entries.  */
4084   return dataflow_set_different_value;
4085 }
4086
4087 /* Free the contents of dataflow set SET.  */
4088
4089 static void
4090 dataflow_set_destroy (dataflow_set *set)
4091 {
4092   int i;
4093
4094   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4095     attrs_list_clear (&set->regs[i]);
4096
4097   shared_hash_destroy (set->vars);
4098   set->vars = NULL;
4099 }
4100
4101 /* Return true if RTL X contains a SYMBOL_REF.  */
4102
4103 static bool
4104 contains_symbol_ref (rtx x)
4105 {
4106   const char *fmt;
4107   RTX_CODE code;
4108   int i;
4109
4110   if (!x)
4111     return false;
4112
4113   code = GET_CODE (x);
4114   if (code == SYMBOL_REF)
4115     return true;
4116
4117   fmt = GET_RTX_FORMAT (code);
4118   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4119     {
4120       if (fmt[i] == 'e')
4121         {
4122           if (contains_symbol_ref (XEXP (x, i)))
4123             return true;
4124         }
4125       else if (fmt[i] == 'E')
4126         {
4127           int j;
4128           for (j = 0; j < XVECLEN (x, i); j++)
4129             if (contains_symbol_ref (XVECEXP (x, i, j)))
4130               return true;
4131         }
4132     }
4133
4134   return false;
4135 }
4136
4137 /* Shall EXPR be tracked?  */
4138
4139 static bool
4140 track_expr_p (tree expr, bool need_rtl)
4141 {
4142   rtx decl_rtl;
4143   tree realdecl;
4144
4145   if (TREE_CODE (expr) == DEBUG_EXPR_DECL)
4146     return DECL_RTL_SET_P (expr);
4147
4148   /* If EXPR is not a parameter or a variable do not track it.  */
4149   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
4150     return 0;
4151
4152   /* It also must have a name...  */
4153   if (!DECL_NAME (expr))
4154     return 0;
4155
4156   /* ... and a RTL assigned to it.  */
4157   decl_rtl = DECL_RTL_IF_SET (expr);
4158   if (!decl_rtl && need_rtl)
4159     return 0;
4160
4161   /* If this expression is really a debug alias of some other declaration, we
4162      don't need to track this expression if the ultimate declaration is
4163      ignored.  */
4164   realdecl = expr;
4165   if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
4166     {
4167       realdecl = DECL_DEBUG_EXPR (realdecl);
4168       /* ??? We don't yet know how to emit DW_OP_piece for variable
4169          that has been SRA'ed.  */
4170       if (!DECL_P (realdecl))
4171         return 0;
4172     }
4173
4174   /* Do not track EXPR if REALDECL it should be ignored for debugging
4175      purposes.  */
4176   if (DECL_IGNORED_P (realdecl))
4177     return 0;
4178
4179   /* Do not track global variables until we are able to emit correct location
4180      list for them.  */
4181   if (TREE_STATIC (realdecl))
4182     return 0;
4183
4184   /* When the EXPR is a DECL for alias of some variable (see example)
4185      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
4186      DECL_RTL contains SYMBOL_REF.
4187
4188      Example:
4189      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
4190      char **_dl_argv;
4191   */
4192   if (decl_rtl && MEM_P (decl_rtl)
4193       && contains_symbol_ref (XEXP (decl_rtl, 0)))
4194     return 0;
4195
4196   /* If RTX is a memory it should not be very large (because it would be
4197      an array or struct).  */
4198   if (decl_rtl && MEM_P (decl_rtl))
4199     {
4200       /* Do not track structures and arrays.  */
4201       if (GET_MODE (decl_rtl) == BLKmode
4202           || AGGREGATE_TYPE_P (TREE_TYPE (realdecl)))
4203         return 0;
4204       if (MEM_SIZE (decl_rtl)
4205           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
4206         return 0;
4207     }
4208
4209   DECL_CHANGED (expr) = 0;
4210   DECL_CHANGED (realdecl) = 0;
4211   return 1;
4212 }
4213
4214 /* Determine whether a given LOC refers to the same variable part as
4215    EXPR+OFFSET.  */
4216
4217 static bool
4218 same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset)
4219 {
4220   tree expr2;
4221   HOST_WIDE_INT offset2;
4222
4223   if (! DECL_P (expr))
4224     return false;
4225
4226   if (REG_P (loc))
4227     {
4228       expr2 = REG_EXPR (loc);
4229       offset2 = REG_OFFSET (loc);
4230     }
4231   else if (MEM_P (loc))
4232     {
4233       expr2 = MEM_EXPR (loc);
4234       offset2 = INT_MEM_OFFSET (loc);
4235     }
4236   else
4237     return false;
4238
4239   if (! expr2 || ! DECL_P (expr2))
4240     return false;
4241
4242   expr = var_debug_decl (expr);
4243   expr2 = var_debug_decl (expr2);
4244
4245   return (expr == expr2 && offset == offset2);
4246 }
4247
4248 /* LOC is a REG or MEM that we would like to track if possible.
4249    If EXPR is null, we don't know what expression LOC refers to,
4250    otherwise it refers to EXPR + OFFSET.  STORE_REG_P is true if
4251    LOC is an lvalue register.
4252
4253    Return true if EXPR is nonnull and if LOC, or some lowpart of it,
4254    is something we can track.  When returning true, store the mode of
4255    the lowpart we can track in *MODE_OUT (if nonnull) and its offset
4256    from EXPR in *OFFSET_OUT (if nonnull).  */
4257
4258 static bool
4259 track_loc_p (rtx loc, tree expr, HOST_WIDE_INT offset, bool store_reg_p,
4260              enum machine_mode *mode_out, HOST_WIDE_INT *offset_out)
4261 {
4262   enum machine_mode mode;
4263
4264   if (expr == NULL || !track_expr_p (expr, true))
4265     return false;
4266
4267   /* If REG was a paradoxical subreg, its REG_ATTRS will describe the
4268      whole subreg, but only the old inner part is really relevant.  */
4269   mode = GET_MODE (loc);
4270   if (REG_P (loc) && !HARD_REGISTER_NUM_P (ORIGINAL_REGNO (loc)))
4271     {
4272       enum machine_mode pseudo_mode;
4273
4274       pseudo_mode = PSEUDO_REGNO_MODE (ORIGINAL_REGNO (loc));
4275       if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (pseudo_mode))
4276         {
4277           offset += byte_lowpart_offset (pseudo_mode, mode);
4278           mode = pseudo_mode;
4279         }
4280     }
4281
4282   /* If LOC is a paradoxical lowpart of EXPR, refer to EXPR itself.
4283      Do the same if we are storing to a register and EXPR occupies
4284      the whole of register LOC; in that case, the whole of EXPR is
4285      being changed.  We exclude complex modes from the second case
4286      because the real and imaginary parts are represented as separate
4287      pseudo registers, even if the whole complex value fits into one
4288      hard register.  */
4289   if ((GET_MODE_SIZE (mode) > GET_MODE_SIZE (DECL_MODE (expr))
4290        || (store_reg_p
4291            && !COMPLEX_MODE_P (DECL_MODE (expr))
4292            && hard_regno_nregs[REGNO (loc)][DECL_MODE (expr)] == 1))
4293       && offset + byte_lowpart_offset (DECL_MODE (expr), mode) == 0)
4294     {
4295       mode = DECL_MODE (expr);
4296       offset = 0;
4297     }
4298
4299   if (offset < 0 || offset >= MAX_VAR_PARTS)
4300     return false;
4301
4302   if (mode_out)
4303     *mode_out = mode;
4304   if (offset_out)
4305     *offset_out = offset;
4306   return true;
4307 }
4308
4309 /* Return the MODE lowpart of LOC, or null if LOC is not something we
4310    want to track.  When returning nonnull, make sure that the attributes
4311    on the returned value are updated.  */
4312
4313 static rtx
4314 var_lowpart (enum machine_mode mode, rtx loc)
4315 {
4316   unsigned int offset, reg_offset, regno;
4317
4318   if (!REG_P (loc) && !MEM_P (loc))
4319     return NULL;
4320
4321   if (GET_MODE (loc) == mode)
4322     return loc;
4323
4324   offset = byte_lowpart_offset (mode, GET_MODE (loc));
4325
4326   if (MEM_P (loc))
4327     return adjust_address_nv (loc, mode, offset);
4328
4329   reg_offset = subreg_lowpart_offset (mode, GET_MODE (loc));
4330   regno = REGNO (loc) + subreg_regno_offset (REGNO (loc), GET_MODE (loc),
4331                                              reg_offset, mode);
4332   return gen_rtx_REG_offset (loc, mode, regno, offset);
4333 }
4334
4335 /* Carry information about uses and stores while walking rtx.  */
4336
4337 struct count_use_info
4338 {
4339   /* The insn where the RTX is.  */
4340   rtx insn;
4341
4342   /* The basic block where insn is.  */
4343   basic_block bb;
4344
4345   /* The array of n_sets sets in the insn, as determined by cselib.  */
4346   struct cselib_set *sets;
4347   int n_sets;
4348
4349   /* True if we're counting stores, false otherwise.  */
4350   bool store_p;
4351 };
4352
4353 /* Find a VALUE corresponding to X.   */
4354
4355 static inline cselib_val *
4356 find_use_val (rtx x, enum machine_mode mode, struct count_use_info *cui)
4357 {
4358   int i;
4359
4360   if (cui->sets)
4361     {
4362       /* This is called after uses are set up and before stores are
4363          processed bycselib, so it's safe to look up srcs, but not
4364          dsts.  So we look up expressions that appear in srcs or in
4365          dest expressions, but we search the sets array for dests of
4366          stores.  */
4367       if (cui->store_p)
4368         {
4369           for (i = 0; i < cui->n_sets; i++)
4370             if (cui->sets[i].dest == x)
4371               return cui->sets[i].src_elt;
4372         }
4373       else
4374         return cselib_lookup (x, mode, 0);
4375     }
4376
4377   return NULL;
4378 }
4379
4380 /* Replace all registers and addresses in an expression with VALUE
4381    expressions that map back to them, unless the expression is a
4382    register.  If no mapping is or can be performed, returns NULL.  */
4383
4384 static rtx
4385 replace_expr_with_values (rtx loc)
4386 {
4387   if (REG_P (loc))
4388     return NULL;
4389   else if (MEM_P (loc))
4390     {
4391       enum machine_mode address_mode
4392         = targetm.addr_space.address_mode (MEM_ADDR_SPACE (loc));
4393       cselib_val *addr = cselib_lookup (XEXP (loc, 0), address_mode, 0);
4394       if (addr)
4395         return replace_equiv_address_nv (loc, addr->val_rtx);
4396       else
4397         return NULL;
4398     }
4399   else
4400     return cselib_subst_to_values (loc);
4401 }
4402
4403 /* Determine what kind of micro operation to choose for a USE.  Return
4404    MO_CLOBBER if no micro operation is to be generated.  */
4405
4406 static enum micro_operation_type
4407 use_type (rtx loc, struct count_use_info *cui, enum machine_mode *modep)
4408 {
4409   tree expr;
4410
4411   if (cui && cui->sets)
4412     {
4413       if (GET_CODE (loc) == VAR_LOCATION)
4414         {
4415           if (track_expr_p (PAT_VAR_LOCATION_DECL (loc), false))
4416             {
4417               rtx ploc = PAT_VAR_LOCATION_LOC (loc);
4418               cselib_val *val = cselib_lookup (ploc, GET_MODE (loc), 1);
4419
4420               /* ??? flag_float_store and volatile mems are never
4421                  given values, but we could in theory use them for
4422                  locations.  */
4423               gcc_assert (val || 1);
4424               return MO_VAL_LOC;
4425             }
4426           else
4427             return MO_CLOBBER;
4428         }
4429
4430       if (REG_P (loc) || MEM_P (loc))
4431         {
4432           if (modep)
4433             *modep = GET_MODE (loc);
4434           if (cui->store_p)
4435             {
4436               if (REG_P (loc)
4437                   || (find_use_val (loc, GET_MODE (loc), cui)
4438                       && cselib_lookup (XEXP (loc, 0), GET_MODE (loc), 0)))
4439                 return MO_VAL_SET;
4440             }
4441           else
4442             {
4443               cselib_val *val = find_use_val (loc, GET_MODE (loc), cui);
4444
4445               if (val && !cselib_preserved_value_p (val))
4446                 return MO_VAL_USE;
4447             }
4448         }
4449     }
4450
4451   if (REG_P (loc))
4452     {
4453       gcc_assert (REGNO (loc) < FIRST_PSEUDO_REGISTER);
4454
4455       expr = REG_EXPR (loc);
4456
4457       if (!expr)
4458         return MO_USE_NO_VAR;
4459       else if (target_for_debug_bind (var_debug_decl (expr)))
4460         return MO_CLOBBER;
4461       else if (track_loc_p (loc, expr, REG_OFFSET (loc),
4462                             false, modep, NULL))
4463         return MO_USE;
4464       else
4465         return MO_USE_NO_VAR;
4466     }
4467   else if (MEM_P (loc))
4468     {
4469       expr = MEM_EXPR (loc);
4470
4471       if (!expr)
4472         return MO_CLOBBER;
4473       else if (target_for_debug_bind (var_debug_decl (expr)))
4474         return MO_CLOBBER;
4475       else if (track_loc_p (loc, expr, INT_MEM_OFFSET (loc),
4476                             false, modep, NULL))
4477         return MO_USE;
4478       else
4479         return MO_CLOBBER;
4480     }
4481
4482   return MO_CLOBBER;
4483 }
4484
4485 /* Log to OUT information about micro-operation MOPT involving X in
4486    INSN of BB.  */
4487
4488 static inline void
4489 log_op_type (rtx x, basic_block bb, rtx insn,
4490              enum micro_operation_type mopt, FILE *out)
4491 {
4492   fprintf (out, "bb %i op %i insn %i %s ",
4493            bb->index, VTI (bb)->n_mos - 1,
4494            INSN_UID (insn), micro_operation_type_name[mopt]);
4495   print_inline_rtx (out, x, 2);
4496   fputc ('\n', out);
4497 }
4498
4499 /* Count uses (register and memory references) LOC which will be tracked.
4500    INSN is instruction which the LOC is part of.  */
4501
4502 static int
4503 count_uses (rtx *ploc, void *cuip)
4504 {
4505   rtx loc = *ploc;
4506   struct count_use_info *cui = (struct count_use_info *) cuip;
4507   enum micro_operation_type mopt = use_type (loc, cui, NULL);
4508
4509   if (mopt != MO_CLOBBER)
4510     {
4511       cselib_val *val;
4512       enum machine_mode mode = GET_MODE (loc);
4513
4514       switch (mopt)
4515         {
4516         case MO_VAL_LOC:
4517           loc = PAT_VAR_LOCATION_LOC (loc);
4518           if (VAR_LOC_UNKNOWN_P (loc))
4519             break;
4520           /* Fall through.  */
4521
4522         case MO_VAL_USE:
4523         case MO_VAL_SET:
4524           if (MEM_P (loc)
4525               && !REG_P (XEXP (loc, 0)) && !MEM_P (XEXP (loc, 0)))
4526             {
4527               enum machine_mode address_mode
4528                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (loc));
4529               val = cselib_lookup (XEXP (loc, 0), address_mode, 0);
4530
4531               if (val && !cselib_preserved_value_p (val))
4532                 {
4533                   VTI (cui->bb)->n_mos++;
4534                   cselib_preserve_value (val);
4535                   if (dump_file && (dump_flags & TDF_DETAILS))
4536                     log_op_type (XEXP (loc, 0), cui->bb, cui->insn,
4537                                  MO_VAL_USE, dump_file);
4538                 }
4539             }
4540
4541           val = find_use_val (loc, mode, cui);
4542           if (val)
4543             {
4544               if (mopt == MO_VAL_SET
4545                   && GET_CODE (PATTERN (cui->insn)) == COND_EXEC
4546                   && (REG_P (loc)
4547                       || (MEM_P (loc)
4548                           && (use_type (loc, NULL, NULL) == MO_USE
4549                               || cui->sets))))
4550                 {
4551                   cselib_val *oval = cselib_lookup (loc, GET_MODE (loc), 0);
4552
4553                   gcc_assert (oval != val);
4554                   gcc_assert (REG_P (loc) || MEM_P (loc));
4555
4556                   if (!cselib_preserved_value_p (oval))
4557                     {
4558                       VTI (cui->bb)->n_mos++;
4559                       cselib_preserve_value (oval);
4560                       if (dump_file && (dump_flags & TDF_DETAILS))
4561                         log_op_type (loc, cui->bb, cui->insn,
4562                                      MO_VAL_USE, dump_file);
4563                     }
4564                 }
4565
4566               cselib_preserve_value (val);
4567             }
4568           else
4569             gcc_assert (mopt == MO_VAL_LOC
4570                         || (mopt == MO_VAL_SET && cui->store_p));
4571
4572           break;
4573
4574         default:
4575           break;
4576         }
4577
4578       VTI (cui->bb)->n_mos++;
4579       if (dump_file && (dump_flags & TDF_DETAILS))
4580         log_op_type (loc, cui->bb, cui->insn, mopt, dump_file);
4581     }
4582
4583   return 0;
4584 }
4585
4586 /* Helper function for finding all uses of REG/MEM in X in CUI's
4587    insn.  */
4588
4589 static void
4590 count_uses_1 (rtx *x, void *cui)
4591 {
4592   for_each_rtx (x, count_uses, cui);
4593 }
4594
4595 /* Count stores (register and memory references) LOC which will be
4596    tracked.  CUI is a count_use_info object containing the instruction
4597    which the LOC is part of.  */
4598
4599 static void
4600 count_stores (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *cui)
4601 {
4602   count_uses (&loc, cui);
4603 }
4604
4605 /* Callback for cselib_record_sets_hook, that counts how many micro
4606    operations it takes for uses and stores in an insn after
4607    cselib_record_sets has analyzed the sets in an insn, but before it
4608    modifies the stored values in the internal tables, unless
4609    cselib_record_sets doesn't call it directly (perhaps because we're
4610    not doing cselib in the first place, in which case sets and n_sets
4611    will be 0).  */
4612
4613 static void
4614 count_with_sets (rtx insn, struct cselib_set *sets, int n_sets)
4615 {
4616   basic_block bb = BLOCK_FOR_INSN (insn);
4617   struct count_use_info cui;
4618
4619   cselib_hook_called = true;
4620
4621   cui.insn = insn;
4622   cui.bb = bb;
4623   cui.sets = sets;
4624   cui.n_sets = n_sets;
4625
4626   cui.store_p = false;
4627   note_uses (&PATTERN (insn), count_uses_1, &cui);
4628   cui.store_p = true;
4629   note_stores (PATTERN (insn), count_stores, &cui);
4630 }
4631
4632 /* Tell whether the CONCAT used to holds a VALUE and its location
4633    needs value resolution, i.e., an attempt of mapping the location
4634    back to other incoming values.  */
4635 #define VAL_NEEDS_RESOLUTION(x) \
4636   (RTL_FLAG_CHECK1 ("VAL_NEEDS_RESOLUTION", (x), CONCAT)->volatil)
4637 /* Whether the location in the CONCAT is a tracked expression, that
4638    should also be handled like a MO_USE.  */
4639 #define VAL_HOLDS_TRACK_EXPR(x) \
4640   (RTL_FLAG_CHECK1 ("VAL_HOLDS_TRACK_EXPR", (x), CONCAT)->used)
4641 /* Whether the location in the CONCAT should be handled like a MO_COPY
4642    as well.  */
4643 #define VAL_EXPR_IS_COPIED(x) \
4644   (RTL_FLAG_CHECK1 ("VAL_EXPR_IS_COPIED", (x), CONCAT)->jump)
4645 /* Whether the location in the CONCAT should be handled like a
4646    MO_CLOBBER as well.  */
4647 #define VAL_EXPR_IS_CLOBBERED(x) \
4648   (RTL_FLAG_CHECK1 ("VAL_EXPR_IS_CLOBBERED", (x), CONCAT)->unchanging)
4649
4650 /* Add uses (register and memory references) LOC which will be tracked
4651    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
4652
4653 static int
4654 add_uses (rtx *ploc, void *data)
4655 {
4656   rtx loc = *ploc;
4657   enum machine_mode mode = VOIDmode;
4658   struct count_use_info *cui = (struct count_use_info *)data;
4659   enum micro_operation_type type = use_type (loc, cui, &mode);
4660
4661   if (type != MO_CLOBBER)
4662     {
4663       basic_block bb = cui->bb;
4664       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
4665
4666       mo->type = type;
4667       mo->u.loc = type == MO_USE ? var_lowpart (mode, loc) : loc;
4668       mo->insn = cui->insn;
4669
4670       if (type == MO_VAL_LOC)
4671         {
4672           rtx oloc = loc;
4673           rtx vloc = PAT_VAR_LOCATION_LOC (oloc);
4674           cselib_val *val;
4675
4676           gcc_assert (cui->sets);
4677
4678           if (MEM_P (vloc)
4679               && !REG_P (XEXP (vloc, 0)) && !MEM_P (XEXP (vloc, 0)))
4680             {
4681               rtx mloc = vloc;
4682               enum machine_mode address_mode
4683                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4684               cselib_val *val
4685                 = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4686
4687               if (val && !cselib_preserved_value_p (val))
4688                 {
4689                   micro_operation *mon = VTI (bb)->mos + VTI (bb)->n_mos++;
4690                   mon->type = mo->type;
4691                   mon->u.loc = mo->u.loc;
4692                   mon->insn = mo->insn;
4693                   cselib_preserve_value (val);
4694                   mo->type = MO_VAL_USE;
4695                   mloc = cselib_subst_to_values (XEXP (mloc, 0));
4696                   mo->u.loc = gen_rtx_CONCAT (address_mode,
4697                                               val->val_rtx, mloc);
4698                   if (dump_file && (dump_flags & TDF_DETAILS))
4699                     log_op_type (mo->u.loc, cui->bb, cui->insn,
4700                                  mo->type, dump_file);
4701                   mo = mon;
4702                 }
4703             }
4704
4705           if (!VAR_LOC_UNKNOWN_P (vloc)
4706               && (val = find_use_val (vloc, GET_MODE (oloc), cui)))
4707             {
4708               enum machine_mode mode2;
4709               enum micro_operation_type type2;
4710               rtx nloc = replace_expr_with_values (vloc);
4711
4712               if (nloc)
4713                 {
4714                   oloc = shallow_copy_rtx (oloc);
4715                   PAT_VAR_LOCATION_LOC (oloc) = nloc;
4716                 }
4717
4718               oloc = gen_rtx_CONCAT (mode, val->val_rtx, oloc);
4719
4720               type2 = use_type (vloc, 0, &mode2);
4721
4722               gcc_assert (type2 == MO_USE || type2 == MO_USE_NO_VAR
4723                           || type2 == MO_CLOBBER);
4724
4725               if (type2 == MO_CLOBBER
4726                   && !cselib_preserved_value_p (val))
4727                 {
4728                   VAL_NEEDS_RESOLUTION (oloc) = 1;
4729                   cselib_preserve_value (val);
4730                 }
4731             }
4732           else if (!VAR_LOC_UNKNOWN_P (vloc))
4733             {
4734               oloc = shallow_copy_rtx (oloc);
4735               PAT_VAR_LOCATION_LOC (oloc) = gen_rtx_UNKNOWN_VAR_LOC ();
4736             }
4737
4738           mo->u.loc = oloc;
4739         }
4740       else if (type == MO_VAL_USE)
4741         {
4742           enum machine_mode mode2 = VOIDmode;
4743           enum micro_operation_type type2;
4744           cselib_val *val = find_use_val (loc, GET_MODE (loc), cui);
4745           rtx vloc, oloc = loc, nloc;
4746
4747           gcc_assert (cui->sets);
4748
4749           if (MEM_P (oloc)
4750               && !REG_P (XEXP (oloc, 0)) && !MEM_P (XEXP (oloc, 0)))
4751             {
4752               rtx mloc = oloc;
4753               enum machine_mode address_mode
4754                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4755               cselib_val *val
4756                 = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4757
4758               if (val && !cselib_preserved_value_p (val))
4759                 {
4760                   micro_operation *mon = VTI (bb)->mos + VTI (bb)->n_mos++;
4761                   mon->type = mo->type;
4762                   mon->u.loc = mo->u.loc;
4763                   mon->insn = mo->insn;
4764                   cselib_preserve_value (val);
4765                   mo->type = MO_VAL_USE;
4766                   mloc = cselib_subst_to_values (XEXP (mloc, 0));
4767                   mo->u.loc = gen_rtx_CONCAT (address_mode,
4768                                               val->val_rtx, mloc);
4769                   mo->insn = cui->insn;
4770                   if (dump_file && (dump_flags & TDF_DETAILS))
4771                     log_op_type (mo->u.loc, cui->bb, cui->insn,
4772                                  mo->type, dump_file);
4773                   mo = mon;
4774                 }
4775             }
4776
4777           type2 = use_type (loc, 0, &mode2);
4778
4779           gcc_assert (type2 == MO_USE || type2 == MO_USE_NO_VAR
4780                       || type2 == MO_CLOBBER);
4781
4782           if (type2 == MO_USE)
4783             vloc = var_lowpart (mode2, loc);
4784           else
4785             vloc = oloc;
4786
4787           /* The loc of a MO_VAL_USE may have two forms:
4788
4789              (concat val src): val is at src, a value-based
4790              representation.
4791
4792              (concat (concat val use) src): same as above, with use as
4793              the MO_USE tracked value, if it differs from src.
4794
4795           */
4796
4797           nloc = replace_expr_with_values (loc);
4798           if (!nloc)
4799             nloc = oloc;
4800
4801           if (vloc != nloc)
4802             oloc = gen_rtx_CONCAT (mode2, val->val_rtx, vloc);
4803           else
4804             oloc = val->val_rtx;
4805
4806           mo->u.loc = gen_rtx_CONCAT (mode, oloc, nloc);
4807
4808           if (type2 == MO_USE)
4809             VAL_HOLDS_TRACK_EXPR (mo->u.loc) = 1;
4810           if (!cselib_preserved_value_p (val))
4811             {
4812               VAL_NEEDS_RESOLUTION (mo->u.loc) = 1;
4813               cselib_preserve_value (val);
4814             }
4815         }
4816       else
4817         gcc_assert (type == MO_USE || type == MO_USE_NO_VAR);
4818
4819       if (dump_file && (dump_flags & TDF_DETAILS))
4820         log_op_type (mo->u.loc, cui->bb, cui->insn, mo->type, dump_file);
4821     }
4822
4823   return 0;
4824 }
4825
4826 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
4827
4828 static void
4829 add_uses_1 (rtx *x, void *cui)
4830 {
4831   for_each_rtx (x, add_uses, cui);
4832 }
4833
4834 /* Add stores (register and memory references) LOC which will be tracked
4835    to VTI (bb)->mos.  EXPR is the RTL expression containing the store.
4836    CUIP->insn is instruction which the LOC is part of.  */
4837
4838 static void
4839 add_stores (rtx loc, const_rtx expr, void *cuip)
4840 {
4841   enum machine_mode mode = VOIDmode, mode2;
4842   struct count_use_info *cui = (struct count_use_info *)cuip;
4843   basic_block bb = cui->bb;
4844   micro_operation *mo;
4845   rtx oloc = loc, nloc, src = NULL;
4846   enum micro_operation_type type = use_type (loc, cui, &mode);
4847   bool track_p = false;
4848   cselib_val *v;
4849   bool resolve, preserve;
4850
4851   if (type == MO_CLOBBER)
4852     return;
4853
4854   mode2 = mode;
4855
4856   if (REG_P (loc))
4857     {
4858       mo = VTI (bb)->mos + VTI (bb)->n_mos++;
4859
4860       if ((GET_CODE (expr) == CLOBBER && type != MO_VAL_SET)
4861           || !(track_p = use_type (loc, NULL, &mode2) == MO_USE)
4862           || GET_CODE (expr) == CLOBBER)
4863         {
4864           mo->type = MO_CLOBBER;
4865           mo->u.loc = loc;
4866         }
4867       else
4868         {
4869           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
4870             src = var_lowpart (mode2, SET_SRC (expr));
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       mo = VTI (bb)->mos + VTI (bb)->n_mos++;
4898
4899       if (MEM_P (loc) && type == MO_VAL_SET
4900           && !REG_P (XEXP (loc, 0)) && !MEM_P (XEXP (loc, 0)))
4901         {
4902           rtx mloc = loc;
4903           enum machine_mode address_mode
4904             = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mloc));
4905           cselib_val *val = cselib_lookup (XEXP (mloc, 0), address_mode, 0);
4906
4907           if (val && !cselib_preserved_value_p (val))
4908             {
4909               cselib_preserve_value (val);
4910               mo->type = MO_VAL_USE;
4911               mloc = cselib_subst_to_values (XEXP (mloc, 0));
4912               mo->u.loc = gen_rtx_CONCAT (address_mode, val->val_rtx, mloc);
4913               mo->insn = cui->insn;
4914               if (dump_file && (dump_flags & TDF_DETAILS))
4915                 log_op_type (mo->u.loc, cui->bb, cui->insn,
4916                              mo->type, dump_file);
4917               mo = VTI (bb)->mos + VTI (bb)->n_mos++;
4918             }
4919         }
4920
4921       if (GET_CODE (expr) == CLOBBER || !track_p)
4922         {
4923           mo->type = MO_CLOBBER;
4924           mo->u.loc = track_p ? var_lowpart (mode2, loc) : loc;
4925         }
4926       else
4927         {
4928           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
4929             src = var_lowpart (mode2, SET_SRC (expr));
4930           loc = var_lowpart (mode2, loc);
4931
4932           if (src == NULL)
4933             {
4934               mo->type = MO_SET;
4935               mo->u.loc = loc;
4936             }
4937           else
4938             {
4939               rtx xexpr = CONST_CAST_RTX (expr);
4940
4941               if (SET_SRC (expr) != src)
4942                 xexpr = gen_rtx_SET (VOIDmode, loc, src);
4943               if (same_variable_part_p (SET_SRC (xexpr),
4944                                         MEM_EXPR (loc),
4945                                         INT_MEM_OFFSET (loc)))
4946                 mo->type = MO_COPY;
4947               else
4948                 mo->type = MO_SET;
4949               mo->u.loc = xexpr;
4950             }
4951         }
4952       mo->insn = cui->insn;
4953     }
4954   else
4955     return;
4956
4957   if (type != MO_VAL_SET)
4958     goto log_and_return;
4959
4960   v = find_use_val (oloc, mode, cui);
4961
4962   if (!v)
4963     goto log_and_return;
4964
4965   resolve = preserve = !cselib_preserved_value_p (v);
4966
4967   nloc = replace_expr_with_values (oloc);
4968   if (nloc)
4969     oloc = nloc;
4970
4971   if (GET_CODE (PATTERN (cui->insn)) == COND_EXEC)
4972     {
4973       cselib_val *oval = cselib_lookup (oloc, GET_MODE (oloc), 0);
4974
4975       gcc_assert (oval != v);
4976       gcc_assert (REG_P (oloc) || MEM_P (oloc));
4977
4978       if (!cselib_preserved_value_p (oval))
4979         {
4980           micro_operation *nmo = VTI (bb)->mos + VTI (bb)->n_mos++;
4981
4982           cselib_preserve_value (oval);
4983
4984           nmo->type = MO_VAL_USE;
4985           nmo->u.loc = gen_rtx_CONCAT (mode, oval->val_rtx, oloc);
4986           VAL_NEEDS_RESOLUTION (nmo->u.loc) = 1;
4987           nmo->insn = mo->insn;
4988
4989           if (dump_file && (dump_flags & TDF_DETAILS))
4990             log_op_type (nmo->u.loc, cui->bb, cui->insn,
4991                          nmo->type, dump_file);
4992         }
4993
4994       resolve = false;
4995     }
4996   else if (resolve && GET_CODE (mo->u.loc) == SET)
4997     {
4998       nloc = replace_expr_with_values (SET_SRC (expr));
4999
5000       /* Avoid the mode mismatch between oexpr and expr.  */
5001       if (!nloc && mode != mode2)
5002         {
5003           nloc = SET_SRC (expr);
5004           gcc_assert (oloc == SET_DEST (expr));
5005         }
5006
5007       if (nloc)
5008         oloc = gen_rtx_SET (GET_MODE (mo->u.loc), oloc, nloc);
5009       else
5010         {
5011           if (oloc == SET_DEST (mo->u.loc))
5012             /* No point in duplicating.  */
5013             oloc = mo->u.loc;
5014           if (!REG_P (SET_SRC (mo->u.loc)))
5015             resolve = false;
5016         }
5017     }
5018   else if (!resolve)
5019     {
5020       if (GET_CODE (mo->u.loc) == SET
5021           && oloc == SET_DEST (mo->u.loc))
5022         /* No point in duplicating.  */
5023         oloc = mo->u.loc;
5024     }
5025   else
5026     resolve = false;
5027
5028   loc = gen_rtx_CONCAT (mode, v->val_rtx, oloc);
5029
5030   if (mo->u.loc != oloc)
5031     loc = gen_rtx_CONCAT (GET_MODE (mo->u.loc), loc, mo->u.loc);
5032
5033   /* The loc of a MO_VAL_SET may have various forms:
5034
5035      (concat val dst): dst now holds val
5036
5037      (concat val (set dst src)): dst now holds val, copied from src
5038
5039      (concat (concat val dstv) dst): dst now holds val; dstv is dst
5040      after replacing mems and non-top-level regs with values.
5041
5042      (concat (concat val dstv) (set dst src)): dst now holds val,
5043      copied from src.  dstv is a value-based representation of dst, if
5044      it differs from dst.  If resolution is needed, src is a REG, and
5045      its mode is the same as that of val.
5046
5047      (concat (concat val (set dstv srcv)) (set dst src)): src
5048      copied to dst, holding val.  dstv and srcv are value-based
5049      representations of dst and src, respectively.
5050
5051   */
5052
5053   mo->u.loc = loc;
5054
5055   if (track_p)
5056     VAL_HOLDS_TRACK_EXPR (loc) = 1;
5057   if (preserve)
5058     {
5059       VAL_NEEDS_RESOLUTION (loc) = resolve;
5060       cselib_preserve_value (v);
5061     }
5062   if (mo->type == MO_CLOBBER)
5063     VAL_EXPR_IS_CLOBBERED (loc) = 1;
5064   if (mo->type == MO_COPY)
5065     VAL_EXPR_IS_COPIED (loc) = 1;
5066
5067   mo->type = MO_VAL_SET;
5068
5069  log_and_return:
5070   if (dump_file && (dump_flags & TDF_DETAILS))
5071     log_op_type (mo->u.loc, cui->bb, cui->insn, mo->type, dump_file);
5072 }
5073
5074 /* Callback for cselib_record_sets_hook, that records as micro
5075    operations uses and stores in an insn after cselib_record_sets has
5076    analyzed the sets in an insn, but before it modifies the stored
5077    values in the internal tables, unless cselib_record_sets doesn't
5078    call it directly (perhaps because we're not doing cselib in the
5079    first place, in which case sets and n_sets will be 0).  */
5080
5081 static void
5082 add_with_sets (rtx insn, struct cselib_set *sets, int n_sets)
5083 {
5084   basic_block bb = BLOCK_FOR_INSN (insn);
5085   int n1, n2;
5086   struct count_use_info cui;
5087
5088   cselib_hook_called = true;
5089
5090   cui.insn = insn;
5091   cui.bb = bb;
5092   cui.sets = sets;
5093   cui.n_sets = n_sets;
5094
5095   n1 = VTI (bb)->n_mos;
5096   cui.store_p = false;
5097   note_uses (&PATTERN (insn), add_uses_1, &cui);
5098   n2 = VTI (bb)->n_mos - 1;
5099
5100   /* Order the MO_USEs to be before MO_USE_NO_VARs and MO_VAL_USE, and
5101      MO_VAL_LOC last.  */
5102   while (n1 < n2)
5103     {
5104       while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
5105         n1++;
5106       while (n1 < n2 && VTI (bb)->mos[n2].type != MO_USE)
5107         n2--;
5108       if (n1 < n2)
5109         {
5110           micro_operation sw;
5111
5112           sw = VTI (bb)->mos[n1];
5113           VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
5114           VTI (bb)->mos[n2] = sw;
5115         }
5116     }
5117
5118   n2 = VTI (bb)->n_mos - 1;
5119
5120   while (n1 < n2)
5121     {
5122       while (n1 < n2 && VTI (bb)->mos[n1].type != MO_VAL_LOC)
5123         n1++;
5124       while (n1 < n2 && VTI (bb)->mos[n2].type == MO_VAL_LOC)
5125         n2--;
5126       if (n1 < n2)
5127         {
5128           micro_operation sw;
5129
5130           sw = VTI (bb)->mos[n1];
5131           VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
5132           VTI (bb)->mos[n2] = sw;
5133         }
5134     }
5135
5136   if (CALL_P (insn))
5137     {
5138       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
5139
5140       mo->type = MO_CALL;
5141       mo->insn = insn;
5142
5143       if (dump_file && (dump_flags & TDF_DETAILS))
5144         log_op_type (PATTERN (insn), bb, insn, mo->type, dump_file);
5145     }
5146
5147   n1 = VTI (bb)->n_mos;
5148   /* This will record NEXT_INSN (insn), such that we can
5149      insert notes before it without worrying about any
5150      notes that MO_USEs might emit after the insn.  */
5151   cui.store_p = true;
5152   note_stores (PATTERN (insn), add_stores, &cui);
5153   n2 = VTI (bb)->n_mos - 1;
5154
5155   /* Order the MO_CLOBBERs to be before MO_SETs.  */
5156   while (n1 < n2)
5157     {
5158       while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
5159         n1++;
5160       while (n1 < n2 && VTI (bb)->mos[n2].type != MO_CLOBBER)
5161         n2--;
5162       if (n1 < n2)
5163         {
5164           micro_operation sw;
5165
5166           sw = VTI (bb)->mos[n1];
5167           VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
5168           VTI (bb)->mos[n2] = sw;
5169         }
5170     }
5171 }
5172
5173 static enum var_init_status
5174 find_src_status (dataflow_set *in, rtx src)
5175 {
5176   tree decl = NULL_TREE;
5177   enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
5178
5179   if (! flag_var_tracking_uninit)
5180     status = VAR_INIT_STATUS_INITIALIZED;
5181
5182   if (src && REG_P (src))
5183     decl = var_debug_decl (REG_EXPR (src));
5184   else if (src && MEM_P (src))
5185     decl = var_debug_decl (MEM_EXPR (src));
5186
5187   if (src && decl)
5188     status = get_init_value (in, src, dv_from_decl (decl));
5189
5190   return status;
5191 }
5192
5193 /* SRC is the source of an assignment.  Use SET to try to find what
5194    was ultimately assigned to SRC.  Return that value if known,
5195    otherwise return SRC itself.  */
5196
5197 static rtx
5198 find_src_set_src (dataflow_set *set, rtx src)
5199 {
5200   tree decl = NULL_TREE;   /* The variable being copied around.          */
5201   rtx set_src = NULL_RTX;  /* The value for "decl" stored in "src".      */
5202   variable var;
5203   location_chain nextp;
5204   int i;
5205   bool found;
5206
5207   if (src && REG_P (src))
5208     decl = var_debug_decl (REG_EXPR (src));
5209   else if (src && MEM_P (src))
5210     decl = var_debug_decl (MEM_EXPR (src));
5211
5212   if (src && decl)
5213     {
5214       decl_or_value dv = dv_from_decl (decl);
5215
5216       var = shared_hash_find (set->vars, dv);
5217       if (var)
5218         {
5219           found = false;
5220           for (i = 0; i < var->n_var_parts && !found; i++)
5221             for (nextp = var->var_part[i].loc_chain; nextp && !found;
5222                  nextp = nextp->next)
5223               if (rtx_equal_p (nextp->loc, src))
5224                 {
5225                   set_src = nextp->set_src;
5226                   found = true;
5227                 }
5228
5229         }
5230     }
5231
5232   return set_src;
5233 }
5234
5235 /* Compute the changes of variable locations in the basic block BB.  */
5236
5237 static bool
5238 compute_bb_dataflow (basic_block bb)
5239 {
5240   int i, n;
5241   bool changed;
5242   dataflow_set old_out;
5243   dataflow_set *in = &VTI (bb)->in;
5244   dataflow_set *out = &VTI (bb)->out;
5245
5246   dataflow_set_init (&old_out);
5247   dataflow_set_copy (&old_out, out);
5248   dataflow_set_copy (out, in);
5249
5250   n = VTI (bb)->n_mos;
5251   for (i = 0; i < n; i++)
5252     {
5253       rtx insn = VTI (bb)->mos[i].insn;
5254
5255       switch (VTI (bb)->mos[i].type)
5256         {
5257           case MO_CALL:
5258             dataflow_set_clear_at_call (out);
5259             break;
5260
5261           case MO_USE:
5262             {
5263               rtx loc = VTI (bb)->mos[i].u.loc;
5264
5265               if (REG_P (loc))
5266                 var_reg_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
5267               else if (MEM_P (loc))
5268                 var_mem_set (out, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
5269             }
5270             break;
5271
5272           case MO_VAL_LOC:
5273             {
5274               rtx loc = VTI (bb)->mos[i].u.loc;
5275               rtx val, vloc;
5276               tree var;
5277
5278               if (GET_CODE (loc) == CONCAT)
5279                 {
5280                   val = XEXP (loc, 0);
5281                   vloc = XEXP (loc, 1);
5282                 }
5283               else
5284                 {
5285                   val = NULL_RTX;
5286                   vloc = loc;
5287                 }
5288
5289               var = PAT_VAR_LOCATION_DECL (vloc);
5290
5291               clobber_variable_part (out, NULL_RTX,
5292                                      dv_from_decl (var), 0, NULL_RTX);
5293               if (val)
5294                 {
5295                   if (VAL_NEEDS_RESOLUTION (loc))
5296                     val_resolve (out, val, PAT_VAR_LOCATION_LOC (vloc), insn);
5297                   set_variable_part (out, val, dv_from_decl (var), 0,
5298                                      VAR_INIT_STATUS_INITIALIZED, NULL_RTX,
5299                                      INSERT);
5300                 }
5301             }
5302             break;
5303
5304           case MO_VAL_USE:
5305             {
5306               rtx loc = VTI (bb)->mos[i].u.loc;
5307               rtx val, vloc, uloc;
5308
5309               vloc = uloc = XEXP (loc, 1);
5310               val = XEXP (loc, 0);
5311
5312               if (GET_CODE (val) == CONCAT)
5313                 {
5314                   uloc = XEXP (val, 1);
5315                   val = XEXP (val, 0);
5316                 }
5317
5318               if (VAL_NEEDS_RESOLUTION (loc))
5319                 val_resolve (out, val, vloc, insn);
5320               else
5321                 val_store (out, val, uloc, insn, false);
5322
5323               if (VAL_HOLDS_TRACK_EXPR (loc))
5324                 {
5325                   if (GET_CODE (uloc) == REG)
5326                     var_reg_set (out, uloc, VAR_INIT_STATUS_UNINITIALIZED,
5327                                  NULL);
5328                   else if (GET_CODE (uloc) == MEM)
5329                     var_mem_set (out, uloc, VAR_INIT_STATUS_UNINITIALIZED,
5330                                  NULL);
5331                 }
5332             }
5333             break;
5334
5335           case MO_VAL_SET:
5336             {
5337               rtx loc = VTI (bb)->mos[i].u.loc;
5338               rtx val, vloc, uloc;
5339
5340               vloc = uloc = XEXP (loc, 1);
5341               val = XEXP (loc, 0);
5342
5343               if (GET_CODE (val) == CONCAT)
5344                 {
5345                   vloc = XEXP (val, 1);
5346                   val = XEXP (val, 0);
5347                 }
5348
5349               if (GET_CODE (vloc) == SET)
5350                 {
5351                   rtx vsrc = SET_SRC (vloc);
5352
5353                   gcc_assert (val != vsrc);
5354                   gcc_assert (vloc == uloc || VAL_NEEDS_RESOLUTION (loc));
5355
5356                   vloc = SET_DEST (vloc);
5357
5358                   if (VAL_NEEDS_RESOLUTION (loc))
5359                     val_resolve (out, val, vsrc, insn);
5360                 }
5361               else if (VAL_NEEDS_RESOLUTION (loc))
5362                 {
5363                   gcc_assert (GET_CODE (uloc) == SET
5364                               && GET_CODE (SET_SRC (uloc)) == REG);
5365                   val_resolve (out, val, SET_SRC (uloc), insn);
5366                 }
5367
5368               if (VAL_HOLDS_TRACK_EXPR (loc))
5369                 {
5370                   if (VAL_EXPR_IS_CLOBBERED (loc))
5371                     {
5372                       if (REG_P (uloc))
5373                         var_reg_delete (out, uloc, true);
5374                       else if (MEM_P (uloc))
5375                         var_mem_delete (out, uloc, true);
5376                     }
5377                   else
5378                     {
5379                       bool copied_p = VAL_EXPR_IS_COPIED (loc);
5380                       rtx set_src = NULL;
5381                       enum var_init_status status = VAR_INIT_STATUS_INITIALIZED;
5382
5383                       if (GET_CODE (uloc) == SET)
5384                         {
5385                           set_src = SET_SRC (uloc);
5386                           uloc = SET_DEST (uloc);
5387                         }
5388
5389                       if (copied_p)
5390                         {
5391                           if (flag_var_tracking_uninit)
5392                             {
5393                               status = find_src_status (in, set_src);
5394
5395                               if (status == VAR_INIT_STATUS_UNKNOWN)
5396                                 status = find_src_status (out, set_src);
5397                             }
5398
5399                           set_src = find_src_set_src (in, set_src);
5400                         }
5401
5402                       if (REG_P (uloc))
5403                         var_reg_delete_and_set (out, uloc, !copied_p,
5404                                                 status, set_src);
5405                       else if (MEM_P (uloc))
5406                         var_mem_delete_and_set (out, uloc, !copied_p,
5407                                                 status, set_src);
5408                     }
5409                 }
5410               else if (REG_P (uloc))
5411                 var_regno_delete (out, REGNO (uloc));
5412
5413               val_store (out, val, vloc, insn, true);
5414             }
5415             break;
5416
5417           case MO_SET:
5418             {
5419               rtx loc = VTI (bb)->mos[i].u.loc;
5420               rtx set_src = NULL;
5421
5422               if (GET_CODE (loc) == SET)
5423                 {
5424                   set_src = SET_SRC (loc);
5425                   loc = SET_DEST (loc);
5426                 }
5427
5428               if (REG_P (loc))
5429                 var_reg_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
5430                                         set_src);
5431               else if (MEM_P (loc))
5432                 var_mem_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
5433                                         set_src);
5434             }
5435             break;
5436
5437           case MO_COPY:
5438             {
5439               rtx loc = VTI (bb)->mos[i].u.loc;
5440               enum var_init_status src_status;
5441               rtx set_src = NULL;
5442
5443               if (GET_CODE (loc) == SET)
5444                 {
5445                   set_src = SET_SRC (loc);
5446                   loc = SET_DEST (loc);
5447                 }
5448
5449               if (! flag_var_tracking_uninit)
5450                 src_status = VAR_INIT_STATUS_INITIALIZED;
5451               else
5452                 {
5453                   src_status = find_src_status (in, set_src);
5454
5455                   if (src_status == VAR_INIT_STATUS_UNKNOWN)
5456                     src_status = find_src_status (out, set_src);
5457                 }
5458
5459               set_src = find_src_set_src (in, set_src);
5460
5461               if (REG_P (loc))
5462                 var_reg_delete_and_set (out, loc, false, src_status, set_src);
5463               else if (MEM_P (loc))
5464                 var_mem_delete_and_set (out, loc, false, src_status, set_src);
5465             }
5466             break;
5467
5468           case MO_USE_NO_VAR:
5469             {
5470               rtx loc = VTI (bb)->mos[i].u.loc;
5471
5472               if (REG_P (loc))
5473                 var_reg_delete (out, loc, false);
5474               else if (MEM_P (loc))
5475                 var_mem_delete (out, loc, false);
5476             }
5477             break;
5478
5479           case MO_CLOBBER:
5480             {
5481               rtx loc = VTI (bb)->mos[i].u.loc;
5482
5483               if (REG_P (loc))
5484                 var_reg_delete (out, loc, true);
5485               else if (MEM_P (loc))
5486                 var_mem_delete (out, loc, true);
5487             }
5488             break;
5489
5490           case MO_ADJUST:
5491             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
5492             break;
5493         }
5494     }
5495
5496   if (MAY_HAVE_DEBUG_INSNS)
5497     {
5498       dataflow_set_equiv_regs (out);
5499       htab_traverse (shared_hash_htab (out->vars), canonicalize_values_mark,
5500                      out);
5501       htab_traverse (shared_hash_htab (out->vars), canonicalize_values_star,
5502                      out);
5503 #if ENABLE_CHECKING
5504       htab_traverse (shared_hash_htab (out->vars),
5505                      canonicalize_loc_order_check, out);
5506 #endif
5507     }
5508   changed = dataflow_set_different (&old_out, out);
5509   dataflow_set_destroy (&old_out);
5510   return changed;
5511 }
5512
5513 /* Find the locations of variables in the whole function.  */
5514
5515 static bool
5516 vt_find_locations (void)
5517 {
5518   fibheap_t worklist, pending, fibheap_swap;
5519   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
5520   basic_block bb;
5521   edge e;
5522   int *bb_order;
5523   int *rc_order;
5524   int i;
5525   int htabsz = 0;
5526   int htabmax = PARAM_VALUE (PARAM_MAX_VARTRACK_SIZE);
5527   bool success = true;
5528
5529   /* Compute reverse completion order of depth first search of the CFG
5530      so that the data-flow runs faster.  */
5531   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
5532   bb_order = XNEWVEC (int, last_basic_block);
5533   pre_and_rev_post_order_compute (NULL, rc_order, false);
5534   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
5535     bb_order[rc_order[i]] = i;
5536   free (rc_order);
5537
5538   worklist = fibheap_new ();
5539   pending = fibheap_new ();
5540   visited = sbitmap_alloc (last_basic_block);
5541   in_worklist = sbitmap_alloc (last_basic_block);
5542   in_pending = sbitmap_alloc (last_basic_block);
5543   sbitmap_zero (in_worklist);
5544
5545   FOR_EACH_BB (bb)
5546     fibheap_insert (pending, bb_order[bb->index], bb);
5547   sbitmap_ones (in_pending);
5548
5549   while (success && !fibheap_empty (pending))
5550     {
5551       fibheap_swap = pending;
5552       pending = worklist;
5553       worklist = fibheap_swap;
5554       sbitmap_swap = in_pending;
5555       in_pending = in_worklist;
5556       in_worklist = sbitmap_swap;
5557
5558       sbitmap_zero (visited);
5559
5560       while (!fibheap_empty (worklist))
5561         {
5562           bb = (basic_block) fibheap_extract_min (worklist);
5563           RESET_BIT (in_worklist, bb->index);
5564           if (!TEST_BIT (visited, bb->index))
5565             {
5566               bool changed;
5567               edge_iterator ei;
5568               int oldinsz, oldoutsz;
5569
5570               SET_BIT (visited, bb->index);
5571
5572               if (VTI (bb)->in.vars)
5573                 {
5574                   htabsz
5575                     -= (htab_size (shared_hash_htab (VTI (bb)->in.vars))
5576                         + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
5577                   oldinsz
5578                     = htab_elements (shared_hash_htab (VTI (bb)->in.vars));
5579                   oldoutsz
5580                     = htab_elements (shared_hash_htab (VTI (bb)->out.vars));
5581                 }
5582               else
5583                 oldinsz = oldoutsz = 0;
5584
5585               if (MAY_HAVE_DEBUG_INSNS)
5586                 {
5587                   dataflow_set *in = &VTI (bb)->in, *first_out = NULL;
5588                   bool first = true, adjust = false;
5589
5590                   /* Calculate the IN set as the intersection of
5591                      predecessor OUT sets.  */
5592
5593                   dataflow_set_clear (in);
5594                   dst_can_be_shared = true;
5595
5596                   FOR_EACH_EDGE (e, ei, bb->preds)
5597                     if (!VTI (e->src)->flooded)
5598                       gcc_assert (bb_order[bb->index]
5599                                   <= bb_order[e->src->index]);
5600                     else if (first)
5601                       {
5602                         dataflow_set_copy (in, &VTI (e->src)->out);
5603                         first_out = &VTI (e->src)->out;
5604                         first = false;
5605                       }
5606                     else
5607                       {
5608                         dataflow_set_merge (in, &VTI (e->src)->out);
5609                         adjust = true;
5610                       }
5611
5612                   if (adjust)
5613                     {
5614                       dataflow_post_merge_adjust (in, &VTI (bb)->permp);
5615 #if ENABLE_CHECKING
5616                       /* Merge and merge_adjust should keep entries in
5617                          canonical order.  */
5618                       htab_traverse (shared_hash_htab (in->vars),
5619                                      canonicalize_loc_order_check,
5620                                      in);
5621 #endif
5622                       if (dst_can_be_shared)
5623                         {
5624                           shared_hash_destroy (in->vars);
5625                           in->vars = shared_hash_copy (first_out->vars);
5626                         }
5627                     }
5628
5629                   VTI (bb)->flooded = true;
5630                 }
5631               else
5632                 {
5633                   /* Calculate the IN set as union of predecessor OUT sets.  */
5634                   dataflow_set_clear (&VTI (bb)->in);
5635                   FOR_EACH_EDGE (e, ei, bb->preds)
5636                     dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
5637                 }
5638
5639               changed = compute_bb_dataflow (bb);
5640               htabsz += (htab_size (shared_hash_htab (VTI (bb)->in.vars))
5641                          + htab_size (shared_hash_htab (VTI (bb)->out.vars)));
5642
5643               if (htabmax && htabsz > htabmax)
5644                 {
5645                   if (MAY_HAVE_DEBUG_INSNS)
5646                     inform (DECL_SOURCE_LOCATION (cfun->decl),
5647                             "variable tracking size limit exceeded with "
5648                             "-fvar-tracking-assignments, retrying without");
5649                   else
5650                     inform (DECL_SOURCE_LOCATION (cfun->decl),
5651                             "variable tracking size limit exceeded");
5652                   success = false;
5653                   break;
5654                 }
5655
5656               if (changed)
5657                 {
5658                   FOR_EACH_EDGE (e, ei, bb->succs)
5659                     {
5660                       if (e->dest == EXIT_BLOCK_PTR)
5661                         continue;
5662
5663                       if (TEST_BIT (visited, e->dest->index))
5664                         {
5665                           if (!TEST_BIT (in_pending, e->dest->index))
5666                             {
5667                               /* Send E->DEST to next round.  */
5668                               SET_BIT (in_pending, e->dest->index);
5669                               fibheap_insert (pending,
5670                                               bb_order[e->dest->index],
5671                                               e->dest);
5672                             }
5673                         }
5674                       else if (!TEST_BIT (in_worklist, e->dest->index))
5675                         {
5676                           /* Add E->DEST to current round.  */
5677                           SET_BIT (in_worklist, e->dest->index);
5678                           fibheap_insert (worklist, bb_order[e->dest->index],
5679                                           e->dest);
5680                         }
5681                     }
5682                 }
5683
5684               if (dump_file)
5685                 fprintf (dump_file,
5686                          "BB %i: in %i (was %i), out %i (was %i), rem %i + %i, tsz %i\n",
5687                          bb->index,
5688                          (int)htab_elements (shared_hash_htab (VTI (bb)->in.vars)),
5689                          oldinsz,
5690                          (int)htab_elements (shared_hash_htab (VTI (bb)->out.vars)),
5691                          oldoutsz,
5692                          (int)worklist->nodes, (int)pending->nodes, htabsz);
5693
5694               if (dump_file && (dump_flags & TDF_DETAILS))
5695                 {
5696                   fprintf (dump_file, "BB %i IN:\n", bb->index);
5697                   dump_dataflow_set (&VTI (bb)->in);
5698                   fprintf (dump_file, "BB %i OUT:\n", bb->index);
5699                   dump_dataflow_set (&VTI (bb)->out);
5700                 }
5701             }
5702         }
5703     }
5704
5705   if (success && MAY_HAVE_DEBUG_INSNS)
5706     FOR_EACH_BB (bb)
5707       gcc_assert (VTI (bb)->flooded);
5708
5709   VEC_free (rtx, heap, values_to_unmark);
5710   free (bb_order);
5711   fibheap_delete (worklist);
5712   fibheap_delete (pending);
5713   sbitmap_free (visited);
5714   sbitmap_free (in_worklist);
5715   sbitmap_free (in_pending);
5716
5717   return success;
5718 }
5719
5720 /* Print the content of the LIST to dump file.  */
5721
5722 static void
5723 dump_attrs_list (attrs list)
5724 {
5725   for (; list; list = list->next)
5726     {
5727       if (dv_is_decl_p (list->dv))
5728         print_mem_expr (dump_file, dv_as_decl (list->dv));
5729       else
5730         print_rtl_single (dump_file, dv_as_value (list->dv));
5731       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
5732     }
5733   fprintf (dump_file, "\n");
5734 }
5735
5736 /* Print the information about variable *SLOT to dump file.  */
5737
5738 static int
5739 dump_var_slot (void **slot, void *data ATTRIBUTE_UNUSED)
5740 {
5741   variable var = (variable) *slot;
5742
5743   dump_var (var);
5744
5745   /* Continue traversing the hash table.  */
5746   return 1;
5747 }
5748
5749 /* Print the information about variable VAR to dump file.  */
5750
5751 static void
5752 dump_var (variable var)
5753 {
5754   int i;
5755   location_chain node;
5756
5757   if (dv_is_decl_p (var->dv))
5758     {
5759       const_tree decl = dv_as_decl (var->dv);
5760
5761       if (DECL_NAME (decl))
5762         fprintf (dump_file, "  name: %s",
5763                  IDENTIFIER_POINTER (DECL_NAME (decl)));
5764       else
5765         fprintf (dump_file, "  name: D.%u", DECL_UID (decl));
5766       if (dump_flags & TDF_UID)
5767         fprintf (dump_file, " D.%u\n", DECL_UID (decl));
5768       else
5769         fprintf (dump_file, "\n");
5770     }
5771   else
5772     {
5773       fputc (' ', dump_file);
5774       print_rtl_single (dump_file, dv_as_value (var->dv));
5775     }
5776
5777   for (i = 0; i < var->n_var_parts; i++)
5778     {
5779       fprintf (dump_file, "    offset %ld\n",
5780                (long) var->var_part[i].offset);
5781       for (node = var->var_part[i].loc_chain; node; node = node->next)
5782         {
5783           fprintf (dump_file, "      ");
5784           if (node->init == VAR_INIT_STATUS_UNINITIALIZED)
5785             fprintf (dump_file, "[uninit]");
5786           print_rtl_single (dump_file, node->loc);
5787         }
5788     }
5789 }
5790
5791 /* Print the information about variables from hash table VARS to dump file.  */
5792
5793 static void
5794 dump_vars (htab_t vars)
5795 {
5796   if (htab_elements (vars) > 0)
5797     {
5798       fprintf (dump_file, "Variables:\n");
5799       htab_traverse (vars, dump_var_slot, NULL);
5800     }
5801 }
5802
5803 /* Print the dataflow set SET to dump file.  */
5804
5805 static void
5806 dump_dataflow_set (dataflow_set *set)
5807 {
5808   int i;
5809
5810   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
5811            set->stack_adjust);
5812   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5813     {
5814       if (set->regs[i])
5815         {
5816           fprintf (dump_file, "Reg %d:", i);
5817           dump_attrs_list (set->regs[i]);
5818         }
5819     }
5820   dump_vars (shared_hash_htab (set->vars));
5821   fprintf (dump_file, "\n");
5822 }
5823
5824 /* Print the IN and OUT sets for each basic block to dump file.  */
5825
5826 static void
5827 dump_dataflow_sets (void)
5828 {
5829   basic_block bb;
5830
5831   FOR_EACH_BB (bb)
5832     {
5833       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
5834       fprintf (dump_file, "IN:\n");
5835       dump_dataflow_set (&VTI (bb)->in);
5836       fprintf (dump_file, "OUT:\n");
5837       dump_dataflow_set (&VTI (bb)->out);
5838     }
5839 }
5840
5841 /* Add variable VAR to the hash table of changed variables and
5842    if it has no locations delete it from SET's hash table.  */
5843
5844 static void
5845 variable_was_changed (variable var, dataflow_set *set)
5846 {
5847   hashval_t hash = dv_htab_hash (var->dv);
5848
5849   if (emit_notes)
5850     {
5851       void **slot;
5852
5853       /* Remember this decl or VALUE has been added to changed_variables.  */
5854       set_dv_changed (var->dv, true);
5855
5856       slot = htab_find_slot_with_hash (changed_variables,
5857                                        var->dv,
5858                                        hash, INSERT);
5859
5860       if (set && var->n_var_parts == 0)
5861         {
5862           variable empty_var;
5863
5864           empty_var = (variable) pool_alloc (dv_pool (var->dv));
5865           empty_var->dv = var->dv;
5866           empty_var->refcount = 1;
5867           empty_var->n_var_parts = 0;
5868           *slot = empty_var;
5869           goto drop_var;
5870         }
5871       else
5872         {
5873           var->refcount++;
5874           *slot = var;
5875         }
5876     }
5877   else
5878     {
5879       gcc_assert (set);
5880       if (var->n_var_parts == 0)
5881         {
5882           void **slot;
5883
5884         drop_var:
5885           slot = shared_hash_find_slot_noinsert (set->vars, var->dv);
5886           if (slot)
5887             {
5888               if (shared_hash_shared (set->vars))
5889                 slot = shared_hash_find_slot_unshare (&set->vars, var->dv,
5890                                                       NO_INSERT);
5891               htab_clear_slot (shared_hash_htab (set->vars), slot);
5892             }
5893         }
5894     }
5895 }
5896
5897 /* Look for the index in VAR->var_part corresponding to OFFSET.
5898    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
5899    referenced int will be set to the index that the part has or should
5900    have, if it should be inserted.  */
5901
5902 static inline int
5903 find_variable_location_part (variable var, HOST_WIDE_INT offset,
5904                              int *insertion_point)
5905 {
5906   int pos, low, high;
5907
5908   /* Find the location part.  */
5909   low = 0;
5910   high = var->n_var_parts;
5911   while (low != high)
5912     {
5913       pos = (low + high) / 2;
5914       if (var->var_part[pos].offset < offset)
5915         low = pos + 1;
5916       else
5917         high = pos;
5918     }
5919   pos = low;
5920
5921   if (insertion_point)
5922     *insertion_point = pos;
5923
5924   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
5925     return pos;
5926
5927   return -1;
5928 }
5929
5930 static void **
5931 set_slot_part (dataflow_set *set, rtx loc, void **slot,
5932                decl_or_value dv, HOST_WIDE_INT offset,
5933                enum var_init_status initialized, rtx set_src)
5934 {
5935   int pos;
5936   location_chain node, next;
5937   location_chain *nextp;
5938   variable var;
5939   bool onepart = dv_onepart_p (dv);
5940
5941   gcc_assert (offset == 0 || !onepart);
5942   gcc_assert (loc != dv_as_opaque (dv));
5943
5944   var = (variable) *slot;
5945
5946   if (! flag_var_tracking_uninit)
5947     initialized = VAR_INIT_STATUS_INITIALIZED;
5948
5949   if (!var)
5950     {
5951       /* Create new variable information.  */
5952       var = (variable) pool_alloc (dv_pool (dv));
5953       var->dv = dv;
5954       var->refcount = 1;
5955       var->n_var_parts = 1;
5956       var->var_part[0].offset = offset;
5957       var->var_part[0].loc_chain = NULL;
5958       var->var_part[0].cur_loc = NULL;
5959       *slot = var;
5960       pos = 0;
5961       nextp = &var->var_part[0].loc_chain;
5962       if (emit_notes && dv_is_value_p (dv))
5963         add_cselib_value_chains (dv);
5964     }
5965   else if (onepart)
5966     {
5967       int r = -1, c = 0;
5968
5969       gcc_assert (dv_as_opaque (var->dv) == dv_as_opaque (dv));
5970
5971       pos = 0;
5972
5973       if (GET_CODE (loc) == VALUE)
5974         {
5975           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
5976                nextp = &node->next)
5977             if (GET_CODE (node->loc) == VALUE)
5978               {
5979                 if (node->loc == loc)
5980                   {
5981                     r = 0;
5982                     break;
5983                   }
5984                 if (canon_value_cmp (node->loc, loc))
5985                   c++;
5986                 else
5987                   {
5988                     r = 1;
5989                     break;
5990                   }
5991               }
5992             else if (REG_P (node->loc) || MEM_P (node->loc))
5993               c++;
5994             else
5995               {
5996                 r = 1;
5997                 break;
5998               }
5999         }
6000       else if (REG_P (loc))
6001         {
6002           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6003                nextp = &node->next)
6004             if (REG_P (node->loc))
6005               {
6006                 if (REGNO (node->loc) < REGNO (loc))
6007                   c++;
6008                 else
6009                   {
6010                     if (REGNO (node->loc) == REGNO (loc))
6011                       r = 0;
6012                     else
6013                       r = 1;
6014                     break;
6015                   }
6016               }
6017             else
6018               {
6019                 r = 1;
6020                 break;
6021               }
6022         }
6023       else if (MEM_P (loc))
6024         {
6025           for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6026                nextp = &node->next)
6027             if (REG_P (node->loc))
6028               c++;
6029             else if (MEM_P (node->loc))
6030               {
6031                 if ((r = loc_cmp (XEXP (node->loc, 0), XEXP (loc, 0))) >= 0)
6032                   break;
6033                 else
6034                   c++;
6035               }
6036             else
6037               {
6038                 r = 1;
6039                 break;
6040               }
6041         }
6042       else
6043         for (nextp = &var->var_part[0].loc_chain; (node = *nextp);
6044              nextp = &node->next)
6045           if ((r = loc_cmp (node->loc, loc)) >= 0)
6046             break;
6047           else
6048             c++;
6049
6050       if (r == 0)
6051         return slot;
6052
6053       if (var->refcount > 1 || shared_hash_shared (set->vars))
6054         {
6055           slot = unshare_variable (set, slot, var, initialized);
6056           var = (variable)*slot;
6057           for (nextp = &var->var_part[0].loc_chain; c;
6058                nextp = &(*nextp)->next)
6059             c--;
6060           gcc_assert ((!node && !*nextp) || node->loc == (*nextp)->loc);
6061         }
6062     }
6063   else
6064     {
6065       int inspos = 0;
6066
6067       gcc_assert (dv_as_decl (var->dv) == dv_as_decl (dv));
6068
6069       pos = find_variable_location_part (var, offset, &inspos);
6070
6071       if (pos >= 0)
6072         {
6073           node = var->var_part[pos].loc_chain;
6074
6075           if (node
6076               && ((REG_P (node->loc) && REG_P (loc)
6077                    && REGNO (node->loc) == REGNO (loc))
6078                   || rtx_equal_p (node->loc, loc)))
6079             {
6080               /* LOC is in the beginning of the chain so we have nothing
6081                  to do.  */
6082               if (node->init < initialized)
6083                 node->init = initialized;
6084               if (set_src != NULL)
6085                 node->set_src = set_src;
6086
6087               return slot;
6088             }
6089           else
6090             {
6091               /* We have to make a copy of a shared variable.  */
6092               if (var->refcount > 1 || shared_hash_shared (set->vars))
6093                 {
6094                   slot = unshare_variable (set, slot, var, initialized);
6095                   var = (variable)*slot;
6096                 }
6097             }
6098         }
6099       else
6100         {
6101           /* We have not found the location part, new one will be created.  */
6102
6103           /* We have to make a copy of the shared variable.  */
6104           if (var->refcount > 1 || shared_hash_shared (set->vars))
6105             {
6106               slot = unshare_variable (set, slot, var, initialized);
6107               var = (variable)*slot;
6108             }
6109
6110           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
6111              thus there are at most MAX_VAR_PARTS different offsets.  */
6112           gcc_assert (var->n_var_parts < MAX_VAR_PARTS
6113                       && (!var->n_var_parts || !dv_onepart_p (var->dv)));
6114
6115           /* We have to move the elements of array starting at index
6116              inspos to the next position.  */
6117           for (pos = var->n_var_parts; pos > inspos; pos--)
6118             var->var_part[pos] = var->var_part[pos - 1];
6119
6120           var->n_var_parts++;
6121           var->var_part[pos].offset = offset;
6122           var->var_part[pos].loc_chain = NULL;
6123           var->var_part[pos].cur_loc = NULL;
6124         }
6125
6126       /* Delete the location from the list.  */
6127       nextp = &var->var_part[pos].loc_chain;
6128       for (node = var->var_part[pos].loc_chain; node; node = next)
6129         {
6130           next = node->next;
6131           if ((REG_P (node->loc) && REG_P (loc)
6132                && REGNO (node->loc) == REGNO (loc))
6133               || rtx_equal_p (node->loc, loc))
6134             {
6135               /* Save these values, to assign to the new node, before
6136                  deleting this one.  */
6137               if (node->init > initialized)
6138                 initialized = node->init;
6139               if (node->set_src != NULL && set_src == NULL)
6140                 set_src = node->set_src;
6141               pool_free (loc_chain_pool, node);
6142               *nextp = next;
6143               break;
6144             }
6145           else
6146             nextp = &node->next;
6147         }
6148
6149       nextp = &var->var_part[pos].loc_chain;
6150     }
6151
6152   /* Add the location to the beginning.  */
6153   node = (location_chain) pool_alloc (loc_chain_pool);
6154   node->loc = loc;
6155   node->init = initialized;
6156   node->set_src = set_src;
6157   node->next = *nextp;
6158   *nextp = node;
6159
6160   if (onepart && emit_notes)
6161     add_value_chains (var->dv, loc);
6162
6163   /* If no location was emitted do so.  */
6164   if (var->var_part[pos].cur_loc == NULL)
6165     {
6166       var->var_part[pos].cur_loc = loc;
6167       variable_was_changed (var, set);
6168     }
6169
6170   return slot;
6171 }
6172
6173 /* Set the part of variable's location in the dataflow set SET.  The
6174    variable part is specified by variable's declaration in DV and
6175    offset OFFSET and the part's location by LOC.  IOPT should be
6176    NO_INSERT if the variable is known to be in SET already and the
6177    variable hash table must not be resized, and INSERT otherwise.  */
6178
6179 static void
6180 set_variable_part (dataflow_set *set, rtx loc,
6181                    decl_or_value dv, HOST_WIDE_INT offset,
6182                    enum var_init_status initialized, rtx set_src,
6183                    enum insert_option iopt)
6184 {
6185   void **slot;
6186
6187   if (iopt == NO_INSERT)
6188     slot = shared_hash_find_slot_noinsert (set->vars, dv);
6189   else
6190     {
6191       slot = shared_hash_find_slot (set->vars, dv);
6192       if (!slot)
6193         slot = shared_hash_find_slot_unshare (&set->vars, dv, iopt);
6194     }
6195   slot = set_slot_part (set, loc, slot, dv, offset, initialized, set_src);
6196 }
6197
6198 /* Remove all recorded register locations for the given variable part
6199    from dataflow set SET, except for those that are identical to loc.
6200    The variable part is specified by variable's declaration or value
6201    DV and offset OFFSET.  */
6202
6203 static void **
6204 clobber_slot_part (dataflow_set *set, rtx loc, void **slot,
6205                    HOST_WIDE_INT offset, rtx set_src)
6206 {
6207   variable var = (variable) *slot;
6208   int pos = find_variable_location_part (var, offset, NULL);
6209
6210   if (pos >= 0)
6211     {
6212       location_chain node, next;
6213
6214       /* Remove the register locations from the dataflow set.  */
6215       next = var->var_part[pos].loc_chain;
6216       for (node = next; node; node = next)
6217         {
6218           next = node->next;
6219           if (node->loc != loc
6220               && (!flag_var_tracking_uninit
6221                   || !set_src
6222                   || MEM_P (set_src)
6223                   || !rtx_equal_p (set_src, node->set_src)))
6224             {
6225               if (REG_P (node->loc))
6226                 {
6227                   attrs anode, anext;
6228                   attrs *anextp;
6229
6230                   /* Remove the variable part from the register's
6231                      list, but preserve any other variable parts
6232                      that might be regarded as live in that same
6233                      register.  */
6234                   anextp = &set->regs[REGNO (node->loc)];
6235                   for (anode = *anextp; anode; anode = anext)
6236                     {
6237                       anext = anode->next;
6238                       if (dv_as_opaque (anode->dv) == dv_as_opaque (var->dv)
6239                           && anode->offset == offset)
6240                         {
6241                           pool_free (attrs_pool, anode);
6242                           *anextp = anext;
6243                         }
6244                       else
6245                         anextp = &anode->next;
6246                     }
6247                 }
6248
6249               slot = delete_slot_part (set, node->loc, slot, offset);
6250             }
6251         }
6252     }
6253
6254   return slot;
6255 }
6256
6257 /* Remove all recorded register locations for the given variable part
6258    from dataflow set SET, except for those that are identical to loc.
6259    The variable part is specified by variable's declaration or value
6260    DV and offset OFFSET.  */
6261
6262 static void
6263 clobber_variable_part (dataflow_set *set, rtx loc, decl_or_value dv,
6264                        HOST_WIDE_INT offset, rtx set_src)
6265 {
6266   void **slot;
6267
6268   if (!dv_as_opaque (dv)
6269       || (!dv_is_value_p (dv) && ! DECL_P (dv_as_decl (dv))))
6270     return;
6271
6272   slot = shared_hash_find_slot_noinsert (set->vars, dv);
6273   if (!slot)
6274     return;
6275
6276   slot = clobber_slot_part (set, loc, slot, offset, set_src);
6277 }
6278
6279 /* Delete the part of variable's location from dataflow set SET.  The
6280    variable part is specified by its SET->vars slot SLOT and offset
6281    OFFSET and the part's location by LOC.  */
6282
6283 static void **
6284 delete_slot_part (dataflow_set *set, rtx loc, void **slot,
6285                   HOST_WIDE_INT offset)
6286 {
6287   variable var = (variable) *slot;
6288   int pos = find_variable_location_part (var, offset, NULL);
6289
6290   if (pos >= 0)
6291     {
6292       location_chain node, next;
6293       location_chain *nextp;
6294       bool changed;
6295
6296       if (var->refcount > 1 || shared_hash_shared (set->vars))
6297         {
6298           /* If the variable contains the location part we have to
6299              make a copy of the variable.  */
6300           for (node = var->var_part[pos].loc_chain; node;
6301                node = node->next)
6302             {
6303               if ((REG_P (node->loc) && REG_P (loc)
6304                    && REGNO (node->loc) == REGNO (loc))
6305                   || rtx_equal_p (node->loc, loc))
6306                 {
6307                   slot = unshare_variable (set, slot, var,
6308                                            VAR_INIT_STATUS_UNKNOWN);
6309                   var = (variable)*slot;
6310                   break;
6311                 }
6312             }
6313         }
6314
6315       /* Delete the location part.  */
6316       nextp = &var->var_part[pos].loc_chain;
6317       for (node = *nextp; node; node = next)
6318         {
6319           next = node->next;
6320           if ((REG_P (node->loc) && REG_P (loc)
6321                && REGNO (node->loc) == REGNO (loc))
6322               || rtx_equal_p (node->loc, loc))
6323             {
6324               if (emit_notes && pos == 0 && dv_onepart_p (var->dv))
6325                 remove_value_chains (var->dv, node->loc);
6326               pool_free (loc_chain_pool, node);
6327               *nextp = next;
6328               break;
6329             }
6330           else
6331             nextp = &node->next;
6332         }
6333
6334       /* If we have deleted the location which was last emitted
6335          we have to emit new location so add the variable to set
6336          of changed variables.  */
6337       if (var->var_part[pos].cur_loc
6338           && ((REG_P (loc)
6339                && REG_P (var->var_part[pos].cur_loc)
6340                && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
6341               || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
6342         {
6343           changed = true;
6344           if (var->var_part[pos].loc_chain)
6345             var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
6346         }
6347       else
6348         changed = false;
6349
6350       if (var->var_part[pos].loc_chain == NULL)
6351         {
6352           gcc_assert (changed);
6353           var->n_var_parts--;
6354           if (emit_notes && var->n_var_parts == 0 && dv_is_value_p (var->dv))
6355             remove_cselib_value_chains (var->dv);
6356           while (pos < var->n_var_parts)
6357             {
6358               var->var_part[pos] = var->var_part[pos + 1];
6359               pos++;
6360             }
6361         }
6362       if (changed)
6363         variable_was_changed (var, set);
6364     }
6365
6366   return slot;
6367 }
6368
6369 /* Delete the part of variable's location from dataflow set SET.  The
6370    variable part is specified by variable's declaration or value DV
6371    and offset OFFSET and the part's location by LOC.  */
6372
6373 static void
6374 delete_variable_part (dataflow_set *set, rtx loc, decl_or_value dv,
6375                       HOST_WIDE_INT offset)
6376 {
6377   void **slot = shared_hash_find_slot_noinsert (set->vars, dv);
6378   if (!slot)
6379     return;
6380
6381   slot = delete_slot_part (set, loc, slot, offset);
6382 }
6383
6384 /* Callback for cselib_expand_value, that looks for expressions
6385    holding the value in the var-tracking hash tables.  Return X for
6386    standard processing, anything else is to be used as-is.  */
6387
6388 static rtx
6389 vt_expand_loc_callback (rtx x, bitmap regs, int max_depth, void *data)
6390 {
6391   htab_t vars = (htab_t)data;
6392   decl_or_value dv;
6393   variable var;
6394   location_chain loc;
6395   rtx result, subreg, xret;
6396
6397   switch (GET_CODE (x))
6398     {
6399     case SUBREG:
6400       subreg = SUBREG_REG (x);
6401
6402       if (GET_CODE (SUBREG_REG (x)) != VALUE)
6403         return x;
6404
6405       subreg = cselib_expand_value_rtx_cb (SUBREG_REG (x), regs,
6406                                            max_depth - 1,
6407                                            vt_expand_loc_callback, data);
6408
6409       if (!subreg)
6410         return NULL;
6411
6412       result = simplify_gen_subreg (GET_MODE (x), subreg,
6413                                     GET_MODE (SUBREG_REG (x)),
6414                                     SUBREG_BYTE (x));
6415
6416       /* Invalid SUBREGs are ok in debug info.  ??? We could try
6417          alternate expansions for the VALUE as well.  */
6418       if (!result && (REG_P (subreg) || MEM_P (subreg)))
6419         result = gen_rtx_raw_SUBREG (GET_MODE (x), subreg, SUBREG_BYTE (x));
6420
6421       return result;
6422
6423     case DEBUG_EXPR:
6424       dv = dv_from_decl (DEBUG_EXPR_TREE_DECL (x));
6425       xret = NULL;
6426       break;
6427
6428     case VALUE:
6429       dv = dv_from_value (x);
6430       xret = x;
6431       break;
6432
6433     default:
6434       return x;
6435     }
6436
6437   if (VALUE_RECURSED_INTO (x))
6438     return NULL;
6439
6440   var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
6441
6442   if (!var)
6443     return xret;
6444
6445   if (var->n_var_parts == 0)
6446     return xret;
6447
6448   gcc_assert (var->n_var_parts == 1);
6449
6450   VALUE_RECURSED_INTO (x) = true;
6451   result = NULL;
6452
6453   for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
6454     {
6455       result = cselib_expand_value_rtx_cb (loc->loc, regs, max_depth,
6456                                            vt_expand_loc_callback, vars);
6457       if (result)
6458         break;
6459     }
6460
6461   VALUE_RECURSED_INTO (x) = false;
6462   if (result)
6463     return result;
6464   else
6465     return xret;
6466 }
6467
6468 /* Expand VALUEs in LOC, using VARS as well as cselib's equivalence
6469    tables.  */
6470
6471 static rtx
6472 vt_expand_loc (rtx loc, htab_t vars)
6473 {
6474   if (!MAY_HAVE_DEBUG_INSNS)
6475     return loc;
6476
6477   loc = cselib_expand_value_rtx_cb (loc, scratch_regs, 5,
6478                                     vt_expand_loc_callback, vars);
6479
6480   if (loc && MEM_P (loc))
6481     loc = targetm.delegitimize_address (loc);
6482
6483   return loc;
6484 }
6485
6486 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
6487    additional parameters: WHERE specifies whether the note shall be emitted
6488    before or after instruction INSN.  */
6489
6490 static int
6491 emit_note_insn_var_location (void **varp, void *data)
6492 {
6493   variable var = (variable) *varp;
6494   rtx insn = ((emit_note_data *)data)->insn;
6495   enum emit_note_where where = ((emit_note_data *)data)->where;
6496   htab_t vars = ((emit_note_data *)data)->vars;
6497   rtx note;
6498   int i, j, n_var_parts;
6499   bool complete;
6500   enum var_init_status initialized = VAR_INIT_STATUS_UNINITIALIZED;
6501   HOST_WIDE_INT last_limit;
6502   tree type_size_unit;
6503   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
6504   rtx loc[MAX_VAR_PARTS];
6505   tree decl;
6506
6507   if (dv_is_value_p (var->dv))
6508     goto clear;
6509
6510   decl = dv_as_decl (var->dv);
6511
6512   if (TREE_CODE (decl) == DEBUG_EXPR_DECL)
6513     goto clear;
6514
6515   gcc_assert (decl);
6516
6517   complete = true;
6518   last_limit = 0;
6519   n_var_parts = 0;
6520   for (i = 0; i < var->n_var_parts; i++)
6521     {
6522       enum machine_mode mode, wider_mode;
6523       rtx loc2;
6524
6525       if (last_limit < var->var_part[i].offset)
6526         {
6527           complete = false;
6528           break;
6529         }
6530       else if (last_limit > var->var_part[i].offset)
6531         continue;
6532       offsets[n_var_parts] = var->var_part[i].offset;
6533       loc2 = vt_expand_loc (var->var_part[i].loc_chain->loc, vars);
6534       if (!loc2)
6535         {
6536           complete = false;
6537           continue;
6538         }
6539       loc[n_var_parts] = loc2;
6540       mode = GET_MODE (var->var_part[i].loc_chain->loc);
6541       initialized = var->var_part[i].loc_chain->init;
6542       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
6543
6544       /* Attempt to merge adjacent registers or memory.  */
6545       wider_mode = GET_MODE_WIDER_MODE (mode);
6546       for (j = i + 1; j < var->n_var_parts; j++)
6547         if (last_limit <= var->var_part[j].offset)
6548           break;
6549       if (j < var->n_var_parts
6550           && wider_mode != VOIDmode
6551           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
6552           && (REG_P (loc[n_var_parts]) || MEM_P (loc[n_var_parts]))
6553           && (loc2 = vt_expand_loc (var->var_part[j].loc_chain->loc, vars))
6554           && GET_CODE (loc[n_var_parts]) == GET_CODE (loc2)
6555           && last_limit == var->var_part[j].offset)
6556         {
6557           rtx new_loc = NULL;
6558
6559           if (REG_P (loc[n_var_parts])
6560               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
6561                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
6562               && end_hard_regno (mode, REGNO (loc[n_var_parts]))
6563                  == REGNO (loc2))
6564             {
6565               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
6566                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
6567                                            mode, 0);
6568               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
6569                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
6570               if (new_loc)
6571                 {
6572                   if (!REG_P (new_loc)
6573                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
6574                     new_loc = NULL;
6575                   else
6576                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
6577                 }
6578             }
6579           else if (MEM_P (loc[n_var_parts])
6580                    && GET_CODE (XEXP (loc2, 0)) == PLUS
6581                    && REG_P (XEXP (XEXP (loc2, 0), 0))
6582                    && CONST_INT_P (XEXP (XEXP (loc2, 0), 1)))
6583             {
6584               if ((REG_P (XEXP (loc[n_var_parts], 0))
6585                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
6586                                    XEXP (XEXP (loc2, 0), 0))
6587                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
6588                       == GET_MODE_SIZE (mode))
6589                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
6590                       && CONST_INT_P (XEXP (XEXP (loc[n_var_parts], 0), 1))
6591                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
6592                                       XEXP (XEXP (loc2, 0), 0))
6593                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
6594                          + GET_MODE_SIZE (mode)
6595                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
6596                 new_loc = adjust_address_nv (loc[n_var_parts],
6597                                              wider_mode, 0);
6598             }
6599
6600           if (new_loc)
6601             {
6602               loc[n_var_parts] = new_loc;
6603               mode = wider_mode;
6604               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
6605               i = j;
6606             }
6607         }
6608       ++n_var_parts;
6609     }
6610   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (decl));
6611   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
6612     complete = false;
6613
6614   if (where != EMIT_NOTE_BEFORE_INSN)
6615     {
6616       note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
6617       if (where == EMIT_NOTE_AFTER_CALL_INSN)
6618         NOTE_DURING_CALL_P (note) = true;
6619     }
6620   else
6621     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
6622
6623   if (! flag_var_tracking_uninit)
6624     initialized = VAR_INIT_STATUS_INITIALIZED;
6625
6626   if (!complete)
6627     {
6628       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, decl,
6629                                                        NULL_RTX, (int) initialized);
6630     }
6631   else if (n_var_parts == 1)
6632     {
6633       rtx expr_list
6634         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
6635
6636       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, decl,
6637                                                        expr_list,
6638                                                        (int) initialized);
6639     }
6640   else if (n_var_parts)
6641     {
6642       rtx parallel;
6643
6644       for (i = 0; i < n_var_parts; i++)
6645         loc[i]
6646           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
6647
6648       parallel = gen_rtx_PARALLEL (VOIDmode,
6649                                    gen_rtvec_v (n_var_parts, loc));
6650       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, decl,
6651                                                        parallel,
6652                                                        (int) initialized);
6653     }
6654
6655  clear:
6656   set_dv_changed (var->dv, false);
6657   htab_clear_slot (changed_variables, varp);
6658
6659   /* Continue traversing the hash table.  */
6660   return 1;
6661 }
6662
6663 DEF_VEC_P (variable);
6664 DEF_VEC_ALLOC_P (variable, heap);
6665
6666 /* Stack of variable_def pointers that need processing with
6667    check_changed_vars_2.  */
6668
6669 static VEC (variable, heap) *changed_variables_stack;
6670
6671 /* Populate changed_variables_stack with variable_def pointers
6672    that need variable_was_changed called on them.  */
6673
6674 static int
6675 check_changed_vars_1 (void **slot, void *data)
6676 {
6677   variable var = (variable) *slot;
6678   htab_t htab = (htab_t) data;
6679
6680   if (dv_is_value_p (var->dv))
6681     {
6682       value_chain vc
6683         = (value_chain) htab_find_with_hash (value_chains, var->dv,
6684                                              dv_htab_hash (var->dv));
6685
6686       if (vc == NULL)
6687         return 1;
6688       for (vc = vc->next; vc; vc = vc->next)
6689         if (!dv_changed_p (vc->dv))
6690           {
6691             variable vcvar
6692               = (variable) htab_find_with_hash (htab, vc->dv,
6693                                                 dv_htab_hash (vc->dv));
6694             if (vcvar)
6695               VEC_safe_push (variable, heap, changed_variables_stack,
6696                              vcvar);
6697           }
6698     }
6699   return 1;
6700 }
6701
6702 /* Add VAR to changed_variables and also for VALUEs add recursively
6703    all DVs that aren't in changed_variables yet but reference the
6704    VALUE from its loc_chain.  */
6705
6706 static void
6707 check_changed_vars_2 (variable var, htab_t htab)
6708 {
6709   variable_was_changed (var, NULL);
6710   if (dv_is_value_p (var->dv))
6711     {
6712       value_chain vc
6713         = (value_chain) htab_find_with_hash (value_chains, var->dv,
6714                                              dv_htab_hash (var->dv));
6715
6716       if (vc == NULL)
6717         return;
6718       for (vc = vc->next; vc; vc = vc->next)
6719         if (!dv_changed_p (vc->dv))
6720           {
6721             variable vcvar
6722               = (variable) htab_find_with_hash (htab, vc->dv,
6723                                                 dv_htab_hash (vc->dv));
6724             if (vcvar)
6725               check_changed_vars_2 (vcvar, htab);
6726           }
6727     }
6728 }
6729
6730 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
6731    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
6732    shall be emitted before of after instruction INSN.  */
6733
6734 static void
6735 emit_notes_for_changes (rtx insn, enum emit_note_where where,
6736                         shared_hash vars)
6737 {
6738   emit_note_data data;
6739   htab_t htab = shared_hash_htab (vars);
6740
6741   if (!htab_elements (changed_variables))
6742     return;
6743
6744   if (MAY_HAVE_DEBUG_INSNS)
6745     {
6746       /* Unfortunately this has to be done in two steps, because
6747          we can't traverse a hashtab into which we are inserting
6748          through variable_was_changed.  */
6749       htab_traverse (changed_variables, check_changed_vars_1, htab);
6750       while (VEC_length (variable, changed_variables_stack) > 0)
6751         check_changed_vars_2 (VEC_pop (variable, changed_variables_stack),
6752                               htab);
6753     }
6754
6755   data.insn = insn;
6756   data.where = where;
6757   data.vars = htab;
6758
6759   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
6760 }
6761
6762 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
6763    same variable in hash table DATA or is not there at all.  */
6764
6765 static int
6766 emit_notes_for_differences_1 (void **slot, void *data)
6767 {
6768   htab_t new_vars = (htab_t) data;
6769   variable old_var, new_var;
6770
6771   old_var = (variable) *slot;
6772   new_var = (variable) htab_find_with_hash (new_vars, old_var->dv,
6773                                             dv_htab_hash (old_var->dv));
6774
6775   if (!new_var)
6776     {
6777       /* Variable has disappeared.  */
6778       variable empty_var;
6779
6780       empty_var = (variable) pool_alloc (dv_pool (old_var->dv));
6781       empty_var->dv = old_var->dv;
6782       empty_var->refcount = 0;
6783       empty_var->n_var_parts = 0;
6784       if (dv_onepart_p (old_var->dv))
6785         {
6786           location_chain lc;
6787
6788           gcc_assert (old_var->n_var_parts == 1);
6789           for (lc = old_var->var_part[0].loc_chain; lc; lc = lc->next)
6790             remove_value_chains (old_var->dv, lc->loc);
6791           if (dv_is_value_p (old_var->dv))
6792             remove_cselib_value_chains (old_var->dv);
6793         }
6794       variable_was_changed (empty_var, NULL);
6795     }
6796   else if (variable_different_p (old_var, new_var, true))
6797     {
6798       if (dv_onepart_p (old_var->dv))
6799         {
6800           location_chain lc1, lc2;
6801
6802           gcc_assert (old_var->n_var_parts == 1);
6803           gcc_assert (new_var->n_var_parts == 1);
6804           lc1 = old_var->var_part[0].loc_chain;
6805           lc2 = new_var->var_part[0].loc_chain;
6806           while (lc1
6807                  && lc2
6808                  && ((REG_P (lc1->loc) && REG_P (lc2->loc))
6809                      || rtx_equal_p (lc1->loc, lc2->loc)))
6810             {
6811               lc1 = lc1->next;
6812               lc2 = lc2->next;
6813             }
6814           for (; lc2; lc2 = lc2->next)
6815             add_value_chains (old_var->dv, lc2->loc);
6816           for (; lc1; lc1 = lc1->next)
6817             remove_value_chains (old_var->dv, lc1->loc);
6818         }
6819       variable_was_changed (new_var, NULL);
6820     }
6821
6822   /* Continue traversing the hash table.  */
6823   return 1;
6824 }
6825
6826 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
6827    table DATA.  */
6828
6829 static int
6830 emit_notes_for_differences_2 (void **slot, void *data)
6831 {
6832   htab_t old_vars = (htab_t) data;
6833   variable old_var, new_var;
6834
6835   new_var = (variable) *slot;
6836   old_var = (variable) htab_find_with_hash (old_vars, new_var->dv,
6837                                             dv_htab_hash (new_var->dv));
6838   if (!old_var)
6839     {
6840       /* Variable has appeared.  */
6841       if (dv_onepart_p (new_var->dv))
6842         {
6843           location_chain lc;
6844
6845           gcc_assert (new_var->n_var_parts == 1);
6846           for (lc = new_var->var_part[0].loc_chain; lc; lc = lc->next)
6847             add_value_chains (new_var->dv, lc->loc);
6848           if (dv_is_value_p (new_var->dv))
6849             add_cselib_value_chains (new_var->dv);
6850         }
6851       variable_was_changed (new_var, NULL);
6852     }
6853
6854   /* Continue traversing the hash table.  */
6855   return 1;
6856 }
6857
6858 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
6859    NEW_SET.  */
6860
6861 static void
6862 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
6863                             dataflow_set *new_set)
6864 {
6865   htab_traverse (shared_hash_htab (old_set->vars),
6866                  emit_notes_for_differences_1,
6867                  shared_hash_htab (new_set->vars));
6868   htab_traverse (shared_hash_htab (new_set->vars),
6869                  emit_notes_for_differences_2,
6870                  shared_hash_htab (old_set->vars));
6871   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, new_set->vars);
6872 }
6873
6874 /* Emit the notes for changes of location parts in the basic block BB.  */
6875
6876 static void
6877 emit_notes_in_bb (basic_block bb, dataflow_set *set)
6878 {
6879   int i;
6880
6881   dataflow_set_clear (set);
6882   dataflow_set_copy (set, &VTI (bb)->in);
6883
6884   for (i = 0; i < VTI (bb)->n_mos; i++)
6885     {
6886       rtx insn = VTI (bb)->mos[i].insn;
6887
6888       switch (VTI (bb)->mos[i].type)
6889         {
6890           case MO_CALL:
6891             dataflow_set_clear_at_call (set);
6892             emit_notes_for_changes (insn, EMIT_NOTE_AFTER_CALL_INSN, set->vars);
6893             break;
6894
6895           case MO_USE:
6896             {
6897               rtx loc = VTI (bb)->mos[i].u.loc;
6898
6899               if (REG_P (loc))
6900                 var_reg_set (set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
6901               else
6902                 var_mem_set (set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
6903
6904               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
6905             }
6906             break;
6907
6908           case MO_VAL_LOC:
6909             {
6910               rtx loc = VTI (bb)->mos[i].u.loc;
6911               rtx val, vloc;
6912               tree var;
6913
6914               if (GET_CODE (loc) == CONCAT)
6915                 {
6916                   val = XEXP (loc, 0);
6917                   vloc = XEXP (loc, 1);
6918                 }
6919               else
6920                 {
6921                   val = NULL_RTX;
6922                   vloc = loc;
6923                 }
6924
6925               var = PAT_VAR_LOCATION_DECL (vloc);
6926
6927               clobber_variable_part (set, NULL_RTX,
6928                                      dv_from_decl (var), 0, NULL_RTX);
6929               if (val)
6930                 {
6931                   if (VAL_NEEDS_RESOLUTION (loc))
6932                     val_resolve (set, val, PAT_VAR_LOCATION_LOC (vloc), insn);
6933                   set_variable_part (set, val, dv_from_decl (var), 0,
6934                                      VAR_INIT_STATUS_INITIALIZED, NULL_RTX,
6935                                      INSERT);
6936                 }
6937
6938               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
6939             }
6940             break;
6941
6942           case MO_VAL_USE:
6943             {
6944               rtx loc = VTI (bb)->mos[i].u.loc;
6945               rtx val, vloc, uloc;
6946
6947               vloc = uloc = XEXP (loc, 1);
6948               val = XEXP (loc, 0);
6949
6950               if (GET_CODE (val) == CONCAT)
6951                 {
6952                   uloc = XEXP (val, 1);
6953                   val = XEXP (val, 0);
6954                 }
6955
6956               if (VAL_NEEDS_RESOLUTION (loc))
6957                 val_resolve (set, val, vloc, insn);
6958               else
6959                 val_store (set, val, uloc, insn, false);
6960
6961               if (VAL_HOLDS_TRACK_EXPR (loc))
6962                 {
6963                   if (GET_CODE (uloc) == REG)
6964                     var_reg_set (set, uloc, VAR_INIT_STATUS_UNINITIALIZED,
6965                                  NULL);
6966                   else if (GET_CODE (uloc) == MEM)
6967                     var_mem_set (set, uloc, VAR_INIT_STATUS_UNINITIALIZED,
6968                                  NULL);
6969                 }
6970
6971               emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, set->vars);
6972             }
6973             break;
6974
6975           case MO_VAL_SET:
6976             {
6977               rtx loc = VTI (bb)->mos[i].u.loc;
6978               rtx val, vloc, uloc;
6979
6980               vloc = uloc = XEXP (loc, 1);
6981               val = XEXP (loc, 0);
6982
6983               if (GET_CODE (val) == CONCAT)
6984                 {
6985                   vloc = XEXP (val, 1);
6986                   val = XEXP (val, 0);
6987                 }
6988
6989               if (GET_CODE (vloc) == SET)
6990                 {
6991                   rtx vsrc = SET_SRC (vloc);
6992
6993                   gcc_assert (val != vsrc);
6994                   gcc_assert (vloc == uloc || VAL_NEEDS_RESOLUTION (loc));
6995
6996                   vloc = SET_DEST (vloc);
6997
6998                   if (VAL_NEEDS_RESOLUTION (loc))
6999                     val_resolve (set, val, vsrc, insn);
7000                 }
7001               else if (VAL_NEEDS_RESOLUTION (loc))
7002                 {
7003                   gcc_assert (GET_CODE (uloc) == SET
7004                               && GET_CODE (SET_SRC (uloc)) == REG);
7005                   val_resolve (set, val, SET_SRC (uloc), insn);
7006                 }
7007
7008               if (VAL_HOLDS_TRACK_EXPR (loc))
7009                 {
7010                   if (VAL_EXPR_IS_CLOBBERED (loc))
7011                     {
7012                       if (REG_P (uloc))
7013                         var_reg_delete (set, uloc, true);
7014                       else if (MEM_P (uloc))
7015                         var_mem_delete (set, uloc, true);
7016                     }
7017                   else
7018                     {
7019                       bool copied_p = VAL_EXPR_IS_COPIED (loc);
7020                       rtx set_src = NULL;
7021                       enum var_init_status status = VAR_INIT_STATUS_INITIALIZED;
7022
7023                       if (GET_CODE (uloc) == SET)
7024                         {
7025                           set_src = SET_SRC (uloc);
7026                           uloc = SET_DEST (uloc);
7027                         }
7028
7029                       if (copied_p)
7030                         {
7031                           status = find_src_status (set, set_src);
7032
7033                           set_src = find_src_set_src (set, set_src);
7034                         }
7035
7036                       if (REG_P (uloc))
7037                         var_reg_delete_and_set (set, uloc, !copied_p,
7038                                                 status, set_src);
7039                       else if (MEM_P (uloc))
7040                         var_mem_delete_and_set (set, uloc, !copied_p,
7041                                                 status, set_src);
7042                     }
7043                 }
7044               else if (REG_P (uloc))
7045                 var_regno_delete (set, REGNO (uloc));
7046
7047               val_store (set, val, vloc, insn, true);
7048
7049               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7050                                       set->vars);
7051             }
7052             break;
7053
7054           case MO_SET:
7055             {
7056               rtx loc = VTI (bb)->mos[i].u.loc;
7057               rtx set_src = NULL;
7058
7059               if (GET_CODE (loc) == SET)
7060                 {
7061                   set_src = SET_SRC (loc);
7062                   loc = SET_DEST (loc);
7063                 }
7064
7065               if (REG_P (loc))
7066                 var_reg_delete_and_set (set, loc, true, VAR_INIT_STATUS_INITIALIZED,
7067                                         set_src);
7068               else
7069                 var_mem_delete_and_set (set, loc, true, VAR_INIT_STATUS_INITIALIZED,
7070                                         set_src);
7071
7072               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7073                                       set->vars);
7074             }
7075             break;
7076
7077           case MO_COPY:
7078             {
7079               rtx loc = VTI (bb)->mos[i].u.loc;
7080               enum var_init_status src_status;
7081               rtx set_src = NULL;
7082
7083               if (GET_CODE (loc) == SET)
7084                 {
7085                   set_src = SET_SRC (loc);
7086                   loc = SET_DEST (loc);
7087                 }
7088
7089               src_status = find_src_status (set, set_src);
7090               set_src = find_src_set_src (set, set_src);
7091
7092               if (REG_P (loc))
7093                 var_reg_delete_and_set (set, loc, false, src_status, set_src);
7094               else
7095                 var_mem_delete_and_set (set, loc, false, src_status, set_src);
7096
7097               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7098                                       set->vars);
7099             }
7100             break;
7101
7102           case MO_USE_NO_VAR:
7103             {
7104               rtx loc = VTI (bb)->mos[i].u.loc;
7105
7106               if (REG_P (loc))
7107                 var_reg_delete (set, loc, false);
7108               else
7109                 var_mem_delete (set, loc, false);
7110
7111               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
7112             }
7113             break;
7114
7115           case MO_CLOBBER:
7116             {
7117               rtx loc = VTI (bb)->mos[i].u.loc;
7118
7119               if (REG_P (loc))
7120                 var_reg_delete (set, loc, true);
7121               else
7122                 var_mem_delete (set, loc, true);
7123
7124               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
7125                                       set->vars);
7126             }
7127             break;
7128
7129           case MO_ADJUST:
7130             set->stack_adjust += VTI (bb)->mos[i].u.adjust;
7131             break;
7132         }
7133     }
7134 }
7135
7136 /* Emit notes for the whole function.  */
7137
7138 static void
7139 vt_emit_notes (void)
7140 {
7141   basic_block bb;
7142   dataflow_set cur;
7143
7144   gcc_assert (!htab_elements (changed_variables));
7145
7146   /* Free memory occupied by the out hash tables, as they aren't used
7147      anymore.  */
7148   FOR_EACH_BB (bb)
7149     dataflow_set_clear (&VTI (bb)->out);
7150
7151   /* Enable emitting notes by functions (mainly by set_variable_part and
7152      delete_variable_part).  */
7153   emit_notes = true;
7154
7155   if (MAY_HAVE_DEBUG_INSNS)
7156     changed_variables_stack = VEC_alloc (variable, heap, 40);
7157
7158   dataflow_set_init (&cur);
7159
7160   FOR_EACH_BB (bb)
7161     {
7162       /* Emit the notes for changes of variable locations between two
7163          subsequent basic blocks.  */
7164       emit_notes_for_differences (BB_HEAD (bb), &cur, &VTI (bb)->in);
7165
7166       /* Emit the notes for the changes in the basic block itself.  */
7167       emit_notes_in_bb (bb, &cur);
7168
7169       /* Free memory occupied by the in hash table, we won't need it
7170          again.  */
7171       dataflow_set_clear (&VTI (bb)->in);
7172     }
7173 #ifdef ENABLE_CHECKING
7174   htab_traverse (shared_hash_htab (cur.vars),
7175                  emit_notes_for_differences_1,
7176                  shared_hash_htab (empty_shared_hash));
7177   if (MAY_HAVE_DEBUG_INSNS)
7178     gcc_assert (htab_elements (value_chains) == 0);
7179 #endif
7180   dataflow_set_destroy (&cur);
7181
7182   if (MAY_HAVE_DEBUG_INSNS)
7183     VEC_free (variable, heap, changed_variables_stack);
7184
7185   emit_notes = false;
7186 }
7187
7188 /* If there is a declaration and offset associated with register/memory RTL
7189    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
7190
7191 static bool
7192 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
7193 {
7194   if (REG_P (rtl))
7195     {
7196       if (REG_ATTRS (rtl))
7197         {
7198           *declp = REG_EXPR (rtl);
7199           *offsetp = REG_OFFSET (rtl);
7200           return true;
7201         }
7202     }
7203   else if (MEM_P (rtl))
7204     {
7205       if (MEM_ATTRS (rtl))
7206         {
7207           *declp = MEM_EXPR (rtl);
7208           *offsetp = INT_MEM_OFFSET (rtl);
7209           return true;
7210         }
7211     }
7212   return false;
7213 }
7214
7215 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
7216
7217 static void
7218 vt_add_function_parameters (void)
7219 {
7220   tree parm;
7221
7222   for (parm = DECL_ARGUMENTS (current_function_decl);
7223        parm; parm = TREE_CHAIN (parm))
7224     {
7225       rtx decl_rtl = DECL_RTL_IF_SET (parm);
7226       rtx incoming = DECL_INCOMING_RTL (parm);
7227       tree decl;
7228       enum machine_mode mode;
7229       HOST_WIDE_INT offset;
7230       dataflow_set *out;
7231       decl_or_value dv;
7232
7233       if (TREE_CODE (parm) != PARM_DECL)
7234         continue;
7235
7236       if (!DECL_NAME (parm))
7237         continue;
7238
7239       if (!decl_rtl || !incoming)
7240         continue;
7241
7242       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
7243         continue;
7244
7245       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
7246         {
7247           if (REG_P (incoming) || MEM_P (incoming))
7248             {
7249               /* This means argument is passed by invisible reference.  */
7250               offset = 0;
7251               decl = parm;
7252               incoming = gen_rtx_MEM (GET_MODE (decl_rtl), incoming);
7253             }
7254           else
7255             {
7256               if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
7257                 continue;
7258               offset += byte_lowpart_offset (GET_MODE (incoming),
7259                                              GET_MODE (decl_rtl));
7260             }
7261         }
7262
7263       if (!decl)
7264         continue;
7265
7266       if (parm != decl)
7267         {
7268           /* Assume that DECL_RTL was a pseudo that got spilled to
7269              memory.  The spill slot sharing code will force the
7270              memory to reference spill_slot_decl (%sfp), so we don't
7271              match above.  That's ok, the pseudo must have referenced
7272              the entire parameter, so just reset OFFSET.  */
7273           gcc_assert (decl == get_spill_slot_decl (false));
7274           offset = 0;
7275         }
7276
7277       if (!track_loc_p (incoming, parm, offset, false, &mode, &offset))
7278         continue;
7279
7280       out = &VTI (ENTRY_BLOCK_PTR)->out;
7281
7282       dv = dv_from_decl (parm);
7283
7284       if (target_for_debug_bind (parm)
7285           /* We can't deal with these right now, because this kind of
7286              variable is single-part.  ??? We could handle parallels
7287              that describe multiple locations for the same single
7288              value, but ATM we don't.  */
7289           && GET_CODE (incoming) != PARALLEL)
7290         {
7291           cselib_val *val;
7292
7293           /* ??? We shouldn't ever hit this, but it may happen because
7294              arguments passed by invisible reference aren't dealt with
7295              above: incoming-rtl will have Pmode rather than the
7296              expected mode for the type.  */
7297           if (offset)
7298             continue;
7299
7300           val = cselib_lookup (var_lowpart (mode, incoming), mode, true);
7301
7302           /* ??? Float-typed values in memory are not handled by
7303              cselib.  */
7304           if (val)
7305             {
7306               cselib_preserve_value (val);
7307               set_variable_part (out, val->val_rtx, dv, offset,
7308                                  VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7309               dv = dv_from_value (val->val_rtx);
7310             }
7311         }
7312
7313       if (REG_P (incoming))
7314         {
7315           incoming = var_lowpart (mode, incoming);
7316           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
7317           attrs_list_insert (&out->regs[REGNO (incoming)], dv, offset,
7318                              incoming);
7319           set_variable_part (out, incoming, dv, offset,
7320                              VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7321         }
7322       else if (MEM_P (incoming))
7323         {
7324           incoming = var_lowpart (mode, incoming);
7325           set_variable_part (out, incoming, dv, offset,
7326                              VAR_INIT_STATUS_INITIALIZED, NULL, INSERT);
7327         }
7328     }
7329
7330   if (MAY_HAVE_DEBUG_INSNS)
7331     {
7332       cselib_preserve_only_values (true);
7333       cselib_reset_table (cselib_get_next_uid ());
7334     }
7335
7336 }
7337
7338 /* Allocate and initialize the data structures for variable tracking
7339    and parse the RTL to get the micro operations.  */
7340
7341 static void
7342 vt_initialize (void)
7343 {
7344   basic_block bb;
7345
7346   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
7347
7348   if (MAY_HAVE_DEBUG_INSNS)
7349     {
7350       cselib_init (true);
7351       scratch_regs = BITMAP_ALLOC (NULL);
7352       valvar_pool = create_alloc_pool ("small variable_def pool",
7353                                        sizeof (struct variable_def), 256);
7354     }
7355   else
7356     {
7357       scratch_regs = NULL;
7358       valvar_pool = NULL;
7359     }
7360
7361   FOR_EACH_BB (bb)
7362     {
7363       rtx insn;
7364       HOST_WIDE_INT pre, post = 0;
7365       int count;
7366       unsigned int next_uid_before = cselib_get_next_uid ();
7367       unsigned int next_uid_after = next_uid_before;
7368
7369       if (MAY_HAVE_DEBUG_INSNS)
7370         {
7371           cselib_record_sets_hook = count_with_sets;
7372           if (dump_file && (dump_flags & TDF_DETAILS))
7373             fprintf (dump_file, "first value: %i\n",
7374                      cselib_get_next_uid ());
7375         }
7376
7377       /* Count the number of micro operations.  */
7378       VTI (bb)->n_mos = 0;
7379       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
7380            insn = NEXT_INSN (insn))
7381         {
7382           if (INSN_P (insn))
7383             {
7384               if (!frame_pointer_needed)
7385                 {
7386                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
7387                   if (pre)
7388                     {
7389                       VTI (bb)->n_mos++;
7390                       if (dump_file && (dump_flags & TDF_DETAILS))
7391                         log_op_type (GEN_INT (pre), bb, insn,
7392                                      MO_ADJUST, dump_file);
7393                     }
7394                   if (post)
7395                     {
7396                       VTI (bb)->n_mos++;
7397                       if (dump_file && (dump_flags & TDF_DETAILS))
7398                         log_op_type (GEN_INT (post), bb, insn,
7399                                      MO_ADJUST, dump_file);
7400                     }
7401                 }
7402               cselib_hook_called = false;
7403               if (MAY_HAVE_DEBUG_INSNS)
7404                 {
7405                   cselib_process_insn (insn);
7406                   if (dump_file && (dump_flags & TDF_DETAILS))
7407                     {
7408                       print_rtl_single (dump_file, insn);
7409                       dump_cselib_table (dump_file);
7410                     }
7411                 }
7412               if (!cselib_hook_called)
7413                 count_with_sets (insn, 0, 0);
7414               if (CALL_P (insn))
7415                 {
7416                   VTI (bb)->n_mos++;
7417                   if (dump_file && (dump_flags & TDF_DETAILS))
7418                     log_op_type (PATTERN (insn), bb, insn,
7419                                  MO_CALL, dump_file);
7420                 }
7421             }
7422         }
7423
7424       count = VTI (bb)->n_mos;
7425
7426       if (MAY_HAVE_DEBUG_INSNS)
7427         {
7428           cselib_preserve_only_values (false);
7429           next_uid_after = cselib_get_next_uid ();
7430           cselib_reset_table (next_uid_before);
7431           cselib_record_sets_hook = add_with_sets;
7432           if (dump_file && (dump_flags & TDF_DETAILS))
7433             fprintf (dump_file, "first value: %i\n",
7434                      cselib_get_next_uid ());
7435         }
7436
7437       /* Add the micro-operations to the array.  */
7438       VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
7439       VTI (bb)->n_mos = 0;
7440       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
7441            insn = NEXT_INSN (insn))
7442         {
7443           if (INSN_P (insn))
7444             {
7445               if (!frame_pointer_needed)
7446                 {
7447                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
7448                   if (pre)
7449                     {
7450                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
7451
7452                       mo->type = MO_ADJUST;
7453                       mo->u.adjust = pre;
7454                       mo->insn = insn;
7455
7456                       if (dump_file && (dump_flags & TDF_DETAILS))
7457                         log_op_type (PATTERN (insn), bb, insn,
7458                                      MO_ADJUST, dump_file);
7459                     }
7460                 }
7461
7462               cselib_hook_called = false;
7463               if (MAY_HAVE_DEBUG_INSNS)
7464                 {
7465                   cselib_process_insn (insn);
7466                   if (dump_file && (dump_flags & TDF_DETAILS))
7467                     {
7468                       print_rtl_single (dump_file, insn);
7469                       dump_cselib_table (dump_file);
7470                     }
7471                 }
7472               if (!cselib_hook_called)
7473                 add_with_sets (insn, 0, 0);
7474
7475               if (!frame_pointer_needed && post)
7476                 {
7477                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
7478
7479                   mo->type = MO_ADJUST;
7480                   mo->u.adjust = post;
7481                   mo->insn = insn;
7482
7483                   if (dump_file && (dump_flags & TDF_DETAILS))
7484                     log_op_type (PATTERN (insn), bb, insn,
7485                                  MO_ADJUST, dump_file);
7486                 }
7487             }
7488         }
7489       gcc_assert (count == VTI (bb)->n_mos);
7490       if (MAY_HAVE_DEBUG_INSNS)
7491         {
7492           cselib_preserve_only_values (true);
7493           gcc_assert (next_uid_after == cselib_get_next_uid ());
7494           cselib_reset_table (next_uid_after);
7495           cselib_record_sets_hook = NULL;
7496         }
7497     }
7498
7499   attrs_pool = create_alloc_pool ("attrs_def pool",
7500                                   sizeof (struct attrs_def), 1024);
7501   var_pool = create_alloc_pool ("variable_def pool",
7502                                 sizeof (struct variable_def)
7503                                 + (MAX_VAR_PARTS - 1)
7504                                 * sizeof (((variable)NULL)->var_part[0]), 64);
7505   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
7506                                       sizeof (struct location_chain_def),
7507                                       1024);
7508   shared_hash_pool = create_alloc_pool ("shared_hash_def pool",
7509                                         sizeof (struct shared_hash_def), 256);
7510   empty_shared_hash = (shared_hash) pool_alloc (shared_hash_pool);
7511   empty_shared_hash->refcount = 1;
7512   empty_shared_hash->htab
7513     = htab_create (1, variable_htab_hash, variable_htab_eq,
7514                    variable_htab_free);
7515   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
7516                                    variable_htab_free);
7517   if (MAY_HAVE_DEBUG_INSNS)
7518     {
7519       value_chain_pool = create_alloc_pool ("value_chain_def pool",
7520                                             sizeof (struct value_chain_def),
7521                                             1024);
7522       value_chains = htab_create (32, value_chain_htab_hash,
7523                                   value_chain_htab_eq, NULL);
7524     }
7525
7526   /* Init the IN and OUT sets.  */
7527   FOR_ALL_BB (bb)
7528     {
7529       VTI (bb)->visited = false;
7530       VTI (bb)->flooded = false;
7531       dataflow_set_init (&VTI (bb)->in);
7532       dataflow_set_init (&VTI (bb)->out);
7533       VTI (bb)->permp = NULL;
7534     }
7535
7536   VTI (ENTRY_BLOCK_PTR)->flooded = true;
7537   vt_add_function_parameters ();
7538 }
7539
7540 /* Get rid of all debug insns from the insn stream.  */
7541
7542 static void
7543 delete_debug_insns (void)
7544 {
7545   basic_block bb;
7546   rtx insn, next;
7547
7548   if (!MAY_HAVE_DEBUG_INSNS)
7549     return;
7550
7551   FOR_EACH_BB (bb)
7552     {
7553       FOR_BB_INSNS_SAFE (bb, insn, next)
7554         if (DEBUG_INSN_P (insn))
7555           delete_insn (insn);
7556     }
7557 }
7558
7559 /* Run a fast, BB-local only version of var tracking, to take care of
7560    information that we don't do global analysis on, such that not all
7561    information is lost.  If SKIPPED holds, we're skipping the global
7562    pass entirely, so we should try to use information it would have
7563    handled as well..  */
7564
7565 static void
7566 vt_debug_insns_local (bool skipped ATTRIBUTE_UNUSED)
7567 {
7568   /* ??? Just skip it all for now.  */
7569   delete_debug_insns ();
7570 }
7571
7572 /* Free the data structures needed for variable tracking.  */
7573
7574 static void
7575 vt_finalize (void)
7576 {
7577   basic_block bb;
7578
7579   FOR_EACH_BB (bb)
7580     {
7581       free (VTI (bb)->mos);
7582     }
7583
7584   FOR_ALL_BB (bb)
7585     {
7586       dataflow_set_destroy (&VTI (bb)->in);
7587       dataflow_set_destroy (&VTI (bb)->out);
7588       if (VTI (bb)->permp)
7589         {
7590           dataflow_set_destroy (VTI (bb)->permp);
7591           XDELETE (VTI (bb)->permp);
7592         }
7593     }
7594   free_aux_for_blocks ();
7595   htab_delete (empty_shared_hash->htab);
7596   htab_delete (changed_variables);
7597   free_alloc_pool (attrs_pool);
7598   free_alloc_pool (var_pool);
7599   free_alloc_pool (loc_chain_pool);
7600   free_alloc_pool (shared_hash_pool);
7601
7602   if (MAY_HAVE_DEBUG_INSNS)
7603     {
7604       htab_delete (value_chains);
7605       free_alloc_pool (value_chain_pool);
7606       free_alloc_pool (valvar_pool);
7607       cselib_finish ();
7608       BITMAP_FREE (scratch_regs);
7609       scratch_regs = NULL;
7610     }
7611
7612   if (vui_vec)
7613     XDELETEVEC (vui_vec);
7614   vui_vec = NULL;
7615   vui_allocated = 0;
7616 }
7617
7618 /* The entry point to variable tracking pass.  */
7619
7620 static inline unsigned int
7621 variable_tracking_main_1 (void)
7622 {
7623   bool success;
7624
7625   if (flag_var_tracking_assignments < 0)
7626     {
7627       delete_debug_insns ();
7628       return 0;
7629     }
7630
7631   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
7632     {
7633       vt_debug_insns_local (true);
7634       return 0;
7635     }
7636
7637   mark_dfs_back_edges ();
7638   vt_initialize ();
7639   if (!frame_pointer_needed)
7640     {
7641       if (!vt_stack_adjustments ())
7642         {
7643           vt_finalize ();
7644           vt_debug_insns_local (true);
7645           return 0;
7646         }
7647     }
7648
7649   success = vt_find_locations ();
7650
7651   if (!success && flag_var_tracking_assignments > 0)
7652     {
7653       vt_finalize ();
7654
7655       delete_debug_insns ();
7656
7657       /* This is later restored by our caller.  */
7658       flag_var_tracking_assignments = 0;
7659
7660       vt_initialize ();
7661
7662       if (!frame_pointer_needed && !vt_stack_adjustments ())
7663         gcc_unreachable ();
7664
7665       success = vt_find_locations ();
7666     }
7667
7668   if (!success)
7669     {
7670       vt_finalize ();
7671       vt_debug_insns_local (false);
7672       return 0;
7673     }
7674
7675   if (dump_file && (dump_flags & TDF_DETAILS))
7676     {
7677       dump_dataflow_sets ();
7678       dump_flow_info (dump_file, dump_flags);
7679     }
7680
7681   vt_emit_notes ();
7682
7683   vt_finalize ();
7684   vt_debug_insns_local (false);
7685   return 0;
7686 }
7687
7688 unsigned int
7689 variable_tracking_main (void)
7690 {
7691   unsigned int ret;
7692   int save = flag_var_tracking_assignments;
7693
7694   ret = variable_tracking_main_1 ();
7695
7696   flag_var_tracking_assignments = save;
7697
7698   return ret;
7699 }
7700 \f
7701 static bool
7702 gate_handle_var_tracking (void)
7703 {
7704   return (flag_var_tracking);
7705 }
7706
7707
7708
7709 struct rtl_opt_pass pass_variable_tracking =
7710 {
7711  {
7712   RTL_PASS,
7713   "vartrack",                           /* name */
7714   gate_handle_var_tracking,             /* gate */
7715   variable_tracking_main,               /* execute */
7716   NULL,                                 /* sub */
7717   NULL,                                 /* next */
7718   0,                                    /* static_pass_number */
7719   TV_VAR_TRACKING,                      /* tv_id */
7720   0,                                    /* properties_required */
7721   0,                                    /* properties_provided */
7722   0,                                    /* properties_destroyed */
7723   0,                                    /* todo_flags_start */
7724   TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */
7725  }
7726 };