gcc/var-tracking.c

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