gcc/var-tracking.c

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