gcc/var-tracking.c

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