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
 110 /* Type of micro operation.  */
 111 enum micro_operation_type
 112 {
 113   MO_USE,       /* Use location (REG or MEM).  */
 114   MO_USE_NO_VAR,/* Use location which is not associated with a variable
 115                    or the variable is not trackable.  */
 116   MO_SET,       /* Set location.  */
 117   MO_COPY,      /* Copy the same portion of a variable from one
 118                    location to another.  */
 119   MO_CLOBBER,   /* Clobber location.  */
 120   MO_CALL,      /* Call insn.  */
 121   MO_ADJUST     /* Adjust stack pointer.  */
 122 };
 123
 124 /* Where shall the note be emitted?  BEFORE or AFTER the instruction.  */
 125 enum emit_note_where
 126 {
 127   EMIT_NOTE_BEFORE_INSN,
 128   EMIT_NOTE_AFTER_INSN
 129 };
 130
 131 /* Structure holding information about micro operation.  */
 132 typedef struct micro_operation_def
 133 {
 134   /* Type of micro operation.  */
 135   enum micro_operation_type type;
 136
 137   union {
 138     /* Location.  For MO_SET and MO_COPY, this is the SET that performs
 139        the assignment, if known, otherwise it is the target of the
 140        assignment.  */
 141     rtx loc;
 142
 143     /* Stack adjustment.  */
 144     HOST_WIDE_INT adjust;
 145   } u;
 146
 147   /* The instruction which the micro operation is in, for MO_USE,
 148      MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent
 149      instruction or note in the original flow (before any var-tracking
 150      notes are inserted, to simplify emission of notes), for MO_SET
 151      and MO_CLOBBER.  */
 152   rtx insn;
 153 } micro_operation;
 154
 155 /* Structure for passing some other parameters to function
 156    emit_note_insn_var_location.  */
 157 typedef struct emit_note_data_def
 158 {
 159   /* The instruction which the note will be emitted before/after.  */
 160   rtx insn;
 161
 162   /* Where the note will be emitted (before/after insn)?  */
 163   enum emit_note_where where;
 164 } emit_note_data;
 165
 166 /* Description of location of a part of a variable.  The content of a physical
 167    register is described by a chain of these structures.
 168    The chains are pretty short (usually 1 or 2 elements) and thus
 169    chain is the best data structure.  */
 170 typedef struct attrs_def
 171 {
 172   /* Pointer to next member of the list.  */
 173   struct attrs_def *next;
 174
 175   /* The rtx of register.  */
 176   rtx loc;
 177
 178   /* The declaration corresponding to LOC.  */
 179   tree decl;
 180
 181   /* Offset from start of DECL.  */
 182   HOST_WIDE_INT offset;
 183 } *attrs;
 184
 185 /* Structure holding a refcounted hash table.  If refcount > 1,
 186    it must be first unshared before modified.  */
 187 typedef struct shared_hash_def
 188 {
 189   /* Reference count.  */
 190   int refcount;
 191
 192   /* Actual hash table.  */
 193   htab_t htab;
 194 } *shared_hash;
 195
 196 /* Structure holding the IN or OUT set for a basic block.  */
 197 typedef struct dataflow_set_def
 198 {
 199   /* Adjustment of stack offset.  */
 200   HOST_WIDE_INT stack_adjust;
 201
 202   /* Attributes for registers (lists of attrs).  */
 203   attrs regs[FIRST_PSEUDO_REGISTER];
 204
 205   /* Variable locations.  */
 206   shared_hash vars;
 207 } dataflow_set;
 208
 209 /* The structure (one for each basic block) containing the information
 210    needed for variable tracking.  */
 211 typedef struct variable_tracking_info_def
 212 {
 213   /* Number of micro operations stored in the MOS array.  */
 214   int n_mos;
 215
 216   /* The array of micro operations.  */
 217   micro_operation *mos;
 218
 219   /* The IN and OUT set for dataflow analysis.  */
 220   dataflow_set in;
 221   dataflow_set out;
 222
 223   /* Has the block been visited in DFS?  */
 224   bool visited;
 225 } *variable_tracking_info;
 226
 227 /* Structure for chaining the locations.  */
 228 typedef struct location_chain_def
 229 {
 230   /* Next element in the chain.  */
 231   struct location_chain_def *next;
 232
 233   /* The location (REG or MEM).  */
 234   rtx loc;
 235
 236   /* The "value" stored in this location.  */
 237   rtx set_src;
 238
 239   /* Initialized? */
 240   enum var_init_status init;
 241 } *location_chain;
 242
 243 /* Structure describing one part of variable.  */
 244 typedef struct variable_part_def
 245 {
 246   /* Chain of locations of the part.  */
 247   location_chain loc_chain;
 248
 249   /* Location which was last emitted to location list.  */
 250   rtx cur_loc;
 251
 252   /* The offset in the variable.  */
 253   HOST_WIDE_INT offset;
 254 } variable_part;
 255
 256 /* Maximum number of location parts.  */
 257 #define MAX_VAR_PARTS 16
 258
 259 /* Structure describing where the variable is located.  */
 260 typedef struct variable_def
 261 {
 262   /* The declaration of the variable.  */
 263   tree decl;
 264
 265   /* Reference count.  */
 266   int refcount;
 267
 268   /* Number of variable parts.  */
 269   int n_var_parts;
 270
 271   /* The variable parts.  */
 272   variable_part var_part[MAX_VAR_PARTS];
 273 } *variable;
 274 typedef const struct variable_def *const_variable;
 275
 276 /* Hash function for DECL for VARIABLE_HTAB.  */
 277 #define VARIABLE_HASH_VAL(decl) (DECL_UID (decl))
 278
 279 /* Pointer to the BB's information specific to variable tracking pass.  */
 280 #define VTI(BB) ((variable_tracking_info) (BB)->aux)
 281
 282 /* Macro to access MEM_OFFSET as an HOST_WIDE_INT.  Evaluates MEM twice.  */
 283 #define INT_MEM_OFFSET(mem) (MEM_OFFSET (mem) ? INTVAL (MEM_OFFSET (mem)) : 0)
 284
 285 /* Alloc pool for struct attrs_def.  */
 286 static alloc_pool attrs_pool;
 287
 288 /* Alloc pool for struct variable_def.  */
 289 static alloc_pool var_pool;
 290
 291 /* Alloc pool for struct location_chain_def.  */
 292 static alloc_pool loc_chain_pool;
 293
 294 /* Alloc pool for struct shared_hash_def.  */
 295 static alloc_pool shared_hash_pool;
 296
 297 /* Changed variables, notes will be emitted for them.  */
 298 static htab_t changed_variables;
 299
 300 /* Shall notes be emitted?  */
 301 static bool emit_notes;
 302
 303 /* Empty shared hashtable.  */
 304 static shared_hash empty_shared_hash;
 305
 306 /* Local function prototypes.  */
 307 static void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
 308                                           HOST_WIDE_INT *);
 309 static void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *,
 310                                                HOST_WIDE_INT *);
 311 static void bb_stack_adjust_offset (basic_block);
 312 static bool vt_stack_adjustments (void);
 313 static rtx adjust_stack_reference (rtx, HOST_WIDE_INT);
 314 static hashval_t variable_htab_hash (const void *);
 315 static int variable_htab_eq (const void *, const void *);
 316 static void variable_htab_free (void *);
 317
 318 static void init_attrs_list_set (attrs *);
 319 static void attrs_list_clear (attrs *);
 320 static attrs attrs_list_member (attrs, tree, HOST_WIDE_INT);
 321 static void attrs_list_insert (attrs *, tree, HOST_WIDE_INT, rtx);
 322 static void attrs_list_copy (attrs *, attrs);
 323 static void attrs_list_union (attrs *, attrs);
 324
 325 static variable unshare_variable (dataflow_set *set, variable var,
 326                                   enum var_init_status);
 327 static int vars_copy_1 (void **, void *);
 328 static void vars_copy (htab_t, htab_t);
 329 static tree var_debug_decl (tree);
 330 static void var_reg_set (dataflow_set *, rtx, enum var_init_status, rtx);
 331 static void var_reg_delete_and_set (dataflow_set *, rtx, bool,
 332                                     enum var_init_status, rtx);
 333 static void var_reg_delete (dataflow_set *, rtx, bool);
 334 static void var_regno_delete (dataflow_set *, int);
 335 static void var_mem_set (dataflow_set *, rtx, enum var_init_status, rtx);
 336 static void var_mem_delete_and_set (dataflow_set *, rtx, bool,
 337                                     enum var_init_status, rtx);
 338 static void var_mem_delete (dataflow_set *, rtx, bool);
 339
 340 static void dataflow_set_init (dataflow_set *);
 341 static void dataflow_set_clear (dataflow_set *);
 342 static void dataflow_set_copy (dataflow_set *, dataflow_set *);
 343 static int variable_union_info_cmp_pos (const void *, const void *);
 344 static int variable_union (void **, void *);
 345 static int variable_canonicalize (void **, void *);
 346 static void dataflow_set_union (dataflow_set *, dataflow_set *);
 347 static bool variable_part_different_p (variable_part *, variable_part *);
 348 static bool variable_different_p (variable, variable, bool);
 349 static int dataflow_set_different_1 (void **, void *);
 350 static int dataflow_set_different_2 (void **, void *);
 351 static bool dataflow_set_different (dataflow_set *, dataflow_set *);
 352 static void dataflow_set_destroy (dataflow_set *);
 353
 354 static bool contains_symbol_ref (rtx);
 355 static bool track_expr_p (tree);
 356 static bool same_variable_part_p (rtx, tree, HOST_WIDE_INT);
 357 static int count_uses (rtx *, void *);
 358 static void count_uses_1 (rtx *, void *);
 359 static void count_stores (rtx, const_rtx, void *);
 360 static int add_uses (rtx *, void *);
 361 static void add_uses_1 (rtx *, void *);
 362 static void add_stores (rtx, const_rtx, void *);
 363 static bool compute_bb_dataflow (basic_block);
 364 static void vt_find_locations (void);
 365
 366 static void dump_attrs_list (attrs);
 367 static int dump_variable (void **, void *);
 368 static void dump_vars (htab_t);
 369 static void dump_dataflow_set (dataflow_set *);
 370 static void dump_dataflow_sets (void);
 371
 372 static void variable_was_changed (variable, dataflow_set *);
 373 static void set_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT,
 374                                enum var_init_status, rtx);
 375 static void clobber_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT,
 376                                    rtx);
 377 static void delete_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT);
 378 static int emit_note_insn_var_location (void **, void *);
 379 static void emit_notes_for_changes (rtx, enum emit_note_where);
 380 static int emit_notes_for_differences_1 (void **, void *);
 381 static int emit_notes_for_differences_2 (void **, void *);
 382 static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
 383 static void emit_notes_in_bb (basic_block);
 384 static void vt_emit_notes (void);
 385
 386 static bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *);
 387 static void vt_add_function_parameters (void);
 388 static void vt_initialize (void);
 389 static void vt_finalize (void);
 390
 391 /* Given a SET, calculate the amount of stack adjustment it contains
 392    PRE- and POST-modifying stack pointer.
 393    This function is similar to stack_adjust_offset.  */
 394
 395 static void
 396 stack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre,
 397                               HOST_WIDE_INT *post)
 398 {
 399   rtx src = SET_SRC (pattern);
 400   rtx dest = SET_DEST (pattern);
 401   enum rtx_code code;
 402
 403   if (dest == stack_pointer_rtx)
 404     {
 405       /* (set (reg sp) (plus (reg sp) (const_int))) */
 406       code = GET_CODE (src);
 407       if (! (code == PLUS || code == MINUS)
 408           || XEXP (src, 0) != stack_pointer_rtx
 409           || GET_CODE (XEXP (src, 1)) != CONST_INT)
 410         return;
 411
 412       if (code == MINUS)
 413         *post += INTVAL (XEXP (src, 1));
 414       else
 415         *post -= INTVAL (XEXP (src, 1));
 416     }
 417   else if (MEM_P (dest))
 418     {
 419       /* (set (mem (pre_dec (reg sp))) (foo)) */
 420       src = XEXP (dest, 0);
 421       code = GET_CODE (src);
 422
 423       switch (code)
 424         {
 425         case PRE_MODIFY:
 426         case POST_MODIFY:
 427           if (XEXP (src, 0) == stack_pointer_rtx)
 428             {
 429               rtx val = XEXP (XEXP (src, 1), 1);
 430               /* We handle only adjustments by constant amount.  */
 431               gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS &&
 432                           GET_CODE (val) == CONST_INT);
 433
 434               if (code == PRE_MODIFY)
 435                 *pre -= INTVAL (val);
 436               else
 437                 *post -= INTVAL (val);
 438               break;
 439             }
 440           return;
 441
 442         case PRE_DEC:
 443           if (XEXP (src, 0) == stack_pointer_rtx)
 444             {
 445               *pre += GET_MODE_SIZE (GET_MODE (dest));
 446               break;
 447             }
 448           return;
 449
 450         case POST_DEC:
 451           if (XEXP (src, 0) == stack_pointer_rtx)
 452             {
 453               *post += GET_MODE_SIZE (GET_MODE (dest));
 454               break;
 455             }
 456           return;
 457
 458         case PRE_INC:
 459           if (XEXP (src, 0) == stack_pointer_rtx)
 460             {
 461               *pre -= GET_MODE_SIZE (GET_MODE (dest));
 462               break;
 463             }
 464           return;
 465
 466         case POST_INC:
 467           if (XEXP (src, 0) == stack_pointer_rtx)
 468             {
 469               *post -= GET_MODE_SIZE (GET_MODE (dest));
 470               break;
 471             }
 472           return;
 473
 474         default:
 475           return;
 476         }
 477     }
 478 }
 479
 480 /* Given an INSN, calculate the amount of stack adjustment it contains
 481    PRE- and POST-modifying stack pointer.  */
 482
 483 static void
 484 insn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre,
 485                                    HOST_WIDE_INT *post)
 486 {
 487   rtx pattern;
 488
 489   *pre = 0;
 490   *post = 0;
 491
 492   pattern = PATTERN (insn);
 493   if (RTX_FRAME_RELATED_P (insn))
 494     {
 495       rtx expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
 496       if (expr)
 497         pattern = XEXP (expr, 0);
 498     }
 499
 500   if (GET_CODE (pattern) == SET)
 501     stack_adjust_offset_pre_post (pattern, pre, post);
 502   else if (GET_CODE (pattern) == PARALLEL
 503            || GET_CODE (pattern) == SEQUENCE)
 504     {
 505       int i;
 506
 507       /* There may be stack adjustments inside compound insns.  Search
 508          for them.  */
 509       for ( i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
 510         if (GET_CODE (XVECEXP (pattern, 0, i)) == SET)
 511           stack_adjust_offset_pre_post (XVECEXP (pattern, 0, i), pre, post);
 512     }
 513 }
 514
 515 /* Compute stack adjustment in basic block BB.  */
 516
 517 static void
 518 bb_stack_adjust_offset (basic_block bb)
 519 {
 520   HOST_WIDE_INT offset;
 521   int i;
 522
 523   offset = VTI (bb)->in.stack_adjust;
 524   for (i = 0; i < VTI (bb)->n_mos; i++)
 525     {
 526       if (VTI (bb)->mos[i].type == MO_ADJUST)
 527         offset += VTI (bb)->mos[i].u.adjust;
 528       else if (VTI (bb)->mos[i].type != MO_CALL)
 529         {
 530           if (MEM_P (VTI (bb)->mos[i].u.loc))
 531             {
 532               VTI (bb)->mos[i].u.loc
 533                 = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset);
 534             }
 535         }
 536     }
 537   VTI (bb)->out.stack_adjust = offset;
 538 }
 539
 540 /* Compute stack adjustments for all blocks by traversing DFS tree.
 541    Return true when the adjustments on all incoming edges are consistent.
 542    Heavily borrowed from pre_and_rev_post_order_compute.  */
 543
 544 static bool
 545 vt_stack_adjustments (void)
 546 {
 547   edge_iterator *stack;
 548   int sp;
 549
 550   /* Initialize entry block.  */
 551   VTI (ENTRY_BLOCK_PTR)->visited = true;
 552   VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET;
 553
 554   /* Allocate stack for back-tracking up CFG.  */
 555   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 556   sp = 0;
 557
 558   /* Push the first edge on to the stack.  */
 559   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 560
 561   while (sp)
 562     {
 563       edge_iterator ei;
 564       basic_block src;
 565       basic_block dest;
 566
 567       /* Look at the edge on the top of the stack.  */
 568       ei = stack[sp - 1];
 569       src = ei_edge (ei)->src;
 570       dest = ei_edge (ei)->dest;
 571
 572       /* Check if the edge destination has been visited yet.  */
 573       if (!VTI (dest)->visited)
 574         {
 575           VTI (dest)->visited = true;
 576           VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust;
 577           bb_stack_adjust_offset (dest);
 578
 579           if (EDGE_COUNT (dest->succs) > 0)
 580             /* Since the DEST node has been visited for the first
 581                time, check its successors.  */
 582             stack[sp++] = ei_start (dest->succs);
 583         }
 584       else
 585         {
 586           /* Check whether the adjustments on the edges are the same.  */
 587           if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust)
 588             {
 589               free (stack);
 590               return false;
 591             }
 592
 593           if (! ei_one_before_end_p (ei))
 594             /* Go to the next edge.  */
 595             ei_next (&stack[sp - 1]);
 596           else
 597             /* Return to previous level if there are no more edges.  */
 598             sp--;
 599         }
 600     }
 601
 602   free (stack);
 603   return true;
 604 }
 605
 606 /* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative
 607    to the argument pointer.  Return the new rtx.  */
 608
 609 static rtx
 610 adjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment)
 611 {
 612   rtx addr, cfa, tmp;
 613
 614 #ifdef FRAME_POINTER_CFA_OFFSET
 615   adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl);
 616   cfa = plus_constant (frame_pointer_rtx, adjustment);
 617 #else
 618   adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl);
 619   cfa = plus_constant (arg_pointer_rtx, adjustment);
 620 #endif
 621
 622   addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa);
 623   tmp = simplify_rtx (addr);
 624   if (tmp)
 625     addr = tmp;
 626
 627   return replace_equiv_address_nv (mem, addr);
 628 }
 629
 630 /* The hash function for variable_htab, computes the hash value
 631    from the declaration of variable X.  */
 632
 633 static hashval_t
 634 variable_htab_hash (const void *x)
 635 {
 636   const_variable const v = (const_variable) x;
 637
 638   return (VARIABLE_HASH_VAL (v->decl));
 639 }
 640
 641 /* Compare the declaration of variable X with declaration Y.  */
 642
 643 static int
 644 variable_htab_eq (const void *x, const void *y)
 645 {
 646   const_variable const v = (const_variable) x;
 647   const_tree const decl = (const_tree) y;
 648
 649   return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl));
 650 }
 651
 652 /* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
 653
 654 static void
 655 variable_htab_free (void *elem)
 656 {
 657   int i;
 658   variable var = (variable) elem;
 659   location_chain node, next;
 660
 661   gcc_assert (var->refcount > 0);
 662
 663   var->refcount--;
 664   if (var->refcount > 0)
 665     return;
 666
 667   for (i = 0; i < var->n_var_parts; i++)
 668     {
 669       for (node = var->var_part[i].loc_chain; node; node = next)
 670         {
 671           next = node->next;
 672           pool_free (loc_chain_pool, node);
 673         }
 674       var->var_part[i].loc_chain = NULL;
 675     }
 676   pool_free (var_pool, var);
 677 }
 678
 679 /* Initialize the set (array) SET of attrs to empty lists.  */
 680
 681 static void
 682 init_attrs_list_set (attrs *set)
 683 {
 684   int i;
 685
 686   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 687     set[i] = NULL;
 688 }
 689
 690 /* Make the list *LISTP empty.  */
 691
 692 static void
 693 attrs_list_clear (attrs *listp)
 694 {
 695   attrs list, next;
 696
 697   for (list = *listp; list; list = next)
 698     {
 699       next = list->next;
 700       pool_free (attrs_pool, list);
 701     }
 702   *listp = NULL;
 703 }
 704
 705 /* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
 706
 707 static attrs
 708 attrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset)
 709 {
 710   for (; list; list = list->next)
 711     if (list->decl == decl && list->offset == offset)
 712       return list;
 713   return NULL;
 714 }
 715
 716 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
 717
 718 static void
 719 attrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc)
 720 {
 721   attrs list;
 722
 723   list = (attrs) pool_alloc (attrs_pool);
 724   list->loc = loc;
 725   list->decl = decl;
 726   list->offset = offset;
 727   list->next = *listp;
 728   *listp = list;
 729 }
 730
 731 /* Copy all nodes from SRC and create a list *DSTP of the copies.  */
 732
 733 static void
 734 attrs_list_copy (attrs *dstp, attrs src)
 735 {
 736   attrs n;
 737
 738   attrs_list_clear (dstp);
 739   for (; src; src = src->next)
 740     {
 741       n = (attrs) pool_alloc (attrs_pool);
 742       n->loc = src->loc;
 743       n->decl = src->decl;
 744       n->offset = src->offset;
 745       n->next = *dstp;
 746       *dstp = n;
 747     }
 748 }
 749
 750 /* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
 751
 752 static void
 753 attrs_list_union (attrs *dstp, attrs src)
 754 {
 755   for (; src; src = src->next)
 756     {
 757       if (!attrs_list_member (*dstp, src->decl, src->offset))
 758         attrs_list_insert (dstp, src->decl, src->offset, src->loc);
 759     }
 760 }
 761
 762 /* Shared hashtable support.  */
 763
 764 /* Return true if VARS is shared.  */
 765
 766 static inline bool
 767 shared_hash_shared (shared_hash vars)
 768 {
 769   return vars->refcount > 1;
 770 }
 771
 772 /* Return the hash table for VARS.  */
 773
 774 static inline htab_t
 775 shared_hash_htab (shared_hash vars)
 776 {
 777   return vars->htab;
 778 }
 779
 780 /* Copy variables into a new hash table.  */
 781
 782 static shared_hash
 783 shared_hash_unshare (shared_hash vars)
 784 {
 785   shared_hash new_vars = (shared_hash) pool_alloc (shared_hash_pool);
 786   gcc_assert (vars->refcount > 1);
 787   new_vars->refcount = 1;
 788   new_vars->htab
 789     = htab_create (htab_elements (vars->htab) + 3, variable_htab_hash,
 790                    variable_htab_eq, variable_htab_free);
 791   vars_copy (new_vars->htab, vars->htab);
 792   vars->refcount--;
 793   return new_vars;
 794 }
 795
 796 /* Increment reference counter on VARS and return it.  */
 797
 798 static inline shared_hash
 799 shared_hash_copy (shared_hash vars)
 800 {
 801   vars->refcount++;
 802   return vars;
 803 }
 804
 805 /* Decrement reference counter and destroy hash table if not shared
 806    anymore.  */
 807
 808 static void
 809 shared_hash_destroy (shared_hash vars)
 810 {
 811   gcc_assert (vars->refcount > 0);
 812   if (--vars->refcount == 0)
 813     {
 814       htab_delete (vars->htab);
 815       pool_free (shared_hash_pool, vars);
 816     }
 817 }
 818
 819 /* Unshare *PVARS if shared and return slot for DECL.  If INS is
 820    INSERT, insert it if not already present.  */
 821
 822 static inline void **
 823 shared_hash_find_slot_unshare (shared_hash *pvars, tree decl,
 824                                enum insert_option ins)
 825 {
 826   if (shared_hash_shared (*pvars))
 827     *pvars = shared_hash_unshare (*pvars);
 828   return htab_find_slot_with_hash (shared_hash_htab (*pvars), decl,
 829                                    VARIABLE_HASH_VAL (decl), ins);
 830 }
 831
 832 /* Return slot for DECL, if it is already present in the hash table.
 833    If it is not present, insert it only VARS is not shared, otherwise
 834    return NULL.  */
 835
 836 static inline void **
 837 shared_hash_find_slot (shared_hash vars, tree decl)
 838 {
 839   return htab_find_slot_with_hash (shared_hash_htab (vars), decl,
 840                                    VARIABLE_HASH_VAL (decl),
 841                                    shared_hash_shared (vars)
 842                                    ? NO_INSERT : INSERT);
 843 }
 844
 845 /* Return slot for DECL only if it is already present in the hash table.  */
 846
 847 static inline void **
 848 shared_hash_find_slot_noinsert (shared_hash vars, tree decl)
 849 {
 850   return htab_find_slot_with_hash (shared_hash_htab (vars), decl,
 851                                    VARIABLE_HASH_VAL (decl), NO_INSERT);
 852 }
 853
 854 /* Return variable for DECL or NULL if not already present in the hash
 855    table.  */
 856
 857 static inline variable
 858 shared_hash_find (shared_hash vars, tree decl)
 859 {
 860   return (variable)
 861          htab_find_with_hash (shared_hash_htab (vars), decl,
 862                               VARIABLE_HASH_VAL (decl));
 863 }
 864
 865 /* Return a copy of a variable VAR and insert it to dataflow set SET.  */
 866
 867 static variable
 868 unshare_variable (dataflow_set *set, variable var,
 869                   enum var_init_status initialized)
 870 {
 871   void **slot;
 872   variable new_var;
 873   int i;
 874
 875   new_var = (variable) pool_alloc (var_pool);
 876   new_var->decl = var->decl;
 877   new_var->refcount = 1;
 878   var->refcount--;
 879   new_var->n_var_parts = var->n_var_parts;
 880
 881   for (i = 0; i < var->n_var_parts; i++)
 882     {
 883       location_chain node;
 884       location_chain *nextp;
 885
 886       new_var->var_part[i].offset = var->var_part[i].offset;
 887       nextp = &new_var->var_part[i].loc_chain;
 888       for (node = var->var_part[i].loc_chain; node; node = node->next)
 889         {
 890           location_chain new_lc;
 891
 892           new_lc = (location_chain) pool_alloc (loc_chain_pool);
 893           new_lc->next = NULL;
 894           if (node->init > initialized)
 895             new_lc->init = node->init;
 896           else
 897             new_lc->init = initialized;
 898           if (node->set_src && !(MEM_P (node->set_src)))
 899             new_lc->set_src = node->set_src;
 900           else
 901             new_lc->set_src = NULL;
 902           new_lc->loc = node->loc;
 903
 904           *nextp = new_lc;
 905           nextp = &new_lc->next;
 906         }
 907
 908       /* We are at the basic block boundary when copying variable description
 909          so set the CUR_LOC to be the first element of the chain.  */
 910       if (new_var->var_part[i].loc_chain)
 911         new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
 912       else
 913         new_var->var_part[i].cur_loc = NULL;
 914     }
 915
 916   slot = shared_hash_find_slot_unshare (&set->vars, new_var->decl, INSERT);
 917   *slot = new_var;
 918   return new_var;
 919 }
 920
 921 /* Add a variable from *SLOT to hash table DATA and increase its reference
 922    count.  */
 923
 924 static int
 925 vars_copy_1 (void **slot, void *data)
 926 {
 927   htab_t dst = (htab_t) data;
 928   variable src, *dstp;
 929
 930   src = *(variable *) slot;
 931   src->refcount++;
 932
 933   dstp = (variable *) htab_find_slot_with_hash (dst, src->decl,
 934                                                 VARIABLE_HASH_VAL (src->decl),
 935                                                 INSERT);
 936   *dstp = src;
 937
 938   /* Continue traversing the hash table.  */
 939   return 1;
 940 }
 941
 942 /* Copy all variables from hash table SRC to hash table DST.  */
 943
 944 static void
 945 vars_copy (htab_t dst, htab_t src)
 946 {
 947   htab_traverse_noresize (src, vars_copy_1, dst);
 948 }
 949
 950 /* Map a decl to its main debug decl.  */
 951
 952 static inline tree
 953 var_debug_decl (tree decl)
 954 {
 955   if (decl && DECL_P (decl)
 956       && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl)
 957       && DECL_P (DECL_DEBUG_EXPR (decl)))
 958     decl = DECL_DEBUG_EXPR (decl);
 959
 960   return decl;
 961 }
 962
 963 /* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
 964
 965 static void
 966 var_reg_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
 967              rtx set_src)
 968 {
 969   tree decl = REG_EXPR (loc);
 970   HOST_WIDE_INT offset = REG_OFFSET (loc);
 971   attrs node;
 972
 973   decl = var_debug_decl (decl);
 974
 975   for (node = set->regs[REGNO (loc)]; node; node = node->next)
 976     if (node->decl == decl && node->offset == offset)
 977       break;
 978   if (!node)
 979     attrs_list_insert (&set->regs[REGNO (loc)], decl, offset, loc);
 980   set_variable_part (set, loc, decl, offset, initialized, set_src);
 981 }
 982
 983 static enum var_init_status
 984 get_init_value (dataflow_set *set, rtx loc, tree decl)
 985 {
 986   variable var;
 987   int i;
 988   enum var_init_status ret_val = VAR_INIT_STATUS_UNKNOWN;
 989
 990   if (! flag_var_tracking_uninit)
 991     return VAR_INIT_STATUS_INITIALIZED;
 992
 993   var = shared_hash_find (set->vars, decl);
 994   if (var)
 995     {
 996       for (i = 0; i < var->n_var_parts && ret_val == VAR_INIT_STATUS_UNKNOWN; i++)
 997         {
 998           location_chain nextp;
 999           for (nextp = var->var_part[i].loc_chain; nextp; nextp = nextp->next)
1000             if (rtx_equal_p (nextp->loc, loc))
1001               {
1002                 ret_val = nextp->init;
1003                 break;
1004               }
1005         }
1006     }
1007
1008   return ret_val;
1009 }
1010
1011 /* Delete current content of register LOC in dataflow set SET and set
1012    the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  If
1013    MODIFY is true, any other live copies of the same variable part are
1014    also deleted from the dataflow set, otherwise the variable part is
1015    assumed to be copied from another location holding the same
1016    part.  */
1017
1018 static void
1019 var_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify,
1020                         enum var_init_status initialized, rtx set_src)
1021 {
1022   tree decl = REG_EXPR (loc);
1023   HOST_WIDE_INT offset = REG_OFFSET (loc);
1024   attrs node, next;
1025   attrs *nextp;
1026
1027   decl = var_debug_decl (decl);
1028
1029   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1030     initialized = get_init_value (set, loc, decl);
1031
1032   nextp = &set->regs[REGNO (loc)];
1033   for (node = *nextp; node; node = next)
1034     {
1035       next = node->next;
1036       if (node->decl != decl || node->offset != offset)
1037         {
1038           delete_variable_part (set, node->loc, node->decl, node->offset);
1039           pool_free (attrs_pool, node);
1040           *nextp = next;
1041         }
1042       else
1043         {
1044           node->loc = loc;
1045           nextp = &node->next;
1046         }
1047     }
1048   if (modify)
1049     clobber_variable_part (set, loc, decl, offset, set_src);
1050   var_reg_set (set, loc, initialized, set_src);
1051 }
1052
1053 /* Delete current content of register LOC in dataflow set SET.  If
1054    CLOBBER is true, also delete any other live copies of the same
1055    variable part.  */
1056
1057 static void
1058 var_reg_delete (dataflow_set *set, rtx loc, bool clobber)
1059 {
1060   attrs *reg = &set->regs[REGNO (loc)];
1061   attrs node, next;
1062
1063   if (clobber)
1064     {
1065       tree decl = REG_EXPR (loc);
1066       HOST_WIDE_INT offset = REG_OFFSET (loc);
1067
1068       decl = var_debug_decl (decl);
1069
1070       clobber_variable_part (set, NULL, decl, offset, NULL);
1071     }
1072
1073   for (node = *reg; node; node = next)
1074     {
1075       next = node->next;
1076       delete_variable_part (set, node->loc, node->decl, node->offset);
1077       pool_free (attrs_pool, node);
1078     }
1079   *reg = NULL;
1080 }
1081
1082 /* Delete content of register with number REGNO in dataflow set SET.  */
1083
1084 static void
1085 var_regno_delete (dataflow_set *set, int regno)
1086 {
1087   attrs *reg = &set->regs[regno];
1088   attrs node, next;
1089
1090   for (node = *reg; node; node = next)
1091     {
1092       next = node->next;
1093       delete_variable_part (set, node->loc, node->decl, node->offset);
1094       pool_free (attrs_pool, node);
1095     }
1096   *reg = NULL;
1097 }
1098
1099 /* Set the location part of variable MEM_EXPR (LOC) in dataflow set
1100    SET to LOC.
1101    Adjust the address first if it is stack pointer based.  */
1102
1103 static void
1104 var_mem_set (dataflow_set *set, rtx loc, enum var_init_status initialized,
1105              rtx set_src)
1106 {
1107   tree decl = MEM_EXPR (loc);
1108   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1109
1110   decl = var_debug_decl (decl);
1111
1112   set_variable_part (set, loc, decl, offset, initialized, set_src);
1113 }
1114
1115 /* Delete and set the location part of variable MEM_EXPR (LOC) in
1116    dataflow set SET to LOC.  If MODIFY is true, any other live copies
1117    of the same variable part are also deleted from the dataflow set,
1118    otherwise the variable part is assumed to be copied from another
1119    location holding the same part.
1120    Adjust the address first if it is stack pointer based.  */
1121
1122 static void
1123 var_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify,
1124                         enum var_init_status initialized, rtx set_src)
1125 {
1126   tree decl = MEM_EXPR (loc);
1127   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1128
1129   decl = var_debug_decl (decl);
1130
1131   if (initialized == VAR_INIT_STATUS_UNKNOWN)
1132     initialized = get_init_value (set, loc, decl);
1133
1134   if (modify)
1135     clobber_variable_part (set, NULL, decl, offset, set_src);
1136   var_mem_set (set, loc, initialized, set_src);
1137 }
1138
1139 /* Delete the location part LOC from dataflow set SET.  If CLOBBER is
1140    true, also delete any other live copies of the same variable part.
1141    Adjust the address first if it is stack pointer based.  */
1142
1143 static void
1144 var_mem_delete (dataflow_set *set, rtx loc, bool clobber)
1145 {
1146   tree decl = MEM_EXPR (loc);
1147   HOST_WIDE_INT offset = INT_MEM_OFFSET (loc);
1148
1149   decl = var_debug_decl (decl);
1150   if (clobber)
1151     clobber_variable_part (set, NULL, decl, offset, NULL);
1152   delete_variable_part (set, loc, decl, offset);
1153 }
1154
1155 /* Initialize dataflow set SET to be empty.
1156    VARS_SIZE is the initial size of hash table VARS.  */
1157
1158 static void
1159 dataflow_set_init (dataflow_set *set)
1160 {
1161   init_attrs_list_set (set->regs);
1162   set->vars = shared_hash_copy (empty_shared_hash);
1163   set->stack_adjust = 0;
1164 }
1165
1166 /* Delete the contents of dataflow set SET.  */
1167
1168 static void
1169 dataflow_set_clear (dataflow_set *set)
1170 {
1171   int i;
1172
1173   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1174     attrs_list_clear (&set->regs[i]);
1175
1176   shared_hash_destroy (set->vars);
1177   set->vars = shared_hash_copy (empty_shared_hash);
1178 }
1179
1180 /* Copy the contents of dataflow set SRC to DST.  */
1181
1182 static void
1183 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
1184 {
1185   int i;
1186
1187   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1188     attrs_list_copy (&dst->regs[i], src->regs[i]);
1189
1190   shared_hash_destroy (dst->vars);
1191   dst->vars = shared_hash_copy (src->vars);
1192   dst->stack_adjust = src->stack_adjust;
1193 }
1194
1195 /* Information for merging lists of locations for a given offset of variable.
1196  */
1197 struct variable_union_info
1198 {
1199   /* Node of the location chain.  */
1200   location_chain lc;
1201
1202   /* The sum of positions in the input chains.  */
1203   int pos;
1204
1205   /* The position in the chains of SRC and DST dataflow sets.  */
1206   int pos_src;
1207   int pos_dst;
1208 };
1209
1210 /* Compare function for qsort, order the structures by POS element.  */
1211
1212 static int
1213 variable_union_info_cmp_pos (const void *n1, const void *n2)
1214 {
1215   const struct variable_union_info *const i1 =
1216     (const struct variable_union_info *) n1;
1217   const struct variable_union_info *const i2 =
1218     ( const struct variable_union_info *) n2;
1219
1220   if (i1->pos != i2->pos)
1221     return i1->pos - i2->pos;
1222
1223   return (i1->pos_dst - i2->pos_dst);
1224 }
1225
1226 /* Compute union of location parts of variable *SLOT and the same variable
1227    from hash table DATA.  Compute "sorted" union of the location chains
1228    for common offsets, i.e. the locations of a variable part are sorted by
1229    a priority where the priority is the sum of the positions in the 2 chains
1230    (if a location is only in one list the position in the second list is
1231    defined to be larger than the length of the chains).
1232    When we are updating the location parts the newest location is in the
1233    beginning of the chain, so when we do the described "sorted" union
1234    we keep the newest locations in the beginning.  */
1235
1236 static int
1237 variable_union (void **slot, void *data)
1238 {
1239   variable src, dst;
1240   void **dstp;
1241   dataflow_set *set = (dataflow_set *) data;
1242   int i, j, k;
1243
1244   src = *(variable *) slot;
1245   dstp = shared_hash_find_slot (set->vars, src->decl);
1246   if (!dstp || !*dstp)
1247     {
1248       src->refcount++;
1249
1250       /* If CUR_LOC of some variable part is not the first element of
1251          the location chain we are going to change it so we have to make
1252          a copy of the variable.  */
1253       for (k = 0; k < src->n_var_parts; k++)
1254         {
1255           gcc_assert (!src->var_part[k].loc_chain
1256                       == !src->var_part[k].cur_loc);
1257           if (src->var_part[k].loc_chain)
1258             {
1259               gcc_assert (src->var_part[k].cur_loc);
1260               if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1261                 break;
1262             }
1263         }
1264       if (k < src->n_var_parts)
1265         {
1266           enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
1267
1268           if (! flag_var_tracking_uninit)
1269             status = VAR_INIT_STATUS_INITIALIZED;
1270
1271           if (dstp)
1272             *dstp = (void *) src;
1273           unshare_variable (set, src, status);
1274         }
1275       else
1276         {
1277           if (!dstp)
1278             dstp = shared_hash_find_slot_unshare (&set->vars, src->decl,
1279                                                   INSERT);
1280           *dstp = (void *) src;
1281         }
1282
1283       /* Continue traversing the hash table.  */
1284       return 1;
1285     }
1286   else
1287     dst = (variable) *dstp;
1288
1289   gcc_assert (src->n_var_parts);
1290
1291   /* Count the number of location parts, result is K.  */
1292   for (i = 0, j = 0, k = 0;
1293        i < src->n_var_parts && j < dst->n_var_parts; k++)
1294     {
1295       if (src->var_part[i].offset == dst->var_part[j].offset)
1296         {
1297           i++;
1298           j++;
1299         }
1300       else if (src->var_part[i].offset < dst->var_part[j].offset)
1301         i++;
1302       else
1303         j++;
1304     }
1305   k += src->n_var_parts - i;
1306   k += dst->n_var_parts - j;
1307
1308   /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1309      thus there are at most MAX_VAR_PARTS different offsets.  */
1310   gcc_assert (k <= MAX_VAR_PARTS);
1311
1312   if ((dst->refcount > 1 || shared_hash_shared (set->vars))
1313       && dst->n_var_parts != k)
1314     {
1315       enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
1316
1317       if (! flag_var_tracking_uninit)
1318         status = VAR_INIT_STATUS_INITIALIZED;
1319       dst = unshare_variable (set, dst, status);
1320     }
1321
1322   i = src->n_var_parts - 1;
1323   j = dst->n_var_parts - 1;
1324   dst->n_var_parts = k;
1325
1326   for (k--; k >= 0; k--)
1327     {
1328       location_chain node, node2;
1329
1330       if (i >= 0 && j >= 0
1331           && src->var_part[i].offset == dst->var_part[j].offset)
1332         {
1333           /* Compute the "sorted" union of the chains, i.e. the locations which
1334              are in both chains go first, they are sorted by the sum of
1335              positions in the chains.  */
1336           int dst_l, src_l;
1337           int ii, jj, n;
1338           struct variable_union_info *vui;
1339
1340           /* If DST is shared compare the location chains.
1341              If they are different we will modify the chain in DST with
1342              high probability so make a copy of DST.  */
1343           if (dst->refcount > 1 || shared_hash_shared (set->vars))
1344             {
1345               for (node = src->var_part[i].loc_chain,
1346                    node2 = dst->var_part[j].loc_chain; node && node2;
1347                    node = node->next, node2 = node2->next)
1348                 {
1349                   if (!((REG_P (node2->loc)
1350                          && REG_P (node->loc)
1351                          && REGNO (node2->loc) == REGNO (node->loc))
1352                         || rtx_equal_p (node2->loc, node->loc)))
1353                     {
1354                       if (node2->init < node->init)
1355                         node2->init = node->init;
1356                       break;
1357                     }
1358                 }
1359               if (node || node2)
1360                 dst = unshare_variable (set, dst, VAR_INIT_STATUS_UNKNOWN);
1361             }
1362
1363           src_l = 0;
1364           for (node = src->var_part[i].loc_chain; node; node = node->next)
1365             src_l++;
1366           dst_l = 0;
1367           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1368             dst_l++;
1369           vui = XCNEWVEC (struct variable_union_info, src_l + dst_l);
1370
1371           /* Fill in the locations from DST.  */
1372           for (node = dst->var_part[j].loc_chain, jj = 0; node;
1373                node = node->next, jj++)
1374             {
1375               vui[jj].lc = node;
1376               vui[jj].pos_dst = jj;
1377
1378               /* Value larger than a sum of 2 valid positions.  */
1379               vui[jj].pos_src = src_l + dst_l;
1380             }
1381
1382           /* Fill in the locations from SRC.  */
1383           n = dst_l;
1384           for (node = src->var_part[i].loc_chain, ii = 0; node;
1385                node = node->next, ii++)
1386             {
1387               /* Find location from NODE.  */
1388               for (jj = 0; jj < dst_l; jj++)
1389                 {
1390                   if ((REG_P (vui[jj].lc->loc)
1391                        && REG_P (node->loc)
1392                        && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
1393                       || rtx_equal_p (vui[jj].lc->loc, node->loc))
1394                     {
1395                       vui[jj].pos_src = ii;
1396                       break;
1397                     }
1398                 }
1399               if (jj >= dst_l)  /* The location has not been found.  */
1400                 {
1401                   location_chain new_node;
1402
1403                   /* Copy the location from SRC.  */
1404                   new_node = (location_chain) pool_alloc (loc_chain_pool);
1405                   new_node->loc = node->loc;
1406                   new_node->init = node->init;
1407                   if (!node->set_src || MEM_P (node->set_src))
1408                     new_node->set_src = NULL;
1409                   else
1410                     new_node->set_src = node->set_src;
1411                   vui[n].lc = new_node;
1412                   vui[n].pos_src = ii;
1413                   vui[n].pos_dst = src_l + dst_l;
1414                   n++;
1415                 }
1416             }
1417
1418           for (ii = 0; ii < src_l + dst_l; ii++)
1419             vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst;
1420
1421           qsort (vui, n, sizeof (struct variable_union_info),
1422                  variable_union_info_cmp_pos);
1423
1424           /* Reconnect the nodes in sorted order.  */
1425           for (ii = 1; ii < n; ii++)
1426             vui[ii - 1].lc->next = vui[ii].lc;
1427           vui[n - 1].lc->next = NULL;
1428
1429           dst->var_part[k].loc_chain = vui[0].lc;
1430           dst->var_part[k].offset = dst->var_part[j].offset;
1431
1432           free (vui);
1433           i--;
1434           j--;
1435         }
1436       else if ((i >= 0 && j >= 0
1437                 && src->var_part[i].offset < dst->var_part[j].offset)
1438                || i < 0)
1439         {
1440           dst->var_part[k] = dst->var_part[j];
1441           j--;
1442         }
1443       else if ((i >= 0 && j >= 0
1444                 && src->var_part[i].offset > dst->var_part[j].offset)
1445                || j < 0)
1446         {
1447           location_chain *nextp;
1448
1449           /* Copy the chain from SRC.  */
1450           nextp = &dst->var_part[k].loc_chain;
1451           for (node = src->var_part[i].loc_chain; node; node = node->next)
1452             {
1453               location_chain new_lc;
1454
1455               new_lc = (location_chain) pool_alloc (loc_chain_pool);
1456               new_lc->next = NULL;
1457               new_lc->init = node->init;
1458               if (!node->set_src || MEM_P (node->set_src))
1459                 new_lc->set_src = NULL;
1460               else
1461                 new_lc->set_src = node->set_src;
1462               new_lc->loc = node->loc;
1463
1464               *nextp = new_lc;
1465               nextp = &new_lc->next;
1466             }
1467
1468           dst->var_part[k].offset = src->var_part[i].offset;
1469           i--;
1470         }
1471
1472       /* We are at the basic block boundary when computing union
1473          so set the CUR_LOC to be the first element of the chain.  */
1474       if (dst->var_part[k].loc_chain)
1475         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
1476       else
1477         dst->var_part[k].cur_loc = NULL;
1478     }
1479
1480   for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++)
1481     {
1482       location_chain node, node2;
1483       for (node = src->var_part[i].loc_chain; node; node = node->next)
1484         for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next)
1485           if (rtx_equal_p (node->loc, node2->loc))
1486             {
1487               if (node->init > node2->init)
1488                 node2->init = node->init;
1489             }
1490     }
1491
1492   /* Continue traversing the hash table.  */
1493   return 1;
1494 }
1495
1496 /* Like variable_union, but only used when doing dataflow_set_union
1497    into an empty hashtab.  To allow sharing, dst is initially shared
1498    with src (so all variables are "copied" from src to dst hashtab),
1499    so only unshare_variable for variables that need canonicalization
1500    are needed.  */
1501
1502 static int
1503 variable_canonicalize (void **slot, void *data)
1504 {
1505   variable src;
1506   dataflow_set *set = (dataflow_set *) data;
1507   int k;
1508
1509   src = *(variable *) slot;
1510
1511   /* If CUR_LOC of some variable part is not the first element of
1512      the location chain we are going to change it so we have to make
1513      a copy of the variable.  */
1514   for (k = 0; k < src->n_var_parts; k++)
1515     {
1516       gcc_assert (!src->var_part[k].loc_chain == !src->var_part[k].cur_loc);
1517       if (src->var_part[k].loc_chain)
1518         {
1519           gcc_assert (src->var_part[k].cur_loc);
1520           if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
1521             break;
1522         }
1523     }
1524   if (k < src->n_var_parts)
1525     {
1526       enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
1527
1528       if (! flag_var_tracking_uninit)
1529         status = VAR_INIT_STATUS_INITIALIZED;
1530
1531       unshare_variable (set, src, status);
1532     }
1533   return 1;
1534 }
1535
1536 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
1537
1538 static void
1539 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
1540 {
1541   int i;
1542
1543   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1544     attrs_list_union (&dst->regs[i], src->regs[i]);
1545
1546   if (dst->vars == empty_shared_hash)
1547     {
1548       shared_hash_destroy (dst->vars);
1549       dst->vars = shared_hash_copy (src->vars);
1550       htab_traverse (shared_hash_htab (src->vars), variable_canonicalize, dst);
1551     }
1552   else
1553     htab_traverse (shared_hash_htab (src->vars), variable_union, dst);
1554 }
1555
1556 /* Flag whether two dataflow sets being compared contain different data.  */
1557 static bool
1558 dataflow_set_different_value;
1559
1560 static bool
1561 variable_part_different_p (variable_part *vp1, variable_part *vp2)
1562 {
1563   location_chain lc1, lc2;
1564
1565   for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
1566     {
1567       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
1568         {
1569           if (REG_P (lc1->loc) && REG_P (lc2->loc))
1570             {
1571               if (REGNO (lc1->loc) == REGNO (lc2->loc))
1572                 break;
1573             }
1574           if (rtx_equal_p (lc1->loc, lc2->loc))
1575             break;
1576         }
1577       if (!lc2)
1578         return true;
1579     }
1580   return false;
1581 }
1582
1583 /* Return true if variables VAR1 and VAR2 are different.
1584    If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
1585    variable part.  */
1586
1587 static bool
1588 variable_different_p (variable var1, variable var2,
1589                       bool compare_current_location)
1590 {
1591   int i;
1592
1593   if (var1 == var2)
1594     return false;
1595
1596   if (var1->n_var_parts != var2->n_var_parts)
1597     return true;
1598
1599   for (i = 0; i < var1->n_var_parts; i++)
1600     {
1601       if (var1->var_part[i].offset != var2->var_part[i].offset)
1602         return true;
1603       if (compare_current_location)
1604         {
1605           if (!((REG_P (var1->var_part[i].cur_loc)
1606                  && REG_P (var2->var_part[i].cur_loc)
1607                  && (REGNO (var1->var_part[i].cur_loc)
1608                      == REGNO (var2->var_part[i].cur_loc)))
1609                 || rtx_equal_p (var1->var_part[i].cur_loc,
1610                                 var2->var_part[i].cur_loc)))
1611             return true;
1612         }
1613       if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
1614         return true;
1615       if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
1616         return true;
1617     }
1618   return false;
1619 }
1620
1621 /* Compare variable *SLOT with the same variable in hash table DATA
1622    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1623
1624 static int
1625 dataflow_set_different_1 (void **slot, void *data)
1626 {
1627   htab_t htab = (htab_t) data;
1628   variable var1, var2;
1629
1630   var1 = *(variable *) slot;
1631   var2 = (variable) htab_find_with_hash (htab, var1->decl,
1632                               VARIABLE_HASH_VAL (var1->decl));
1633   if (!var2)
1634     {
1635       dataflow_set_different_value = true;
1636
1637       /* Stop traversing the hash table.  */
1638       return 0;
1639     }
1640
1641   if (variable_different_p (var1, var2, false))
1642     {
1643       dataflow_set_different_value = true;
1644
1645       /* Stop traversing the hash table.  */
1646       return 0;
1647     }
1648
1649   /* Continue traversing the hash table.  */
1650   return 1;
1651 }
1652
1653 /* Compare variable *SLOT with the same variable in hash table DATA
1654    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1655
1656 static int
1657 dataflow_set_different_2 (void **slot, void *data)
1658 {
1659   htab_t htab = (htab_t) data;
1660   variable var1, var2;
1661
1662   var1 = *(variable *) slot;
1663   var2 = (variable) htab_find_with_hash (htab, var1->decl,
1664                               VARIABLE_HASH_VAL (var1->decl));
1665   if (!var2)
1666     {
1667       dataflow_set_different_value = true;
1668
1669       /* Stop traversing the hash table.  */
1670       return 0;
1671     }
1672
1673   /* If both variables are defined they have been already checked for
1674      equivalence.  */
1675   gcc_assert (!variable_different_p (var1, var2, false));
1676
1677   /* Continue traversing the hash table.  */
1678   return 1;
1679 }
1680
1681 /* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
1682
1683 static bool
1684 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
1685 {
1686   if (old_set->vars == new_set->vars)
1687     return false;
1688
1689   if (htab_elements (shared_hash_htab (old_set->vars))
1690       != htab_elements (shared_hash_htab (new_set->vars)))
1691     return true;
1692
1693   dataflow_set_different_value = false;
1694
1695   htab_traverse (shared_hash_htab (old_set->vars), dataflow_set_different_1,
1696                  shared_hash_htab (new_set->vars));
1697   if (!dataflow_set_different_value)
1698     {
1699       /* We have compared the variables which are in both hash tables
1700          so now only check whether there are some variables in NEW_SET->VARS
1701          which are not in OLD_SET->VARS.  */
1702       htab_traverse (shared_hash_htab (new_set->vars), dataflow_set_different_2,
1703                      shared_hash_htab (old_set->vars));
1704     }
1705   return dataflow_set_different_value;
1706 }
1707
1708 /* Free the contents of dataflow set SET.  */
1709
1710 static void
1711 dataflow_set_destroy (dataflow_set *set)
1712 {
1713   int i;
1714
1715   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1716     attrs_list_clear (&set->regs[i]);
1717
1718   shared_hash_destroy (set->vars);
1719   set->vars = NULL;
1720 }
1721
1722 /* Return true if RTL X contains a SYMBOL_REF.  */
1723
1724 static bool
1725 contains_symbol_ref (rtx x)
1726 {
1727   const char *fmt;
1728   RTX_CODE code;
1729   int i;
1730
1731   if (!x)
1732     return false;
1733
1734   code = GET_CODE (x);
1735   if (code == SYMBOL_REF)
1736     return true;
1737
1738   fmt = GET_RTX_FORMAT (code);
1739   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1740     {
1741       if (fmt[i] == 'e')
1742         {
1743           if (contains_symbol_ref (XEXP (x, i)))
1744             return true;
1745         }
1746       else if (fmt[i] == 'E')
1747         {
1748           int j;
1749           for (j = 0; j < XVECLEN (x, i); j++)
1750             if (contains_symbol_ref (XVECEXP (x, i, j)))
1751               return true;
1752         }
1753     }
1754
1755   return false;
1756 }
1757
1758 /* Shall EXPR be tracked?  */
1759
1760 static bool
1761 track_expr_p (tree expr)
1762 {
1763   rtx decl_rtl;
1764   tree realdecl;
1765
1766   /* If EXPR is not a parameter or a variable do not track it.  */
1767   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
1768     return 0;
1769
1770   /* It also must have a name...  */
1771   if (!DECL_NAME (expr))
1772     return 0;
1773
1774   /* ... and a RTL assigned to it.  */
1775   decl_rtl = DECL_RTL_IF_SET (expr);
1776   if (!decl_rtl)
1777     return 0;
1778
1779   /* If this expression is really a debug alias of some other declaration, we
1780      don't need to track this expression if the ultimate declaration is
1781      ignored.  */
1782   realdecl = expr;
1783   if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
1784     {
1785       realdecl = DECL_DEBUG_EXPR (realdecl);
1786       /* ??? We don't yet know how to emit DW_OP_piece for variable
1787          that has been SRA'ed.  */
1788       if (!DECL_P (realdecl))
1789         return 0;
1790     }
1791
1792   /* Do not track EXPR if REALDECL it should be ignored for debugging
1793      purposes.  */
1794   if (DECL_IGNORED_P (realdecl))
1795     return 0;
1796
1797   /* Do not track global variables until we are able to emit correct location
1798      list for them.  */
1799   if (TREE_STATIC (realdecl))
1800     return 0;
1801
1802   /* When the EXPR is a DECL for alias of some variable (see example)
1803      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
1804      DECL_RTL contains SYMBOL_REF.
1805
1806      Example:
1807      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
1808      char **_dl_argv;
1809   */
1810   if (MEM_P (decl_rtl)
1811       && contains_symbol_ref (XEXP (decl_rtl, 0)))
1812     return 0;
1813
1814   /* If RTX is a memory it should not be very large (because it would be
1815      an array or struct).  */
1816   if (MEM_P (decl_rtl))
1817     {
1818       /* Do not track structures and arrays.  */
1819       if (GET_MODE (decl_rtl) == BLKmode
1820           || AGGREGATE_TYPE_P (TREE_TYPE (realdecl)))
1821         return 0;
1822       if (MEM_SIZE (decl_rtl)
1823           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
1824         return 0;
1825     }
1826
1827   return 1;
1828 }
1829
1830 /* Determine whether a given LOC refers to the same variable part as
1831    EXPR+OFFSET.  */
1832
1833 static bool
1834 same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset)
1835 {
1836   tree expr2;
1837   HOST_WIDE_INT offset2;
1838
1839   if (! DECL_P (expr))
1840     return false;
1841
1842   if (REG_P (loc))
1843     {
1844       expr2 = REG_EXPR (loc);
1845       offset2 = REG_OFFSET (loc);
1846     }
1847   else if (MEM_P (loc))
1848     {
1849       expr2 = MEM_EXPR (loc);
1850       offset2 = INT_MEM_OFFSET (loc);
1851     }
1852   else
1853     return false;
1854
1855   if (! expr2 || ! DECL_P (expr2))
1856     return false;
1857
1858   expr = var_debug_decl (expr);
1859   expr2 = var_debug_decl (expr2);
1860
1861   return (expr == expr2 && offset == offset2);
1862 }
1863
1864 /* LOC is a REG or MEM that we would like to track if possible.
1865    If EXPR is null, we don't know what expression LOC refers to,
1866    otherwise it refers to EXPR + OFFSET.  STORE_REG_P is true if
1867    LOC is an lvalue register.
1868
1869    Return true if EXPR is nonnull and if LOC, or some lowpart of it,
1870    is something we can track.  When returning true, store the mode of
1871    the lowpart we can track in *MODE_OUT (if nonnull) and its offset
1872    from EXPR in *OFFSET_OUT (if nonnull).  */
1873
1874 static bool
1875 track_loc_p (rtx loc, tree expr, HOST_WIDE_INT offset, bool store_reg_p,
1876              enum machine_mode *mode_out, HOST_WIDE_INT *offset_out)
1877 {
1878   enum machine_mode mode;
1879
1880   if (expr == NULL || !track_expr_p (expr))
1881     return false;
1882
1883   /* If REG was a paradoxical subreg, its REG_ATTRS will describe the
1884      whole subreg, but only the old inner part is really relevant.  */
1885   mode = GET_MODE (loc);
1886   if (REG_P (loc) && !HARD_REGISTER_NUM_P (ORIGINAL_REGNO (loc)))
1887     {
1888       enum machine_mode pseudo_mode;
1889
1890       pseudo_mode = PSEUDO_REGNO_MODE (ORIGINAL_REGNO (loc));
1891       if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (pseudo_mode))
1892         {
1893           offset += byte_lowpart_offset (pseudo_mode, mode);
1894           mode = pseudo_mode;
1895         }
1896     }
1897
1898   /* If LOC is a paradoxical lowpart of EXPR, refer to EXPR itself.
1899      Do the same if we are storing to a register and EXPR occupies
1900      the whole of register LOC; in that case, the whole of EXPR is
1901      being changed.  We exclude complex modes from the second case
1902      because the real and imaginary parts are represented as separate
1903      pseudo registers, even if the whole complex value fits into one
1904      hard register.  */
1905   if ((GET_MODE_SIZE (mode) > GET_MODE_SIZE (DECL_MODE (expr))
1906        || (store_reg_p
1907            && !COMPLEX_MODE_P (DECL_MODE (expr))
1908            && hard_regno_nregs[REGNO (loc)][DECL_MODE (expr)] == 1))
1909       && offset + byte_lowpart_offset (DECL_MODE (expr), mode) == 0)
1910     {
1911       mode = DECL_MODE (expr);
1912       offset = 0;
1913     }
1914
1915   if (offset < 0 || offset >= MAX_VAR_PARTS)
1916     return false;
1917
1918   if (mode_out)
1919     *mode_out = mode;
1920   if (offset_out)
1921     *offset_out = offset;
1922   return true;
1923 }
1924
1925 /* Return the MODE lowpart of LOC, or null if LOC is not something we
1926    want to track.  When returning nonnull, make sure that the attributes
1927    on the returned value are updated.  */
1928
1929 static rtx
1930 var_lowpart (enum machine_mode mode, rtx loc)
1931 {
1932   unsigned int offset, reg_offset, regno;
1933
1934   if (!REG_P (loc) && !MEM_P (loc))
1935     return NULL;
1936
1937   if (GET_MODE (loc) == mode)
1938     return loc;
1939
1940   offset = byte_lowpart_offset (mode, GET_MODE (loc));
1941
1942   if (MEM_P (loc))
1943     return adjust_address_nv (loc, mode, offset);
1944
1945   reg_offset = subreg_lowpart_offset (mode, GET_MODE (loc));
1946   regno = REGNO (loc) + subreg_regno_offset (REGNO (loc), GET_MODE (loc),
1947                                              reg_offset, mode);
1948   return gen_rtx_REG_offset (loc, mode, regno, offset);
1949 }
1950
1951 /* Count uses (register and memory references) LOC which will be tracked.
1952    INSN is instruction which the LOC is part of.  */
1953
1954 static int
1955 count_uses (rtx *loc, void *insn)
1956 {
1957   basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1958
1959   if (REG_P (*loc))
1960     {
1961       gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER);
1962       VTI (bb)->n_mos++;
1963     }
1964   else if (MEM_P (*loc)
1965            && track_loc_p (*loc, MEM_EXPR (*loc), INT_MEM_OFFSET (*loc),
1966                            false, NULL, NULL))
1967     {
1968       VTI (bb)->n_mos++;
1969     }
1970
1971   return 0;
1972 }
1973
1974 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1975
1976 static void
1977 count_uses_1 (rtx *x, void *insn)
1978 {
1979   for_each_rtx (x, count_uses, insn);
1980 }
1981
1982 /* Count stores (register and memory references) LOC which will be tracked.
1983    INSN is instruction which the LOC is part of.  */
1984
1985 static void
1986 count_stores (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *insn)
1987 {
1988   count_uses (&loc, insn);
1989 }
1990
1991 /* Add uses (register and memory references) LOC which will be tracked
1992    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
1993
1994 static int
1995 add_uses (rtx *loc, void *insn)
1996 {
1997   enum machine_mode mode;
1998
1999   if (REG_P (*loc))
2000     {
2001       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
2002       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2003
2004       if (track_loc_p (*loc, REG_EXPR (*loc), REG_OFFSET (*loc),
2005                        false, &mode, NULL))
2006         {
2007           mo->type = MO_USE;
2008           mo->u.loc = var_lowpart (mode, *loc);
2009         }
2010       else
2011         {
2012           mo->type = MO_USE_NO_VAR;
2013           mo->u.loc = *loc;
2014         }
2015       mo->insn = (rtx) insn;
2016     }
2017   else if (MEM_P (*loc)
2018            && track_loc_p (*loc, MEM_EXPR (*loc), INT_MEM_OFFSET (*loc),
2019                            false, &mode, NULL))
2020     {
2021       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
2022       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2023
2024       mo->type = MO_USE;
2025       mo->u.loc = var_lowpart (mode, *loc);
2026       mo->insn = (rtx) insn;
2027     }
2028
2029   return 0;
2030 }
2031
2032 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
2033
2034 static void
2035 add_uses_1 (rtx *x, void *insn)
2036 {
2037   for_each_rtx (x, add_uses, insn);
2038 }
2039
2040 /* Add stores (register and memory references) LOC which will be tracked
2041    to VTI (bb)->mos. EXPR is the RTL expression containing the store.
2042    INSN is instruction which the LOC is part of.  */
2043
2044 static void
2045 add_stores (rtx loc, const_rtx expr, void *insn)
2046 {
2047   enum machine_mode mode;
2048
2049   if (REG_P (loc))
2050     {
2051       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
2052       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2053
2054       if (GET_CODE (expr) == CLOBBER
2055           || !track_loc_p (loc, REG_EXPR (loc), REG_OFFSET (loc),
2056                            true, &mode, NULL))
2057         {
2058           mo->type = MO_CLOBBER;
2059           mo->u.loc = loc;
2060         }
2061       else
2062         {
2063           rtx src = NULL;
2064
2065           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
2066             src = var_lowpart (mode, SET_SRC (expr));
2067           loc = var_lowpart (mode, loc);
2068
2069           if (src == NULL)
2070             {
2071               mo->type = MO_SET;
2072               mo->u.loc = loc;
2073             }
2074           else
2075             {
2076               if (SET_SRC (expr) != src)
2077                 expr = gen_rtx_SET (VOIDmode, loc, src);
2078               if (same_variable_part_p (src, REG_EXPR (loc), REG_OFFSET (loc)))
2079                 mo->type = MO_COPY;
2080               else
2081                 mo->type = MO_SET;
2082               mo->u.loc = CONST_CAST_RTX (expr);
2083             }
2084         }
2085       mo->insn = (rtx) insn;
2086     }
2087   else if (MEM_P (loc)
2088            && track_loc_p (loc, MEM_EXPR (loc), INT_MEM_OFFSET (loc),
2089                            false, &mode, NULL))
2090     {
2091       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
2092       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2093
2094       if (GET_CODE (expr) == CLOBBER)
2095         {
2096           mo->type = MO_CLOBBER;
2097           mo->u.loc = var_lowpart (mode, loc);
2098         }
2099       else
2100         {
2101           rtx src = NULL;
2102
2103           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
2104             src = var_lowpart (mode, SET_SRC (expr));
2105           loc = var_lowpart (mode, loc);
2106
2107           if (src == NULL)
2108             {
2109               mo->type = MO_SET;
2110               mo->u.loc = loc;
2111             }
2112           else
2113             {
2114               if (SET_SRC (expr) != src)
2115                 expr = gen_rtx_SET (VOIDmode, loc, src);
2116               if (same_variable_part_p (SET_SRC (expr),
2117                                         MEM_EXPR (loc),
2118                                         INT_MEM_OFFSET (loc)))
2119                 mo->type = MO_COPY;
2120               else
2121                 mo->type = MO_SET;
2122               mo->u.loc = CONST_CAST_RTX (expr);
2123             }
2124         }
2125       mo->insn = (rtx) insn;
2126     }
2127 }
2128
2129 static enum var_init_status
2130 find_src_status (dataflow_set *in, rtx src)
2131 {
2132   tree decl = NULL_TREE;
2133   enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
2134
2135   if (! flag_var_tracking_uninit)
2136     status = VAR_INIT_STATUS_INITIALIZED;
2137
2138   if (src && REG_P (src))
2139     decl = var_debug_decl (REG_EXPR (src));
2140   else if (src && MEM_P (src))
2141     decl = var_debug_decl (MEM_EXPR (src));
2142
2143   if (src && decl)
2144     status = get_init_value (in, src, decl);
2145
2146   return status;
2147 }
2148
2149 /* SRC is the source of an assignment.  Use SET to try to find what
2150    was ultimately assigned to SRC.  Return that value if known,
2151    otherwise return SRC itself.  */
2152
2153 static rtx
2154 find_src_set_src (dataflow_set *set, rtx src)
2155 {
2156   tree decl = NULL_TREE;   /* The variable being copied around.          */
2157   rtx set_src = NULL_RTX;  /* The value for "decl" stored in "src".      */
2158   variable var;
2159   location_chain nextp;
2160   int i;
2161   bool found;
2162
2163   if (src && REG_P (src))
2164     decl = var_debug_decl (REG_EXPR (src));
2165   else if (src && MEM_P (src))
2166     decl = var_debug_decl (MEM_EXPR (src));
2167
2168   if (src && decl)
2169     {
2170       var = shared_hash_find (set->vars, decl);
2171       if (var)
2172         {
2173           found = false;
2174           for (i = 0; i < var->n_var_parts && !found; i++)
2175             for (nextp = var->var_part[i].loc_chain; nextp && !found;
2176                  nextp = nextp->next)
2177               if (rtx_equal_p (nextp->loc, src))
2178                 {
2179                   set_src = nextp->set_src;
2180                   found = true;
2181                 }
2182
2183         }
2184     }
2185
2186   return set_src;
2187 }
2188
2189 /* Compute the changes of variable locations in the basic block BB.  */
2190
2191 static bool
2192 compute_bb_dataflow (basic_block bb)
2193 {
2194   int i, n, r;
2195   bool changed;
2196   dataflow_set old_out;
2197   dataflow_set *in = &VTI (bb)->in;
2198   dataflow_set *out = &VTI (bb)->out;
2199
2200   dataflow_set_init (&old_out);
2201   dataflow_set_copy (&old_out, out);
2202   dataflow_set_copy (out, in);
2203
2204   n = VTI (bb)->n_mos;
2205   for (i = 0; i < n; i++)
2206     {
2207       switch (VTI (bb)->mos[i].type)
2208         {
2209           case MO_CALL:
2210             for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2211               if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2212                 var_regno_delete (out, r);
2213             break;
2214
2215           case MO_USE:
2216             {
2217               rtx loc = VTI (bb)->mos[i].u.loc;
2218               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
2219
2220               if (! flag_var_tracking_uninit)
2221                 status = VAR_INIT_STATUS_INITIALIZED;
2222
2223               if (GET_CODE (loc) == REG)
2224                 var_reg_set (out, loc, status, NULL);
2225               else if (GET_CODE (loc) == MEM)
2226                 var_mem_set (out, loc, status, NULL);
2227             }
2228             break;
2229
2230           case MO_SET:
2231             {
2232               rtx loc = VTI (bb)->mos[i].u.loc;
2233               rtx set_src = NULL;
2234
2235               if (GET_CODE (loc) == SET)
2236                 {
2237                   set_src = SET_SRC (loc);
2238                   loc = SET_DEST (loc);
2239                 }
2240
2241               if (REG_P (loc))
2242                 var_reg_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
2243                                         set_src);
2244               else if (MEM_P (loc))
2245                 var_mem_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
2246                                         set_src);
2247             }
2248             break;
2249
2250           case MO_COPY:
2251             {
2252               rtx loc = VTI (bb)->mos[i].u.loc;
2253               enum var_init_status src_status;
2254               rtx set_src = NULL;
2255
2256               if (GET_CODE (loc) == SET)
2257                 {
2258                   set_src = SET_SRC (loc);
2259                   loc = SET_DEST (loc);
2260                 }
2261
2262               if (! flag_var_tracking_uninit)
2263                 src_status = VAR_INIT_STATUS_INITIALIZED;
2264               else
2265                 src_status = find_src_status (in, set_src);
2266
2267               if (src_status == VAR_INIT_STATUS_UNKNOWN)
2268                 src_status = find_src_status (out, set_src);
2269
2270               set_src = find_src_set_src (in, set_src);
2271
2272               if (REG_P (loc))
2273                 var_reg_delete_and_set (out, loc, false, src_status, set_src);
2274               else if (MEM_P (loc))
2275                 var_mem_delete_and_set (out, loc, false, src_status, set_src);
2276             }
2277             break;
2278
2279           case MO_USE_NO_VAR:
2280             {
2281               rtx loc = VTI (bb)->mos[i].u.loc;
2282
2283               if (REG_P (loc))
2284                 var_reg_delete (out, loc, false);
2285               else if (MEM_P (loc))
2286                 var_mem_delete (out, loc, false);
2287             }
2288             break;
2289
2290           case MO_CLOBBER:
2291             {
2292               rtx loc = VTI (bb)->mos[i].u.loc;
2293
2294               if (REG_P (loc))
2295                 var_reg_delete (out, loc, true);
2296               else if (MEM_P (loc))
2297                 var_mem_delete (out, loc, true);
2298             }
2299             break;
2300
2301           case MO_ADJUST:
2302             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
2303             break;
2304         }
2305     }
2306
2307   changed = dataflow_set_different (&old_out, out);
2308   dataflow_set_destroy (&old_out);
2309   return changed;
2310 }
2311
2312 /* Find the locations of variables in the whole function.  */
2313
2314 static void
2315 vt_find_locations (void)
2316 {
2317   fibheap_t worklist, pending, fibheap_swap;
2318   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
2319   basic_block bb;
2320   edge e;
2321   int *bb_order;
2322   int *rc_order;
2323   int i;
2324
2325   /* Compute reverse completion order of depth first search of the CFG
2326      so that the data-flow runs faster.  */
2327   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
2328   bb_order = XNEWVEC (int, last_basic_block);
2329   pre_and_rev_post_order_compute (NULL, rc_order, false);
2330   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2331     bb_order[rc_order[i]] = i;
2332   free (rc_order);
2333
2334   worklist = fibheap_new ();
2335   pending = fibheap_new ();
2336   visited = sbitmap_alloc (last_basic_block);
2337   in_worklist = sbitmap_alloc (last_basic_block);
2338   in_pending = sbitmap_alloc (last_basic_block);
2339   sbitmap_zero (in_worklist);
2340
2341   FOR_EACH_BB (bb)
2342     fibheap_insert (pending, bb_order[bb->index], bb);
2343   sbitmap_ones (in_pending);
2344
2345   while (!fibheap_empty (pending))
2346     {
2347       fibheap_swap = pending;
2348       pending = worklist;
2349       worklist = fibheap_swap;
2350       sbitmap_swap = in_pending;
2351       in_pending = in_worklist;
2352       in_worklist = sbitmap_swap;
2353
2354       sbitmap_zero (visited);
2355
2356       while (!fibheap_empty (worklist))
2357         {
2358           bb = (basic_block) fibheap_extract_min (worklist);
2359           RESET_BIT (in_worklist, bb->index);
2360           if (!TEST_BIT (visited, bb->index))
2361             {
2362               bool changed;
2363               edge_iterator ei;
2364
2365               SET_BIT (visited, bb->index);
2366
2367               /* Calculate the IN set as union of predecessor OUT sets.  */
2368               dataflow_set_clear (&VTI (bb)->in);
2369               FOR_EACH_EDGE (e, ei, bb->preds)
2370                 {
2371                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
2372                 }
2373
2374               changed = compute_bb_dataflow (bb);
2375               if (changed)
2376                 {
2377                   FOR_EACH_EDGE (e, ei, bb->succs)
2378                     {
2379                       if (e->dest == EXIT_BLOCK_PTR)
2380                         continue;
2381
2382                       if (e->dest == bb)
2383                         continue;
2384
2385                       if (TEST_BIT (visited, e->dest->index))
2386                         {
2387                           if (!TEST_BIT (in_pending, e->dest->index))
2388                             {
2389                               /* Send E->DEST to next round.  */
2390                               SET_BIT (in_pending, e->dest->index);
2391                               fibheap_insert (pending,
2392                                               bb_order[e->dest->index],
2393                                               e->dest);
2394                             }
2395                         }
2396                       else if (!TEST_BIT (in_worklist, e->dest->index))
2397                         {
2398                           /* Add E->DEST to current round.  */
2399                           SET_BIT (in_worklist, e->dest->index);
2400                           fibheap_insert (worklist, bb_order[e->dest->index],
2401                                           e->dest);
2402                         }
2403                     }
2404                 }
2405             }
2406         }
2407     }
2408
2409   free (bb_order);
2410   fibheap_delete (worklist);
2411   fibheap_delete (pending);
2412   sbitmap_free (visited);
2413   sbitmap_free (in_worklist);
2414   sbitmap_free (in_pending);
2415 }
2416
2417 /* Print the content of the LIST to dump file.  */
2418
2419 static void
2420 dump_attrs_list (attrs list)
2421 {
2422   for (; list; list = list->next)
2423     {
2424       print_mem_expr (dump_file, list->decl);
2425       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
2426     }
2427   fprintf (dump_file, "\n");
2428 }
2429
2430 /* Print the information about variable *SLOT to dump file.  */
2431
2432 static int
2433 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
2434 {
2435   variable var = *(variable *) slot;
2436   int i;
2437   location_chain node;
2438
2439   fprintf (dump_file, "  name: %s",
2440            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
2441   if (dump_flags & TDF_UID)
2442     fprintf (dump_file, " D.%u\n", DECL_UID (var->decl));
2443   else
2444     fprintf (dump_file, "\n");
2445
2446   for (i = 0; i < var->n_var_parts; i++)
2447     {
2448       fprintf (dump_file, "    offset %ld\n",
2449                (long) var->var_part[i].offset);
2450       for (node = var->var_part[i].loc_chain; node; node = node->next)
2451         {
2452           fprintf (dump_file, "      ");
2453           if (node->init == VAR_INIT_STATUS_UNINITIALIZED)
2454             fprintf (dump_file, "[uninit]");
2455           print_rtl_single (dump_file, node->loc);
2456         }
2457     }
2458
2459   /* Continue traversing the hash table.  */
2460   return 1;
2461 }
2462
2463 /* Print the information about variables from hash table VARS to dump file.  */
2464
2465 static void
2466 dump_vars (htab_t vars)
2467 {
2468   if (htab_elements (vars) > 0)
2469     {
2470       fprintf (dump_file, "Variables:\n");
2471       htab_traverse (vars, dump_variable, NULL);
2472     }
2473 }
2474
2475 /* Print the dataflow set SET to dump file.  */
2476
2477 static void
2478 dump_dataflow_set (dataflow_set *set)
2479 {
2480   int i;
2481
2482   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
2483            set->stack_adjust);
2484   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2485     {
2486       if (set->regs[i])
2487         {
2488           fprintf (dump_file, "Reg %d:", i);
2489           dump_attrs_list (set->regs[i]);
2490         }
2491     }
2492   dump_vars (shared_hash_htab (set->vars));
2493   fprintf (dump_file, "\n");
2494 }
2495
2496 /* Print the IN and OUT sets for each basic block to dump file.  */
2497
2498 static void
2499 dump_dataflow_sets (void)
2500 {
2501   basic_block bb;
2502
2503   FOR_EACH_BB (bb)
2504     {
2505       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
2506       fprintf (dump_file, "IN:\n");
2507       dump_dataflow_set (&VTI (bb)->in);
2508       fprintf (dump_file, "OUT:\n");
2509       dump_dataflow_set (&VTI (bb)->out);
2510     }
2511 }
2512
2513 /* Add variable VAR to the hash table of changed variables and
2514    if it has no locations delete it from SET's hash table.  */
2515
2516 static void
2517 variable_was_changed (variable var, dataflow_set *set)
2518 {
2519   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
2520
2521   if (emit_notes)
2522     {
2523       variable *slot;
2524
2525       slot = (variable *) htab_find_slot_with_hash (changed_variables,
2526                                                     var->decl, hash, INSERT);
2527
2528       if (set && var->n_var_parts == 0)
2529         {
2530           variable empty_var;
2531
2532           empty_var = (variable) pool_alloc (var_pool);
2533           empty_var->decl = var->decl;
2534           empty_var->refcount = 1;
2535           empty_var->n_var_parts = 0;
2536           *slot = empty_var;
2537           goto drop_var;
2538         }
2539       else
2540         {
2541           var->refcount++;
2542           *slot = var;
2543         }
2544     }
2545   else
2546     {
2547       gcc_assert (set);
2548       if (var->n_var_parts == 0)
2549         {
2550           void **slot;
2551
2552         drop_var:
2553           slot = shared_hash_find_slot_noinsert (set->vars, var->decl);
2554           if (slot)
2555             {
2556               if (shared_hash_shared (set->vars))
2557                 slot = shared_hash_find_slot_unshare (&set->vars, var->decl,
2558                                                       NO_INSERT);
2559               htab_clear_slot (shared_hash_htab (set->vars), slot);
2560             }
2561         }
2562     }
2563 }
2564
2565 /* Look for the index in VAR->var_part corresponding to OFFSET.
2566    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
2567    referenced int will be set to the index that the part has or should
2568    have, if it should be inserted.  */
2569
2570 static inline int
2571 find_variable_location_part (variable var, HOST_WIDE_INT offset,
2572                              int *insertion_point)
2573 {
2574   int pos, low, high;
2575
2576   /* Find the location part.  */
2577   low = 0;
2578   high = var->n_var_parts;
2579   while (low != high)
2580     {
2581       pos = (low + high) / 2;
2582       if (var->var_part[pos].offset < offset)
2583         low = pos + 1;
2584       else
2585         high = pos;
2586     }
2587   pos = low;
2588
2589   if (insertion_point)
2590     *insertion_point = pos;
2591
2592   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2593     return pos;
2594
2595   return -1;
2596 }
2597
2598 /* Set the part of variable's location in the dataflow set SET.  The variable
2599    part is specified by variable's declaration DECL and offset OFFSET and the
2600    part's location by LOC.  */
2601
2602 static void
2603 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset,
2604                    enum var_init_status initialized, rtx set_src)
2605 {
2606   int pos;
2607   location_chain node, next;
2608   location_chain *nextp;
2609   variable var;
2610   void **slot = shared_hash_find_slot (set->vars, decl);
2611
2612   if (!slot || !*slot)
2613     {
2614       if (!slot)
2615         slot = shared_hash_find_slot_unshare (&set->vars, decl, INSERT);
2616       /* Create new variable information.  */
2617       var = (variable) pool_alloc (var_pool);
2618       var->decl = decl;
2619       var->refcount = 1;
2620       var->n_var_parts = 1;
2621       var->var_part[0].offset = offset;
2622       var->var_part[0].loc_chain = NULL;
2623       var->var_part[0].cur_loc = NULL;
2624       *slot = var;
2625       pos = 0;
2626     }
2627   else
2628     {
2629       int inspos = 0;
2630
2631       var = (variable) *slot;
2632
2633       pos = find_variable_location_part (var, offset, &inspos);
2634
2635       if (pos >= 0)
2636         {
2637           node = var->var_part[pos].loc_chain;
2638
2639           if (node
2640               && ((REG_P (node->loc) && REG_P (loc)
2641                    && REGNO (node->loc) == REGNO (loc))
2642                   || rtx_equal_p (node->loc, loc)))
2643             {
2644               /* LOC is in the beginning of the chain so we have nothing
2645                  to do.  */
2646               if (node->init < initialized)
2647                 node->init = initialized;
2648               if (set_src != NULL)
2649                 node->set_src = set_src;
2650
2651               return;
2652             }
2653           else
2654             {
2655               /* We have to make a copy of a shared variable.  */
2656               if (var->refcount > 1 || shared_hash_shared (set->vars))
2657                 var = unshare_variable (set, var, initialized);
2658             }
2659         }
2660       else
2661         {
2662           /* We have not found the location part, new one will be created.  */
2663
2664           /* We have to make a copy of the shared variable.  */
2665           if (var->refcount > 1 || shared_hash_shared (set->vars))
2666             var = unshare_variable (set, var, initialized);
2667
2668           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2669              thus there are at most MAX_VAR_PARTS different offsets.  */
2670           gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
2671
2672           /* We have to move the elements of array starting at index
2673              inspos to the next position.  */
2674           for (pos = var->n_var_parts; pos > inspos; pos--)
2675             var->var_part[pos] = var->var_part[pos - 1];
2676
2677           var->n_var_parts++;
2678           var->var_part[pos].offset = offset;
2679           var->var_part[pos].loc_chain = NULL;
2680           var->var_part[pos].cur_loc = NULL;
2681         }
2682     }
2683
2684   /* Delete the location from the list.  */
2685   nextp = &var->var_part[pos].loc_chain;
2686   for (node = var->var_part[pos].loc_chain; node; node = next)
2687     {
2688       next = node->next;
2689       if ((REG_P (node->loc) && REG_P (loc)
2690            && REGNO (node->loc) == REGNO (loc))
2691           || rtx_equal_p (node->loc, loc))
2692         {
2693           /* Save these values, to assign to the new node, before
2694              deleting this one.  */
2695           if (node->init > initialized)
2696             initialized = node->init;
2697           if (node->set_src != NULL && set_src == NULL)
2698             set_src = node->set_src;
2699           pool_free (loc_chain_pool, node);
2700           *nextp = next;
2701           break;
2702         }
2703       else
2704         nextp = &node->next;
2705     }
2706
2707   /* Add the location to the beginning.  */
2708   node = (location_chain) pool_alloc (loc_chain_pool);
2709   node->loc = loc;
2710   node->init = initialized;
2711   node->set_src = set_src;
2712   node->next = var->var_part[pos].loc_chain;
2713   var->var_part[pos].loc_chain = node;
2714
2715   /* If no location was emitted do so.  */
2716   if (var->var_part[pos].cur_loc == NULL)
2717     {
2718       var->var_part[pos].cur_loc = loc;
2719       variable_was_changed (var, set);
2720     }
2721 }
2722
2723 /* Remove all recorded register locations for the given variable part
2724    from dataflow set SET, except for those that are identical to loc.
2725    The variable part is specified by variable's declaration DECL and
2726    offset OFFSET.  */
2727
2728 static void
2729 clobber_variable_part (dataflow_set *set, rtx loc, tree decl,
2730                        HOST_WIDE_INT offset, rtx set_src)
2731 {
2732   variable var;
2733
2734   if (! decl || ! DECL_P (decl))
2735     return;
2736
2737   var = shared_hash_find (set->vars, decl);
2738   if (var)
2739     {
2740       int pos = find_variable_location_part (var, offset, NULL);
2741
2742       if (pos >= 0)
2743         {
2744           location_chain node, next;
2745
2746           /* Remove the register locations from the dataflow set.  */
2747           next = var->var_part[pos].loc_chain;
2748           for (node = next; node; node = next)
2749             {
2750               next = node->next;
2751               if (node->loc != loc
2752                   && (!flag_var_tracking_uninit
2753                       || !set_src
2754                       || MEM_P (set_src)
2755                       || !rtx_equal_p (set_src, node->set_src)))
2756                 {
2757                   if (REG_P (node->loc))
2758                     {
2759                       attrs anode, anext;
2760                       attrs *anextp;
2761
2762                       /* Remove the variable part from the register's
2763                          list, but preserve any other variable parts
2764                          that might be regarded as live in that same
2765                          register.  */
2766                       anextp = &set->regs[REGNO (node->loc)];
2767                       for (anode = *anextp; anode; anode = anext)
2768                         {
2769                           anext = anode->next;
2770                           if (anode->decl == decl
2771                               && anode->offset == offset)
2772                             {
2773                               pool_free (attrs_pool, anode);
2774                               *anextp = anext;
2775                             }
2776                           else
2777                             anextp = &anode->next;
2778                         }
2779                     }
2780
2781                   delete_variable_part (set, node->loc, decl, offset);
2782                 }
2783             }
2784         }
2785     }
2786 }
2787
2788 /* Delete the part of variable's location from dataflow set SET.  The variable
2789    part is specified by variable's declaration DECL and offset OFFSET and the
2790    part's location by LOC.  */
2791
2792 static void
2793 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2794                       HOST_WIDE_INT offset)
2795 {
2796   variable var = shared_hash_find (set->vars, decl);;
2797   if (var)
2798     {
2799       int pos = find_variable_location_part (var, offset, NULL);
2800
2801       if (pos >= 0)
2802         {
2803           location_chain node, next;
2804           location_chain *nextp;
2805           bool changed;
2806
2807           if (var->refcount > 1 || shared_hash_shared (set->vars))
2808             {
2809               /* If the variable contains the location part we have to
2810                  make a copy of the variable.  */
2811               for (node = var->var_part[pos].loc_chain; node;
2812                    node = node->next)
2813                 {
2814                   if ((REG_P (node->loc) && REG_P (loc)
2815                        && REGNO (node->loc) == REGNO (loc))
2816                       || rtx_equal_p (node->loc, loc))
2817                     {
2818                       enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
2819                       if (! flag_var_tracking_uninit)
2820                         status = VAR_INIT_STATUS_INITIALIZED;
2821                       var = unshare_variable (set, var, status);
2822                       break;
2823                     }
2824                 }
2825             }
2826
2827           /* Delete the location part.  */
2828           nextp = &var->var_part[pos].loc_chain;
2829           for (node = *nextp; node; node = next)
2830             {
2831               next = node->next;
2832               if ((REG_P (node->loc) && REG_P (loc)
2833                    && REGNO (node->loc) == REGNO (loc))
2834                   || rtx_equal_p (node->loc, loc))
2835                 {
2836                   pool_free (loc_chain_pool, node);
2837                   *nextp = next;
2838                   break;
2839                 }
2840               else
2841                 nextp = &node->next;
2842             }
2843
2844           /* If we have deleted the location which was last emitted
2845              we have to emit new location so add the variable to set
2846              of changed variables.  */
2847           if (var->var_part[pos].cur_loc
2848               && ((REG_P (loc)
2849                    && REG_P (var->var_part[pos].cur_loc)
2850                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2851                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2852             {
2853               changed = true;
2854               if (var->var_part[pos].loc_chain)
2855                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2856             }
2857           else
2858             changed = false;
2859
2860           if (var->var_part[pos].loc_chain == NULL)
2861             {
2862               var->n_var_parts--;
2863               while (pos < var->n_var_parts)
2864                 {
2865                   var->var_part[pos] = var->var_part[pos + 1];
2866                   pos++;
2867                 }
2868             }
2869           if (changed)
2870             variable_was_changed (var, set);
2871         }
2872     }
2873 }
2874
2875 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2876    additional parameters: WHERE specifies whether the note shall be emitted
2877    before of after instruction INSN.  */
2878
2879 static int
2880 emit_note_insn_var_location (void **varp, void *data)
2881 {
2882   variable var = *(variable *) varp;
2883   rtx insn = ((emit_note_data *)data)->insn;
2884   enum emit_note_where where = ((emit_note_data *)data)->where;
2885   rtx note;
2886   int i, j, n_var_parts;
2887   bool complete;
2888   enum var_init_status initialized = VAR_INIT_STATUS_UNINITIALIZED;
2889   HOST_WIDE_INT last_limit;
2890   tree type_size_unit;
2891   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2892   rtx loc[MAX_VAR_PARTS];
2893
2894   gcc_assert (var->decl);
2895
2896   if (! flag_var_tracking_uninit)
2897     initialized = VAR_INIT_STATUS_INITIALIZED;
2898
2899   complete = true;
2900   last_limit = 0;
2901   n_var_parts = 0;
2902   for (i = 0; i < var->n_var_parts; i++)
2903     {
2904       enum machine_mode mode, wider_mode;
2905
2906       if (last_limit < var->var_part[i].offset)
2907         {
2908           complete = false;
2909           break;
2910         }
2911       else if (last_limit > var->var_part[i].offset)
2912         continue;
2913       offsets[n_var_parts] = var->var_part[i].offset;
2914       loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2915       mode = GET_MODE (loc[n_var_parts]);
2916       initialized = var->var_part[i].loc_chain->init;
2917       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2918
2919       /* Attempt to merge adjacent registers or memory.  */
2920       wider_mode = GET_MODE_WIDER_MODE (mode);
2921       for (j = i + 1; j < var->n_var_parts; j++)
2922         if (last_limit <= var->var_part[j].offset)
2923           break;
2924       if (j < var->n_var_parts
2925           && wider_mode != VOIDmode
2926           && GET_CODE (loc[n_var_parts])
2927              == GET_CODE (var->var_part[j].loc_chain->loc)
2928           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2929           && last_limit == var->var_part[j].offset)
2930         {
2931           rtx new_loc = NULL;
2932           rtx loc2 = var->var_part[j].loc_chain->loc;
2933
2934           if (REG_P (loc[n_var_parts])
2935               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2936                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2937               && end_hard_regno (mode, REGNO (loc[n_var_parts]))
2938                  == REGNO (loc2))
2939             {
2940               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2941                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2942                                            mode, 0);
2943               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2944                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2945               if (new_loc)
2946                 {
2947                   if (!REG_P (new_loc)
2948                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2949                     new_loc = NULL;
2950                   else
2951                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2952                 }
2953             }
2954           else if (MEM_P (loc[n_var_parts])
2955                    && GET_CODE (XEXP (loc2, 0)) == PLUS
2956                    && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2957                    && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2958             {
2959               if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2960                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2961                                    XEXP (XEXP (loc2, 0), 0))
2962                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
2963                       == GET_MODE_SIZE (mode))
2964                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2965                       && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2966                          == CONST_INT
2967                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2968                                       XEXP (XEXP (loc2, 0), 0))
2969                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2970                          + GET_MODE_SIZE (mode)
2971                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2972                 new_loc = adjust_address_nv (loc[n_var_parts],
2973                                              wider_mode, 0);
2974             }
2975
2976           if (new_loc)
2977             {
2978               loc[n_var_parts] = new_loc;
2979               mode = wider_mode;
2980               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2981               i = j;
2982             }
2983         }
2984       ++n_var_parts;
2985     }
2986   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2987   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2988     complete = false;
2989
2990   if (where == EMIT_NOTE_AFTER_INSN)
2991     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2992   else
2993     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2994
2995   if (! flag_var_tracking_uninit)
2996     initialized = VAR_INIT_STATUS_INITIALIZED;
2997
2998   if (!complete)
2999     {
3000       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
3001                                                        NULL_RTX, (int) initialized);
3002     }
3003   else if (n_var_parts == 1)
3004     {
3005       rtx expr_list
3006         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
3007
3008       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
3009                                                        expr_list,
3010                                                        (int) initialized);
3011     }
3012   else if (n_var_parts)
3013     {
3014       rtx parallel;
3015
3016       for (i = 0; i < n_var_parts; i++)
3017         loc[i]
3018           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
3019
3020       parallel = gen_rtx_PARALLEL (VOIDmode,
3021                                    gen_rtvec_v (n_var_parts, loc));
3022       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
3023                                                        parallel,
3024                                                        (int) initialized);
3025     }
3026
3027   htab_clear_slot (changed_variables, varp);
3028
3029   /* Continue traversing the hash table.  */
3030   return 1;
3031 }
3032
3033 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
3034    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
3035    shall be emitted before of after instruction INSN.  */
3036
3037 static void
3038 emit_notes_for_changes (rtx insn, enum emit_note_where where)
3039 {
3040   emit_note_data data;
3041
3042   data.insn = insn;
3043   data.where = where;
3044   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
3045 }
3046
3047 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
3048    same variable in hash table DATA or is not there at all.  */
3049
3050 static int
3051 emit_notes_for_differences_1 (void **slot, void *data)
3052 {
3053   htab_t new_vars = (htab_t) data;
3054   variable old_var, new_var;
3055
3056   old_var = *(variable *) slot;
3057   new_var = (variable) htab_find_with_hash (new_vars, old_var->decl,
3058                                  VARIABLE_HASH_VAL (old_var->decl));
3059
3060   if (!new_var)
3061     {
3062       /* Variable has disappeared.  */
3063       variable empty_var;
3064
3065       empty_var = (variable) pool_alloc (var_pool);
3066       empty_var->decl = old_var->decl;
3067       empty_var->refcount = 0;
3068       empty_var->n_var_parts = 0;
3069       variable_was_changed (empty_var, NULL);
3070     }
3071   else if (variable_different_p (old_var, new_var, true))
3072     {
3073       variable_was_changed (new_var, NULL);
3074     }
3075
3076   /* Continue traversing the hash table.  */
3077   return 1;
3078 }
3079
3080 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
3081    table DATA.  */
3082
3083 static int
3084 emit_notes_for_differences_2 (void **slot, void *data)
3085 {
3086   htab_t old_vars = (htab_t) data;
3087   variable old_var, new_var;
3088
3089   new_var = *(variable *) slot;
3090   old_var = (variable) htab_find_with_hash (old_vars, new_var->decl,
3091                                  VARIABLE_HASH_VAL (new_var->decl));
3092   if (!old_var)
3093     {
3094       /* Variable has appeared.  */
3095       variable_was_changed (new_var, NULL);
3096     }
3097
3098   /* Continue traversing the hash table.  */
3099   return 1;
3100 }
3101
3102 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
3103    NEW_SET.  */
3104
3105 static void
3106 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
3107                             dataflow_set *new_set)
3108 {
3109   htab_traverse (shared_hash_htab (old_set->vars),
3110                  emit_notes_for_differences_1,
3111                  shared_hash_htab (new_set->vars));
3112   htab_traverse (shared_hash_htab (new_set->vars),
3113                  emit_notes_for_differences_2,
3114                  shared_hash_htab (old_set->vars));
3115   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
3116 }
3117
3118 /* Emit the notes for changes of location parts in the basic block BB.  */
3119
3120 static void
3121 emit_notes_in_bb (basic_block bb)
3122 {
3123   int i;
3124   dataflow_set set;
3125
3126   dataflow_set_init (&set);
3127   dataflow_set_copy (&set, &VTI (bb)->in);
3128
3129   for (i = 0; i < VTI (bb)->n_mos; i++)
3130     {
3131       rtx insn = VTI (bb)->mos[i].insn;
3132
3133       switch (VTI (bb)->mos[i].type)
3134         {
3135           case MO_CALL:
3136             {
3137               int r;
3138
3139               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
3140                 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
3141                   {
3142                     var_regno_delete (&set, r);
3143                   }
3144               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
3145             }
3146             break;
3147
3148           case MO_USE:
3149             {
3150               rtx loc = VTI (bb)->mos[i].u.loc;
3151
3152               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
3153               if (! flag_var_tracking_uninit)
3154                 status = VAR_INIT_STATUS_INITIALIZED;
3155               if (GET_CODE (loc) == REG)
3156                 var_reg_set (&set, loc, status, NULL);
3157               else
3158                 var_mem_set (&set, loc, status, NULL);
3159
3160               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
3161             }
3162             break;
3163
3164           case MO_SET:
3165             {
3166               rtx loc = VTI (bb)->mos[i].u.loc;
3167               rtx set_src = NULL;
3168
3169               if (GET_CODE (loc) == SET)
3170                 {
3171                   set_src = SET_SRC (loc);
3172                   loc = SET_DEST (loc);
3173                 }
3174
3175               if (REG_P (loc))
3176                 var_reg_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
3177                                         set_src);
3178               else
3179                 var_mem_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
3180                                         set_src);
3181
3182               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
3183             }
3184             break;
3185
3186           case MO_COPY:
3187             {
3188               rtx loc = VTI (bb)->mos[i].u.loc;
3189               enum var_init_status src_status;
3190               rtx set_src = NULL;
3191
3192               if (GET_CODE (loc) == SET)
3193                 {
3194                   set_src = SET_SRC (loc);
3195                   loc = SET_DEST (loc);
3196                 }
3197
3198               src_status = find_src_status (&set, set_src);
3199               set_src = find_src_set_src (&set, set_src);
3200
3201               if (REG_P (loc))
3202                 var_reg_delete_and_set (&set, loc, false, src_status, set_src);
3203               else
3204                 var_mem_delete_and_set (&set, loc, false, src_status, set_src);
3205
3206               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
3207             }
3208             break;
3209
3210           case MO_USE_NO_VAR:
3211             {
3212               rtx loc = VTI (bb)->mos[i].u.loc;
3213
3214               if (REG_P (loc))
3215                 var_reg_delete (&set, loc, false);
3216               else
3217                 var_mem_delete (&set, loc, false);
3218
3219               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
3220             }
3221             break;
3222
3223           case MO_CLOBBER:
3224             {
3225               rtx loc = VTI (bb)->mos[i].u.loc;
3226
3227               if (REG_P (loc))
3228                 var_reg_delete (&set, loc, true);
3229               else
3230                 var_mem_delete (&set, loc, true);
3231
3232               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
3233             }
3234             break;
3235
3236           case MO_ADJUST:
3237             set.stack_adjust += VTI (bb)->mos[i].u.adjust;
3238             break;
3239         }
3240     }
3241   dataflow_set_destroy (&set);
3242 }
3243
3244 /* Emit notes for the whole function.  */
3245
3246 static void
3247 vt_emit_notes (void)
3248 {
3249   basic_block bb;
3250   dataflow_set *last_out;
3251   dataflow_set empty;
3252
3253   gcc_assert (!htab_elements (changed_variables));
3254
3255   /* Enable emitting notes by functions (mainly by set_variable_part and
3256      delete_variable_part).  */
3257   emit_notes = true;
3258
3259   dataflow_set_init (&empty);
3260   last_out = &empty;
3261
3262   FOR_EACH_BB (bb)
3263     {
3264       /* Emit the notes for changes of variable locations between two
3265          subsequent basic blocks.  */
3266       emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
3267
3268       /* Emit the notes for the changes in the basic block itself.  */
3269       emit_notes_in_bb (bb);
3270
3271       last_out = &VTI (bb)->out;
3272     }
3273   dataflow_set_destroy (&empty);
3274   emit_notes = false;
3275 }
3276
3277 /* If there is a declaration and offset associated with register/memory RTL
3278    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
3279
3280 static bool
3281 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
3282 {
3283   if (REG_P (rtl))
3284     {
3285       if (REG_ATTRS (rtl))
3286         {
3287           *declp = REG_EXPR (rtl);
3288           *offsetp = REG_OFFSET (rtl);
3289           return true;
3290         }
3291     }
3292   else if (MEM_P (rtl))
3293     {
3294       if (MEM_ATTRS (rtl))
3295         {
3296           *declp = MEM_EXPR (rtl);
3297           *offsetp = INT_MEM_OFFSET (rtl);
3298           return true;
3299         }
3300     }
3301   return false;
3302 }
3303
3304 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
3305
3306 static void
3307 vt_add_function_parameters (void)
3308 {
3309   tree parm;
3310
3311   for (parm = DECL_ARGUMENTS (current_function_decl);
3312        parm; parm = TREE_CHAIN (parm))
3313     {
3314       rtx decl_rtl = DECL_RTL_IF_SET (parm);
3315       rtx incoming = DECL_INCOMING_RTL (parm);
3316       tree decl;
3317       enum machine_mode mode;
3318       HOST_WIDE_INT offset;
3319       dataflow_set *out;
3320
3321       if (TREE_CODE (parm) != PARM_DECL)
3322         continue;
3323
3324       if (!DECL_NAME (parm))
3325         continue;
3326
3327       if (!decl_rtl || !incoming)
3328         continue;
3329
3330       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
3331         continue;
3332
3333       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
3334         {
3335           if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
3336             continue;
3337           offset += byte_lowpart_offset (GET_MODE (incoming),
3338                                          GET_MODE (decl_rtl));
3339         }
3340
3341       if (!decl)
3342         continue;
3343
3344       if (parm != decl)
3345         {
3346           /* Assume that DECL_RTL was a pseudo that got spilled to
3347              memory.  The spill slot sharing code will force the
3348              memory to reference spill_slot_decl (%sfp), so we don't
3349              match above.  That's ok, the pseudo must have referenced
3350              the entire parameter, so just reset OFFSET.  */
3351           gcc_assert (decl == get_spill_slot_decl (false));
3352           offset = 0;
3353         }
3354
3355       if (!track_loc_p (incoming, parm, offset, false, &mode, &offset))
3356         continue;
3357
3358       out = &VTI (ENTRY_BLOCK_PTR)->out;
3359
3360       if (REG_P (incoming))
3361         {
3362           incoming = var_lowpart (mode, incoming);
3363           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
3364           attrs_list_insert (&out->regs[REGNO (incoming)],
3365                              parm, offset, incoming);
3366           set_variable_part (out, incoming, parm, offset, VAR_INIT_STATUS_INITIALIZED,
3367                              NULL);
3368         }
3369       else if (MEM_P (incoming))
3370         {
3371           incoming = var_lowpart (mode, incoming);
3372           set_variable_part (out, incoming, parm, offset,
3373                              VAR_INIT_STATUS_INITIALIZED, NULL);
3374         }
3375     }
3376 }
3377
3378 /* Allocate and initialize the data structures for variable tracking
3379    and parse the RTL to get the micro operations.  */
3380
3381 static void
3382 vt_initialize (void)
3383 {
3384   basic_block bb;
3385
3386   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
3387
3388   FOR_EACH_BB (bb)
3389     {
3390       rtx insn;
3391       HOST_WIDE_INT pre, post = 0;
3392
3393       /* Count the number of micro operations.  */
3394       VTI (bb)->n_mos = 0;
3395       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3396            insn = NEXT_INSN (insn))
3397         {
3398           if (INSN_P (insn))
3399             {
3400               if (!frame_pointer_needed)
3401                 {
3402                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3403                   if (pre)
3404                     VTI (bb)->n_mos++;
3405                   if (post)
3406                     VTI (bb)->n_mos++;
3407                 }
3408               note_uses (&PATTERN (insn), count_uses_1, insn);
3409               note_stores (PATTERN (insn), count_stores, insn);
3410               if (CALL_P (insn))
3411                 VTI (bb)->n_mos++;
3412             }
3413         }
3414
3415       /* Add the micro-operations to the array.  */
3416       VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
3417       VTI (bb)->n_mos = 0;
3418       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3419            insn = NEXT_INSN (insn))
3420         {
3421           if (INSN_P (insn))
3422             {
3423               int n1, n2;
3424
3425               if (!frame_pointer_needed)
3426                 {
3427                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3428                   if (pre)
3429                     {
3430                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3431
3432                       mo->type = MO_ADJUST;
3433                       mo->u.adjust = pre;
3434                       mo->insn = insn;
3435                     }
3436                 }
3437
3438               n1 = VTI (bb)->n_mos;
3439               note_uses (&PATTERN (insn), add_uses_1, insn);
3440               n2 = VTI (bb)->n_mos - 1;
3441
3442               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
3443               while (n1 < n2)
3444                 {
3445                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
3446                     n1++;
3447                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
3448                     n2--;
3449                   if (n1 < n2)
3450                     {
3451                       micro_operation sw;
3452
3453                       sw = VTI (bb)->mos[n1];
3454                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3455                       VTI (bb)->mos[n2] = sw;
3456                     }
3457                 }
3458
3459               if (CALL_P (insn))
3460                 {
3461                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3462
3463                   mo->type = MO_CALL;
3464                   mo->insn = insn;
3465                 }
3466
3467               n1 = VTI (bb)->n_mos;
3468               /* This will record NEXT_INSN (insn), such that we can
3469                  insert notes before it without worrying about any
3470                  notes that MO_USEs might emit after the insn.  */
3471               note_stores (PATTERN (insn), add_stores, insn);
3472               n2 = VTI (bb)->n_mos - 1;
3473
3474               /* Order the MO_CLOBBERs to be before MO_SETs.  */
3475               while (n1 < n2)
3476                 {
3477                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
3478                     n1++;
3479                   while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET
3480                                      || VTI (bb)->mos[n2].type == MO_COPY))
3481                     n2--;
3482                   if (n1 < n2)
3483                     {
3484                       micro_operation sw;
3485
3486                       sw = VTI (bb)->mos[n1];
3487                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3488                       VTI (bb)->mos[n2] = sw;
3489                     }
3490                 }
3491
3492               if (!frame_pointer_needed && post)
3493                 {
3494                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3495
3496                   mo->type = MO_ADJUST;
3497                   mo->u.adjust = post;
3498                   mo->insn = insn;
3499                 }
3500             }
3501         }
3502     }
3503
3504   attrs_pool = create_alloc_pool ("attrs_def pool",
3505                                   sizeof (struct attrs_def), 1024);
3506   var_pool = create_alloc_pool ("variable_def pool",
3507                                 sizeof (struct variable_def), 64);
3508   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
3509                                       sizeof (struct location_chain_def),
3510                                       1024);
3511   shared_hash_pool = create_alloc_pool ("shared_hash_def pool",
3512                                         sizeof (struct shared_hash_def), 256);
3513   empty_shared_hash = (shared_hash) pool_alloc (shared_hash_pool);
3514   empty_shared_hash->refcount = 1;
3515   empty_shared_hash->htab
3516     = htab_create (1, variable_htab_hash, variable_htab_eq,
3517                    variable_htab_free);
3518   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
3519                                    variable_htab_free);
3520
3521   /* Init the IN and OUT sets.  */
3522   FOR_ALL_BB (bb)
3523     {
3524       VTI (bb)->visited = false;
3525       dataflow_set_init (&VTI (bb)->in);
3526       dataflow_set_init (&VTI (bb)->out);
3527     }
3528
3529   vt_add_function_parameters ();
3530 }
3531
3532 /* Free the data structures needed for variable tracking.  */
3533
3534 static void
3535 vt_finalize (void)
3536 {
3537   basic_block bb;
3538
3539   FOR_EACH_BB (bb)
3540     {
3541       free (VTI (bb)->mos);
3542     }
3543
3544   FOR_ALL_BB (bb)
3545     {
3546       dataflow_set_destroy (&VTI (bb)->in);
3547       dataflow_set_destroy (&VTI (bb)->out);
3548     }
3549   free_aux_for_blocks ();
3550   htab_delete (empty_shared_hash->htab);
3551   htab_delete (changed_variables);
3552   free_alloc_pool (attrs_pool);
3553   free_alloc_pool (var_pool);
3554   free_alloc_pool (loc_chain_pool);
3555   free_alloc_pool (shared_hash_pool);
3556 }
3557
3558 /* The entry point to variable tracking pass.  */
3559
3560 unsigned int
3561 variable_tracking_main (void)
3562 {
3563   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
3564     return 0;
3565
3566   mark_dfs_back_edges ();
3567   vt_initialize ();
3568   if (!frame_pointer_needed)
3569     {
3570       if (!vt_stack_adjustments ())
3571         {
3572           vt_finalize ();
3573           return 0;
3574         }
3575     }
3576
3577   vt_find_locations ();
3578   vt_emit_notes ();
3579
3580   if (dump_file && (dump_flags & TDF_DETAILS))
3581     {
3582       dump_dataflow_sets ();
3583       dump_flow_info (dump_file, dump_flags);
3584     }
3585
3586   vt_finalize ();
3587   return 0;
3588 }
3589 \f
3590 static bool
3591 gate_handle_var_tracking (void)
3592 {
3593   return (flag_var_tracking);
3594 }
3595
3596
3597
3598 struct rtl_opt_pass pass_variable_tracking =
3599 {
3600  {
3601   RTL_PASS,
3602   "vartrack",                           /* name */
3603   gate_handle_var_tracking,             /* gate */
3604   variable_tracking_main,               /* execute */
3605   NULL,                                 /* sub */
3606   NULL,                                 /* next */
3607   0,                                    /* static_pass_number */
3608   TV_VAR_TRACKING,                      /* tv_id */
3609   0,                                    /* properties_required */
3610   0,                                    /* properties_provided */
3611   0,                                    /* properties_destroyed */
3612   0,                                    /* todo_flags_start */
3613   TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */
3614  }
3615 };