gcc/var-tracking.c

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