gcc/var-tracking.c

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