gcc/var-tracking.c

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