gcc/var-tracking.c

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