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