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   rtx pattern;
1810   tree decl = NULL_TREE;
1811   enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
1812
1813   if (! flag_var_tracking_uninit)
1814     status = VAR_INIT_STATUS_INITIALIZED;
1815
1816   pattern = PATTERN (insn);
1817
1818   if (GET_CODE (pattern) == COND_EXEC)
1819     pattern = COND_EXEC_CODE (pattern);
1820
1821   if (GET_CODE (pattern) == SET)
1822     src = SET_SRC (pattern);
1823   else if (GET_CODE (pattern) == PARALLEL
1824            || GET_CODE (pattern) == SEQUENCE)
1825     {
1826       int i;
1827       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1828         if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
1829             && SET_DEST (XVECEXP (pattern, 0, i)) == loc)
1830           src = SET_SRC (XVECEXP (pattern, 0, i));
1831     }
1832
1833   if (src && REG_P (src))
1834     decl = var_debug_decl (REG_EXPR (src));
1835   else if (src && MEM_P (src))
1836     decl = var_debug_decl (MEM_EXPR (src));
1837
1838   if (src && decl)
1839     status = get_init_value (in, src, decl);
1840
1841   return status;
1842 }
1843
1844 /* LOC is the destination the variable is being copied to.  INSN
1845    contains the copy instruction.  SET is the dataflow set containing
1846    the variable in LOC.  */
1847
1848 static rtx
1849 find_src_set_src (dataflow_set *set, rtx loc, rtx insn)
1850 {
1851   tree decl = NULL_TREE;   /* The variable being copied around.          */
1852   rtx src = NULL_RTX;      /* The location "decl" is being copied from.  */
1853   rtx set_src = NULL_RTX;  /* The value for "decl" stored in "src".      */
1854   rtx pattern;
1855   void **slot;
1856   variable var;
1857   location_chain nextp;
1858   int i;
1859   bool found;
1860
1861
1862   pattern = PATTERN (insn);
1863   if (GET_CODE (pattern) == COND_EXEC)
1864     pattern = COND_EXEC_CODE (pattern);
1865
1866   if (GET_CODE (pattern) == SET)
1867     src = SET_SRC (pattern);
1868   else if (GET_CODE (pattern) == PARALLEL
1869            || GET_CODE (pattern) == SEQUENCE)
1870     {
1871       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1872         if (GET_CODE (XVECEXP (pattern, 0, i)) == SET
1873             && SET_DEST (XVECEXP (pattern, 0, i)) == loc)
1874           src = SET_SRC (XVECEXP (pattern, 0, i));
1875     }
1876
1877   if (src && REG_P (src))
1878     decl = var_debug_decl (REG_EXPR (src));
1879   else if (src && MEM_P (src))
1880     decl = var_debug_decl (MEM_EXPR (src));
1881
1882   if (src && decl)
1883     {
1884       slot = htab_find_slot_with_hash (set->vars, decl,
1885                                        VARIABLE_HASH_VAL (decl), NO_INSERT);
1886
1887       if (slot)
1888         {
1889           var = *(variable *) slot;
1890           found = false;
1891           for (i = 0; i < var->n_var_parts && !found; i++)
1892             for (nextp = var->var_part[i].loc_chain; nextp && !found;
1893                  nextp = nextp->next)
1894               if (rtx_equal_p (nextp->loc, src))
1895                 {
1896                   set_src = nextp->set_src;
1897                   found = true;
1898                 }
1899
1900         }
1901     }
1902
1903   return set_src;
1904 }
1905
1906 /* Compute the changes of variable locations in the basic block BB.  */
1907
1908 static bool
1909 compute_bb_dataflow (basic_block bb)
1910 {
1911   int i, n, r;
1912   bool changed;
1913   dataflow_set old_out;
1914   dataflow_set *in = &VTI (bb)->in;
1915   dataflow_set *out = &VTI (bb)->out;
1916
1917   dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
1918   dataflow_set_copy (&old_out, out);
1919   dataflow_set_copy (out, in);
1920
1921   n = VTI (bb)->n_mos;
1922   for (i = 0; i < n; i++)
1923     {
1924       switch (VTI (bb)->mos[i].type)
1925         {
1926           case MO_CALL:
1927             for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1928               if (TEST_HARD_REG_BIT (call_used_reg_set, r))
1929                 var_regno_delete (out, r);
1930             break;
1931
1932           case MO_USE:
1933             {
1934               rtx loc = VTI (bb)->mos[i].u.loc;
1935               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
1936
1937               if (! flag_var_tracking_uninit)
1938                 status = VAR_INIT_STATUS_INITIALIZED;
1939
1940               if (GET_CODE (loc) == REG)
1941                 var_reg_set (out, loc, status, NULL);
1942               else if (GET_CODE (loc) == MEM)
1943                 var_mem_set (out, loc, status, NULL);
1944             }
1945             break;
1946
1947           case MO_SET:
1948             {
1949               rtx loc = VTI (bb)->mos[i].u.loc;
1950               rtx set_src =  NULL;
1951               rtx insn = VTI (bb)->mos[i].insn;
1952
1953               if (GET_CODE (PATTERN (insn)) == SET)
1954                 set_src = SET_SRC (PATTERN (insn));
1955               else if (GET_CODE (PATTERN (insn)) == PARALLEL
1956                        || GET_CODE (PATTERN (insn)) == SEQUENCE)
1957                 {
1958                   int j;
1959                   for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
1960                     if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
1961                         && SET_DEST (XVECEXP (PATTERN (insn), 0, j)) == loc)
1962                       set_src = SET_SRC (XVECEXP (PATTERN (insn), 0, j));
1963                 }
1964
1965               if (REG_P (loc))
1966                 var_reg_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
1967                                         set_src);
1968               else if (MEM_P (loc))
1969                 var_mem_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
1970                                         set_src);
1971             }
1972             break;
1973
1974           case MO_COPY:
1975             {
1976               rtx loc = VTI (bb)->mos[i].u.loc;
1977               enum var_init_status src_status;
1978               rtx set_src;
1979
1980               if (! flag_var_tracking_uninit)
1981                 src_status = VAR_INIT_STATUS_INITIALIZED;
1982               else
1983                 src_status = find_src_status (in, loc, VTI (bb)->mos[i].insn);
1984
1985               if (src_status == VAR_INIT_STATUS_UNKNOWN)
1986                 src_status = find_src_status (out, loc, VTI (bb)->mos[i].insn);
1987
1988               set_src = find_src_set_src (in, loc, VTI (bb)->mos[i].insn);
1989
1990               if (REG_P (loc))
1991                 var_reg_delete_and_set (out, loc, false, src_status, set_src);
1992               else if (MEM_P (loc))
1993                 var_mem_delete_and_set (out, loc, false, src_status, set_src);
1994             }
1995             break;
1996
1997           case MO_USE_NO_VAR:
1998             {
1999               rtx loc = VTI (bb)->mos[i].u.loc;
2000
2001               if (REG_P (loc))
2002                 var_reg_delete (out, loc, false);
2003               else if (MEM_P (loc))
2004                 var_mem_delete (out, loc, false);
2005             }
2006             break;
2007
2008           case MO_CLOBBER:
2009             {
2010               rtx loc = VTI (bb)->mos[i].u.loc;
2011
2012               if (REG_P (loc))
2013                 var_reg_delete (out, loc, true);
2014               else if (MEM_P (loc))
2015                 var_mem_delete (out, loc, true);
2016             }
2017             break;
2018
2019           case MO_ADJUST:
2020             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
2021             break;
2022         }
2023     }
2024
2025   changed = dataflow_set_different (&old_out, out);
2026   dataflow_set_destroy (&old_out);
2027   return changed;
2028 }
2029
2030 /* Find the locations of variables in the whole function.  */
2031
2032 static void
2033 vt_find_locations (void)
2034 {
2035   fibheap_t worklist, pending, fibheap_swap;
2036   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
2037   basic_block bb;
2038   edge e;
2039   int *bb_order;
2040   int *rc_order;
2041   int i;
2042
2043   /* Compute reverse completion order of depth first search of the CFG
2044      so that the data-flow runs faster.  */
2045   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
2046   bb_order = XNEWVEC (int, last_basic_block);
2047   pre_and_rev_post_order_compute (NULL, rc_order, false);
2048   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2049     bb_order[rc_order[i]] = i;
2050   free (rc_order);
2051
2052   worklist = fibheap_new ();
2053   pending = fibheap_new ();
2054   visited = sbitmap_alloc (last_basic_block);
2055   in_worklist = sbitmap_alloc (last_basic_block);
2056   in_pending = sbitmap_alloc (last_basic_block);
2057   sbitmap_zero (in_worklist);
2058
2059   FOR_EACH_BB (bb)
2060     fibheap_insert (pending, bb_order[bb->index], bb);
2061   sbitmap_ones (in_pending);
2062
2063   while (!fibheap_empty (pending))
2064     {
2065       fibheap_swap = pending;
2066       pending = worklist;
2067       worklist = fibheap_swap;
2068       sbitmap_swap = in_pending;
2069       in_pending = in_worklist;
2070       in_worklist = sbitmap_swap;
2071
2072       sbitmap_zero (visited);
2073
2074       while (!fibheap_empty (worklist))
2075         {
2076           bb = fibheap_extract_min (worklist);
2077           RESET_BIT (in_worklist, bb->index);
2078           if (!TEST_BIT (visited, bb->index))
2079             {
2080               bool changed;
2081               edge_iterator ei;
2082
2083               SET_BIT (visited, bb->index);
2084
2085               /* Calculate the IN set as union of predecessor OUT sets.  */
2086               dataflow_set_clear (&VTI (bb)->in);
2087               FOR_EACH_EDGE (e, ei, bb->preds)
2088                 {
2089                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
2090                 }
2091
2092               changed = compute_bb_dataflow (bb);
2093               if (changed)
2094                 {
2095                   FOR_EACH_EDGE (e, ei, bb->succs)
2096                     {
2097                       if (e->dest == EXIT_BLOCK_PTR)
2098                         continue;
2099
2100                       if (e->dest == bb)
2101                         continue;
2102
2103                       if (TEST_BIT (visited, e->dest->index))
2104                         {
2105                           if (!TEST_BIT (in_pending, e->dest->index))
2106                             {
2107                               /* Send E->DEST to next round.  */
2108                               SET_BIT (in_pending, e->dest->index);
2109                               fibheap_insert (pending,
2110                                               bb_order[e->dest->index],
2111                                               e->dest);
2112                             }
2113                         }
2114                       else if (!TEST_BIT (in_worklist, e->dest->index))
2115                         {
2116                           /* Add E->DEST to current round.  */
2117                           SET_BIT (in_worklist, e->dest->index);
2118                           fibheap_insert (worklist, bb_order[e->dest->index],
2119                                           e->dest);
2120                         }
2121                     }
2122                 }
2123             }
2124         }
2125     }
2126
2127   free (bb_order);
2128   fibheap_delete (worklist);
2129   fibheap_delete (pending);
2130   sbitmap_free (visited);
2131   sbitmap_free (in_worklist);
2132   sbitmap_free (in_pending);
2133 }
2134
2135 /* Print the content of the LIST to dump file.  */
2136
2137 static void
2138 dump_attrs_list (attrs list)
2139 {
2140   for (; list; list = list->next)
2141     {
2142       print_mem_expr (dump_file, list->decl);
2143       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
2144     }
2145   fprintf (dump_file, "\n");
2146 }
2147
2148 /* Print the information about variable *SLOT to dump file.  */
2149
2150 static int
2151 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
2152 {
2153   variable var = *(variable *) slot;
2154   int i;
2155   location_chain node;
2156
2157   fprintf (dump_file, "  name: %s\n",
2158            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
2159   for (i = 0; i < var->n_var_parts; i++)
2160     {
2161       fprintf (dump_file, "    offset %ld\n",
2162                (long) var->var_part[i].offset);
2163       for (node = var->var_part[i].loc_chain; node; node = node->next)
2164         {
2165           fprintf (dump_file, "      ");
2166           if (node->init == VAR_INIT_STATUS_UNINITIALIZED)
2167             fprintf (dump_file, "[uninit]");
2168           print_rtl_single (dump_file, node->loc);
2169         }
2170     }
2171
2172   /* Continue traversing the hash table.  */
2173   return 1;
2174 }
2175
2176 /* Print the information about variables from hash table VARS to dump file.  */
2177
2178 static void
2179 dump_vars (htab_t vars)
2180 {
2181   if (htab_elements (vars) > 0)
2182     {
2183       fprintf (dump_file, "Variables:\n");
2184       htab_traverse (vars, dump_variable, NULL);
2185     }
2186 }
2187
2188 /* Print the dataflow set SET to dump file.  */
2189
2190 static void
2191 dump_dataflow_set (dataflow_set *set)
2192 {
2193   int i;
2194
2195   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
2196            set->stack_adjust);
2197   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2198     {
2199       if (set->regs[i])
2200         {
2201           fprintf (dump_file, "Reg %d:", i);
2202           dump_attrs_list (set->regs[i]);
2203         }
2204     }
2205   dump_vars (set->vars);
2206   fprintf (dump_file, "\n");
2207 }
2208
2209 /* Print the IN and OUT sets for each basic block to dump file.  */
2210
2211 static void
2212 dump_dataflow_sets (void)
2213 {
2214   basic_block bb;
2215
2216   FOR_EACH_BB (bb)
2217     {
2218       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
2219       fprintf (dump_file, "IN:\n");
2220       dump_dataflow_set (&VTI (bb)->in);
2221       fprintf (dump_file, "OUT:\n");
2222       dump_dataflow_set (&VTI (bb)->out);
2223     }
2224 }
2225
2226 /* Add variable VAR to the hash table of changed variables and
2227    if it has no locations delete it from hash table HTAB.  */
2228
2229 static void
2230 variable_was_changed (variable var, htab_t htab)
2231 {
2232   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
2233
2234   if (emit_notes)
2235     {
2236       variable *slot;
2237
2238       slot = (variable *) htab_find_slot_with_hash (changed_variables,
2239                                                     var->decl, hash, INSERT);
2240
2241       if (htab && var->n_var_parts == 0)
2242         {
2243           variable empty_var;
2244           void **old;
2245
2246           empty_var = pool_alloc (var_pool);
2247           empty_var->decl = var->decl;
2248           empty_var->refcount = 1;
2249           empty_var->n_var_parts = 0;
2250           *slot = empty_var;
2251
2252           old = htab_find_slot_with_hash (htab, var->decl, hash,
2253                                           NO_INSERT);
2254           if (old)
2255             htab_clear_slot (htab, old);
2256         }
2257       else
2258         {
2259           *slot = var;
2260         }
2261     }
2262   else
2263     {
2264       gcc_assert (htab);
2265       if (var->n_var_parts == 0)
2266         {
2267           void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
2268                                                   NO_INSERT);
2269           if (slot)
2270             htab_clear_slot (htab, slot);
2271         }
2272     }
2273 }
2274
2275 /* Look for the index in VAR->var_part corresponding to OFFSET.
2276    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
2277    referenced int will be set to the index that the part has or should
2278    have, if it should be inserted.  */
2279
2280 static inline int
2281 find_variable_location_part (variable var, HOST_WIDE_INT offset,
2282                              int *insertion_point)
2283 {
2284   int pos, low, high;
2285
2286   /* Find the location part.  */
2287   low = 0;
2288   high = var->n_var_parts;
2289   while (low != high)
2290     {
2291       pos = (low + high) / 2;
2292       if (var->var_part[pos].offset < offset)
2293         low = pos + 1;
2294       else
2295         high = pos;
2296     }
2297   pos = low;
2298
2299   if (insertion_point)
2300     *insertion_point = pos;
2301
2302   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2303     return pos;
2304
2305   return -1;
2306 }
2307
2308 /* Set the part of variable's location in the dataflow set SET.  The variable
2309    part is specified by variable's declaration DECL and offset OFFSET and the
2310    part's location by LOC.  */
2311
2312 static void
2313 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset,
2314                    enum var_init_status initialized, rtx set_src)
2315 {
2316   int pos;
2317   location_chain node, next;
2318   location_chain *nextp;
2319   variable var;
2320   void **slot;
2321
2322   slot = htab_find_slot_with_hash (set->vars, decl,
2323                                    VARIABLE_HASH_VAL (decl), INSERT);
2324   if (!*slot)
2325     {
2326       /* Create new variable information.  */
2327       var = pool_alloc (var_pool);
2328       var->decl = decl;
2329       var->refcount = 1;
2330       var->n_var_parts = 1;
2331       var->var_part[0].offset = offset;
2332       var->var_part[0].loc_chain = NULL;
2333       var->var_part[0].cur_loc = NULL;
2334       *slot = var;
2335       pos = 0;
2336     }
2337   else
2338     {
2339       int inspos = 0;
2340
2341       var = (variable) *slot;
2342
2343       pos = find_variable_location_part (var, offset, &inspos);
2344
2345       if (pos >= 0)
2346         {
2347           node = var->var_part[pos].loc_chain;
2348
2349           if (node
2350               && ((REG_P (node->loc) && REG_P (loc)
2351                    && REGNO (node->loc) == REGNO (loc))
2352                   || rtx_equal_p (node->loc, loc)))
2353             {
2354               /* LOC is in the beginning of the chain so we have nothing
2355                  to do.  */
2356               if (node->init < initialized)
2357                 node->init = initialized;
2358               if (set_src != NULL)
2359                 node->set_src = set_src;
2360
2361               *slot = var;
2362               return;
2363             }
2364           else
2365             {
2366               /* We have to make a copy of a shared variable.  */
2367               if (var->refcount > 1)
2368                 var = unshare_variable (set, var, initialized);
2369             }
2370         }
2371       else
2372         {
2373           /* We have not found the location part, new one will be created.  */
2374
2375           /* We have to make a copy of the shared variable.  */
2376           if (var->refcount > 1)
2377             var = unshare_variable (set, var, initialized);
2378
2379           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2380              thus there are at most MAX_VAR_PARTS different offsets.  */
2381           gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
2382
2383           /* We have to move the elements of array starting at index
2384              inspos to the next position.  */
2385           for (pos = var->n_var_parts; pos > inspos; pos--)
2386             var->var_part[pos] = var->var_part[pos - 1];
2387
2388           var->n_var_parts++;
2389           var->var_part[pos].offset = offset;
2390           var->var_part[pos].loc_chain = NULL;
2391           var->var_part[pos].cur_loc = NULL;
2392         }
2393     }
2394
2395   /* Delete the location from the list.  */
2396   nextp = &var->var_part[pos].loc_chain;
2397   for (node = var->var_part[pos].loc_chain; node; node = next)
2398     {
2399       next = node->next;
2400       if ((REG_P (node->loc) && REG_P (loc)
2401            && REGNO (node->loc) == REGNO (loc))
2402           || rtx_equal_p (node->loc, loc))
2403         {
2404           /* Save these values, to assign to the new node, before
2405              deleting this one.  */
2406           if (node->init > initialized)
2407             initialized = node->init;
2408           if (node->set_src != NULL && set_src == NULL)
2409             set_src = node->set_src;
2410           pool_free (loc_chain_pool, node);
2411           *nextp = next;
2412           break;
2413         }
2414       else
2415         nextp = &node->next;
2416     }
2417
2418   /* Add the location to the beginning.  */
2419   node = pool_alloc (loc_chain_pool);
2420   node->loc = loc;
2421   node->init = initialized;
2422   node->set_src = set_src;
2423   node->next = var->var_part[pos].loc_chain;
2424   var->var_part[pos].loc_chain = node;
2425
2426   /* If no location was emitted do so.  */
2427   if (var->var_part[pos].cur_loc == NULL)
2428     {
2429       var->var_part[pos].cur_loc = loc;
2430       variable_was_changed (var, set->vars);
2431     }
2432 }
2433
2434 /* Remove all recorded register locations for the given variable part
2435    from dataflow set SET, except for those that are identical to loc.
2436    The variable part is specified by variable's declaration DECL and
2437    offset OFFSET.  */
2438
2439 static void
2440 clobber_variable_part (dataflow_set *set, rtx loc, tree decl,
2441                        HOST_WIDE_INT offset, rtx set_src)
2442 {
2443   void **slot;
2444
2445   if (! decl || ! DECL_P (decl))
2446     return;
2447
2448   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2449                                    NO_INSERT);
2450   if (slot)
2451     {
2452       variable var = (variable) *slot;
2453       int pos = find_variable_location_part (var, offset, NULL);
2454
2455       if (pos >= 0)
2456         {
2457           location_chain node, next;
2458
2459           /* Remove the register locations from the dataflow set.  */
2460           next = var->var_part[pos].loc_chain;
2461           for (node = next; node; node = next)
2462             {
2463               next = node->next;
2464               if (node->loc != loc
2465                   && (!flag_var_tracking_uninit
2466                       || !set_src
2467                       || MEM_P (set_src)
2468                       || !rtx_equal_p (set_src, node->set_src)))
2469                 {
2470                   if (REG_P (node->loc))
2471                     {
2472                       attrs anode, anext;
2473                       attrs *anextp;
2474
2475                       /* Remove the variable part from the register's
2476                          list, but preserve any other variable parts
2477                          that might be regarded as live in that same
2478                          register.  */
2479                       anextp = &set->regs[REGNO (node->loc)];
2480                       for (anode = *anextp; anode; anode = anext)
2481                         {
2482                           anext = anode->next;
2483                           if (anode->decl == decl
2484                               && anode->offset == offset)
2485                             {
2486                               pool_free (attrs_pool, anode);
2487                               *anextp = anext;
2488                             }
2489                         }
2490                     }
2491
2492                   delete_variable_part (set, node->loc, decl, offset);
2493                 }
2494             }
2495         }
2496     }
2497 }
2498
2499 /* Delete the part of variable's location from dataflow set SET.  The variable
2500    part is specified by variable's declaration DECL and offset OFFSET and the
2501    part's location by LOC.  */
2502
2503 static void
2504 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2505                       HOST_WIDE_INT offset)
2506 {
2507   void **slot;
2508
2509   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2510                                    NO_INSERT);
2511   if (slot)
2512     {
2513       variable var = (variable) *slot;
2514       int pos = find_variable_location_part (var, offset, NULL);
2515
2516       if (pos >= 0)
2517         {
2518           location_chain node, next;
2519           location_chain *nextp;
2520           bool changed;
2521
2522           if (var->refcount > 1)
2523             {
2524               /* If the variable contains the location part we have to
2525                  make a copy of the variable.  */
2526               for (node = var->var_part[pos].loc_chain; node;
2527                    node = node->next)
2528                 {
2529                   if ((REG_P (node->loc) && REG_P (loc)
2530                        && REGNO (node->loc) == REGNO (loc))
2531                       || rtx_equal_p (node->loc, loc))
2532                     {
2533                       enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
2534                       if (! flag_var_tracking_uninit)
2535                         status = VAR_INIT_STATUS_INITIALIZED;
2536                       var = unshare_variable (set, var, status);
2537                       break;
2538                     }
2539                 }
2540             }
2541
2542           /* Delete the location part.  */
2543           nextp = &var->var_part[pos].loc_chain;
2544           for (node = *nextp; node; node = next)
2545             {
2546               next = node->next;
2547               if ((REG_P (node->loc) && REG_P (loc)
2548                    && REGNO (node->loc) == REGNO (loc))
2549                   || rtx_equal_p (node->loc, loc))
2550                 {
2551                   pool_free (loc_chain_pool, node);
2552                   *nextp = next;
2553                   break;
2554                 }
2555               else
2556                 nextp = &node->next;
2557             }
2558
2559           /* If we have deleted the location which was last emitted
2560              we have to emit new location so add the variable to set
2561              of changed variables.  */
2562           if (var->var_part[pos].cur_loc
2563               && ((REG_P (loc)
2564                    && REG_P (var->var_part[pos].cur_loc)
2565                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2566                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2567             {
2568               changed = true;
2569               if (var->var_part[pos].loc_chain)
2570                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2571             }
2572           else
2573             changed = false;
2574
2575           if (var->var_part[pos].loc_chain == NULL)
2576             {
2577               var->n_var_parts--;
2578               while (pos < var->n_var_parts)
2579                 {
2580                   var->var_part[pos] = var->var_part[pos + 1];
2581                   pos++;
2582                 }
2583             }
2584           if (changed)
2585             variable_was_changed (var, set->vars);
2586         }
2587     }
2588 }
2589
2590 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2591    additional parameters: WHERE specifies whether the note shall be emitted
2592    before of after instruction INSN.  */
2593
2594 static int
2595 emit_note_insn_var_location (void **varp, void *data)
2596 {
2597   variable var = *(variable *) varp;
2598   rtx insn = ((emit_note_data *)data)->insn;
2599   enum emit_note_where where = ((emit_note_data *)data)->where;
2600   rtx note;
2601   int i, j, n_var_parts;
2602   bool complete;
2603   enum var_init_status initialized = VAR_INIT_STATUS_UNINITIALIZED;
2604   HOST_WIDE_INT last_limit;
2605   tree type_size_unit;
2606   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2607   rtx loc[MAX_VAR_PARTS];
2608
2609   gcc_assert (var->decl);
2610
2611   if (! flag_var_tracking_uninit)
2612     initialized = VAR_INIT_STATUS_INITIALIZED;
2613
2614   complete = true;
2615   last_limit = 0;
2616   n_var_parts = 0;
2617   for (i = 0; i < var->n_var_parts; i++)
2618     {
2619       enum machine_mode mode, wider_mode;
2620
2621       if (last_limit < var->var_part[i].offset)
2622         {
2623           complete = false;
2624           break;
2625         }
2626       else if (last_limit > var->var_part[i].offset)
2627         continue;
2628       offsets[n_var_parts] = var->var_part[i].offset;
2629       loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2630       mode = GET_MODE (loc[n_var_parts]);
2631       initialized = var->var_part[i].loc_chain->init;
2632       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2633
2634       /* Attempt to merge adjacent registers or memory.  */
2635       wider_mode = GET_MODE_WIDER_MODE (mode);
2636       for (j = i + 1; j < var->n_var_parts; j++)
2637         if (last_limit <= var->var_part[j].offset)
2638           break;
2639       if (j < var->n_var_parts
2640           && wider_mode != VOIDmode
2641           && GET_CODE (loc[n_var_parts])
2642              == GET_CODE (var->var_part[j].loc_chain->loc)
2643           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2644           && last_limit == var->var_part[j].offset)
2645         {
2646           rtx new_loc = NULL;
2647           rtx loc2 = var->var_part[j].loc_chain->loc;
2648
2649           if (REG_P (loc[n_var_parts])
2650               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2651                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2652               && end_hard_regno (mode, REGNO (loc[n_var_parts]))
2653                  == REGNO (loc2))
2654             {
2655               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2656                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2657                                            mode, 0);
2658               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2659                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2660               if (new_loc)
2661                 {
2662                   if (!REG_P (new_loc)
2663                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2664                     new_loc = NULL;
2665                   else
2666                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2667                 }
2668             }
2669           else if (MEM_P (loc[n_var_parts])
2670                    && GET_CODE (XEXP (loc2, 0)) == PLUS
2671                    && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2672                    && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2673             {
2674               if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2675                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2676                                    XEXP (XEXP (loc2, 0), 0))
2677                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
2678                       == GET_MODE_SIZE (mode))
2679                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2680                       && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2681                          == CONST_INT
2682                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2683                                       XEXP (XEXP (loc2, 0), 0))
2684                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2685                          + GET_MODE_SIZE (mode)
2686                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2687                 new_loc = adjust_address_nv (loc[n_var_parts],
2688                                              wider_mode, 0);
2689             }
2690
2691           if (new_loc)
2692             {
2693               loc[n_var_parts] = new_loc;
2694               mode = wider_mode;
2695               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2696               i = j;
2697             }
2698         }
2699       ++n_var_parts;
2700     }
2701   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2702   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2703     complete = false;
2704
2705   if (where == EMIT_NOTE_AFTER_INSN)
2706     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2707   else
2708     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2709
2710   if (! flag_var_tracking_uninit)
2711     initialized = VAR_INIT_STATUS_INITIALIZED;
2712
2713   if (!complete)
2714     {
2715       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2716                                                        NULL_RTX, (int) initialized);
2717     }
2718   else if (n_var_parts == 1)
2719     {
2720       rtx expr_list
2721         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
2722
2723       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2724                                                        expr_list,
2725                                                        (int) initialized);
2726     }
2727   else if (n_var_parts)
2728     {
2729       rtx parallel;
2730
2731       for (i = 0; i < n_var_parts; i++)
2732         loc[i]
2733           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
2734
2735       parallel = gen_rtx_PARALLEL (VOIDmode,
2736                                    gen_rtvec_v (n_var_parts, loc));
2737       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2738                                                        parallel,
2739                                                        (int) initialized);
2740     }
2741
2742   htab_clear_slot (changed_variables, varp);
2743
2744   /* When there are no location parts the variable has been already
2745      removed from hash table and a new empty variable was created.
2746      Free the empty variable.  */
2747   if (var->n_var_parts == 0)
2748     {
2749       pool_free (var_pool, var);
2750     }
2751
2752   /* Continue traversing the hash table.  */
2753   return 1;
2754 }
2755
2756 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2757    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
2758    shall be emitted before of after instruction INSN.  */
2759
2760 static void
2761 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2762 {
2763   emit_note_data data;
2764
2765   data.insn = insn;
2766   data.where = where;
2767   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2768 }
2769
2770 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2771    same variable in hash table DATA or is not there at all.  */
2772
2773 static int
2774 emit_notes_for_differences_1 (void **slot, void *data)
2775 {
2776   htab_t new_vars = (htab_t) data;
2777   variable old_var, new_var;
2778
2779   old_var = *(variable *) slot;
2780   new_var = htab_find_with_hash (new_vars, old_var->decl,
2781                                  VARIABLE_HASH_VAL (old_var->decl));
2782
2783   if (!new_var)
2784     {
2785       /* Variable has disappeared.  */
2786       variable empty_var;
2787
2788       empty_var = pool_alloc (var_pool);
2789       empty_var->decl = old_var->decl;
2790       empty_var->refcount = 1;
2791       empty_var->n_var_parts = 0;
2792       variable_was_changed (empty_var, NULL);
2793     }
2794   else if (variable_different_p (old_var, new_var, true))
2795     {
2796       variable_was_changed (new_var, NULL);
2797     }
2798
2799   /* Continue traversing the hash table.  */
2800   return 1;
2801 }
2802
2803 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2804    table DATA.  */
2805
2806 static int
2807 emit_notes_for_differences_2 (void **slot, void *data)
2808 {
2809   htab_t old_vars = (htab_t) data;
2810   variable old_var, new_var;
2811
2812   new_var = *(variable *) slot;
2813   old_var = htab_find_with_hash (old_vars, new_var->decl,
2814                                  VARIABLE_HASH_VAL (new_var->decl));
2815   if (!old_var)
2816     {
2817       /* Variable has appeared.  */
2818       variable_was_changed (new_var, NULL);
2819     }
2820
2821   /* Continue traversing the hash table.  */
2822   return 1;
2823 }
2824
2825 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2826    NEW_SET.  */
2827
2828 static void
2829 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2830                             dataflow_set *new_set)
2831 {
2832   htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2833   htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2834   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2835 }
2836
2837 /* Emit the notes for changes of location parts in the basic block BB.  */
2838
2839 static void
2840 emit_notes_in_bb (basic_block bb)
2841 {
2842   int i;
2843   dataflow_set set;
2844
2845   dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2846   dataflow_set_copy (&set, &VTI (bb)->in);
2847
2848   for (i = 0; i < VTI (bb)->n_mos; i++)
2849     {
2850       rtx insn = VTI (bb)->mos[i].insn;
2851
2852       switch (VTI (bb)->mos[i].type)
2853         {
2854           case MO_CALL:
2855             {
2856               int r;
2857
2858               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2859                 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2860                   {
2861                     var_regno_delete (&set, r);
2862                   }
2863               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2864             }
2865             break;
2866
2867           case MO_USE:
2868             {
2869               rtx loc = VTI (bb)->mos[i].u.loc;
2870
2871               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
2872               if (! flag_var_tracking_uninit)
2873                 status = VAR_INIT_STATUS_INITIALIZED;
2874               if (GET_CODE (loc) == REG)
2875                 var_reg_set (&set, loc, status, NULL);
2876               else
2877                 var_mem_set (&set, loc, status, NULL);
2878
2879               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2880             }
2881             break;
2882
2883           case MO_SET:
2884             {
2885               rtx loc = VTI (bb)->mos[i].u.loc;
2886               rtx set_src =  NULL;
2887
2888               if (GET_CODE (PATTERN (insn)) == SET)
2889                 set_src = SET_SRC (PATTERN (insn));
2890               else if (GET_CODE (PATTERN (insn)) == PARALLEL
2891                        || GET_CODE (PATTERN (insn)) == SEQUENCE)
2892                 {
2893                   int j;
2894                   for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--)
2895                     if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET
2896                         && SET_DEST (XVECEXP (PATTERN (insn), 0, j)) == loc)
2897                       set_src = SET_SRC (XVECEXP (PATTERN (insn), 0, j));
2898                 }
2899
2900               if (REG_P (loc))
2901                 var_reg_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
2902                                         set_src);
2903               else
2904                 var_mem_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
2905                                         set_src);
2906
2907               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
2908             }
2909             break;
2910
2911           case MO_COPY:
2912             {
2913               rtx loc = VTI (bb)->mos[i].u.loc;
2914               enum var_init_status src_status;
2915               rtx set_src;
2916
2917               src_status = find_src_status (&set, loc, VTI (bb)->mos[i].insn);
2918               set_src = find_src_set_src (&set, loc, VTI (bb)->mos[i].insn);
2919
2920               if (REG_P (loc))
2921                 var_reg_delete_and_set (&set, loc, false, src_status, set_src);
2922               else
2923                 var_mem_delete_and_set (&set, loc, false, src_status, set_src);
2924
2925               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
2926             }
2927             break;
2928
2929           case MO_USE_NO_VAR:
2930             {
2931               rtx loc = VTI (bb)->mos[i].u.loc;
2932
2933               if (REG_P (loc))
2934                 var_reg_delete (&set, loc, false);
2935               else
2936                 var_mem_delete (&set, loc, false);
2937
2938               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2939             }
2940             break;
2941
2942           case MO_CLOBBER:
2943             {
2944               rtx loc = VTI (bb)->mos[i].u.loc;
2945
2946               if (REG_P (loc))
2947                 var_reg_delete (&set, loc, true);
2948               else
2949                 var_mem_delete (&set, loc, true);
2950
2951               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
2952             }
2953             break;
2954
2955           case MO_ADJUST:
2956             set.stack_adjust += VTI (bb)->mos[i].u.adjust;
2957             break;
2958         }
2959     }
2960   dataflow_set_destroy (&set);
2961 }
2962
2963 /* Emit notes for the whole function.  */
2964
2965 static void
2966 vt_emit_notes (void)
2967 {
2968   basic_block bb;
2969   dataflow_set *last_out;
2970   dataflow_set empty;
2971
2972   gcc_assert (!htab_elements (changed_variables));
2973
2974   /* Enable emitting notes by functions (mainly by set_variable_part and
2975      delete_variable_part).  */
2976   emit_notes = true;
2977
2978   dataflow_set_init (&empty, 7);
2979   last_out = &empty;
2980
2981   FOR_EACH_BB (bb)
2982     {
2983       /* Emit the notes for changes of variable locations between two
2984          subsequent basic blocks.  */
2985       emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
2986
2987       /* Emit the notes for the changes in the basic block itself.  */
2988       emit_notes_in_bb (bb);
2989
2990       last_out = &VTI (bb)->out;
2991     }
2992   dataflow_set_destroy (&empty);
2993   emit_notes = false;
2994 }
2995
2996 /* If there is a declaration and offset associated with register/memory RTL
2997    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
2998
2999 static bool
3000 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
3001 {
3002   if (REG_P (rtl))
3003     {
3004       if (REG_ATTRS (rtl))
3005         {
3006           *declp = REG_EXPR (rtl);
3007           *offsetp = REG_OFFSET (rtl);
3008           return true;
3009         }
3010     }
3011   else if (MEM_P (rtl))
3012     {
3013       if (MEM_ATTRS (rtl))
3014         {
3015           *declp = MEM_EXPR (rtl);
3016           *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0;
3017           return true;
3018         }
3019     }
3020   return false;
3021 }
3022
3023 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
3024
3025 static void
3026 vt_add_function_parameters (void)
3027 {
3028   tree parm;
3029
3030   for (parm = DECL_ARGUMENTS (current_function_decl);
3031        parm; parm = TREE_CHAIN (parm))
3032     {
3033       rtx decl_rtl = DECL_RTL_IF_SET (parm);
3034       rtx incoming = DECL_INCOMING_RTL (parm);
3035       tree decl;
3036       HOST_WIDE_INT offset;
3037       dataflow_set *out;
3038
3039       if (TREE_CODE (parm) != PARM_DECL)
3040         continue;
3041
3042       if (!DECL_NAME (parm))
3043         continue;
3044
3045       if (!decl_rtl || !incoming)
3046         continue;
3047
3048       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
3049         continue;
3050
3051       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
3052         if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
3053           continue;
3054
3055       if (!decl)
3056         continue;
3057
3058       gcc_assert (parm == decl);
3059
3060       out = &VTI (ENTRY_BLOCK_PTR)->out;
3061
3062       if (REG_P (incoming))
3063         {
3064           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
3065           attrs_list_insert (&out->regs[REGNO (incoming)],
3066                              parm, offset, incoming);
3067           set_variable_part (out, incoming, parm, offset, VAR_INIT_STATUS_INITIALIZED,
3068                              NULL);
3069         }
3070       else if (MEM_P (incoming))
3071         set_variable_part (out, incoming, parm, offset, VAR_INIT_STATUS_INITIALIZED,
3072                            NULL);
3073     }
3074 }
3075
3076 /* Allocate and initialize the data structures for variable tracking
3077    and parse the RTL to get the micro operations.  */
3078
3079 static void
3080 vt_initialize (void)
3081 {
3082   basic_block bb;
3083
3084   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
3085
3086   FOR_EACH_BB (bb)
3087     {
3088       rtx insn;
3089       HOST_WIDE_INT pre, post = 0;
3090
3091       /* Count the number of micro operations.  */
3092       VTI (bb)->n_mos = 0;
3093       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3094            insn = NEXT_INSN (insn))
3095         {
3096           if (INSN_P (insn))
3097             {
3098               if (!frame_pointer_needed)
3099                 {
3100                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3101                   if (pre)
3102                     VTI (bb)->n_mos++;
3103                   if (post)
3104                     VTI (bb)->n_mos++;
3105                 }
3106               note_uses (&PATTERN (insn), count_uses_1, insn);
3107               note_stores (PATTERN (insn), count_stores, insn);
3108               if (CALL_P (insn))
3109                 VTI (bb)->n_mos++;
3110             }
3111         }
3112
3113       /* Add the micro-operations to the array.  */
3114       VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
3115       VTI (bb)->n_mos = 0;
3116       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3117            insn = NEXT_INSN (insn))
3118         {
3119           if (INSN_P (insn))
3120             {
3121               int n1, n2;
3122
3123               if (!frame_pointer_needed)
3124                 {
3125                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3126                   if (pre)
3127                     {
3128                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3129
3130                       mo->type = MO_ADJUST;
3131                       mo->u.adjust = pre;
3132                       mo->insn = insn;
3133                     }
3134                 }
3135
3136               n1 = VTI (bb)->n_mos;
3137               note_uses (&PATTERN (insn), add_uses_1, insn);
3138               n2 = VTI (bb)->n_mos - 1;
3139
3140               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
3141               while (n1 < n2)
3142                 {
3143                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
3144                     n1++;
3145                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
3146                     n2--;
3147                   if (n1 < n2)
3148                     {
3149                       micro_operation sw;
3150
3151                       sw = VTI (bb)->mos[n1];
3152                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3153                       VTI (bb)->mos[n2] = sw;
3154                     }
3155                 }
3156
3157               if (CALL_P (insn))
3158                 {
3159                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3160
3161                   mo->type = MO_CALL;
3162                   mo->insn = insn;
3163                 }
3164
3165               n1 = VTI (bb)->n_mos;
3166               /* This will record NEXT_INSN (insn), such that we can
3167                  insert notes before it without worrying about any
3168                  notes that MO_USEs might emit after the insn.  */
3169               note_stores (PATTERN (insn), add_stores, insn);
3170               n2 = VTI (bb)->n_mos - 1;
3171
3172               /* Order the MO_CLOBBERs to be before MO_SETs.  */
3173               while (n1 < n2)
3174                 {
3175                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
3176                     n1++;
3177                   while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET
3178                                      || VTI (bb)->mos[n2].type == MO_COPY))
3179                     n2--;
3180                   if (n1 < n2)
3181                     {
3182                       micro_operation sw;
3183
3184                       sw = VTI (bb)->mos[n1];
3185                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3186                       VTI (bb)->mos[n2] = sw;
3187                     }
3188                 }
3189
3190               if (!frame_pointer_needed && post)
3191                 {
3192                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3193
3194                   mo->type = MO_ADJUST;
3195                   mo->u.adjust = post;
3196                   mo->insn = insn;
3197                 }
3198             }
3199         }
3200     }
3201
3202   /* Init the IN and OUT sets.  */
3203   FOR_ALL_BB (bb)
3204     {
3205       VTI (bb)->visited = false;
3206       dataflow_set_init (&VTI (bb)->in, 7);
3207       dataflow_set_init (&VTI (bb)->out, 7);
3208     }
3209
3210   attrs_pool = create_alloc_pool ("attrs_def pool",
3211                                   sizeof (struct attrs_def), 1024);
3212   var_pool = create_alloc_pool ("variable_def pool",
3213                                 sizeof (struct variable_def), 64);
3214   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
3215                                       sizeof (struct location_chain_def),
3216                                       1024);
3217   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
3218                                    NULL);
3219   vt_add_function_parameters ();
3220 }
3221
3222 /* Free the data structures needed for variable tracking.  */
3223
3224 static void
3225 vt_finalize (void)
3226 {
3227   basic_block bb;
3228
3229   FOR_EACH_BB (bb)
3230     {
3231       free (VTI (bb)->mos);
3232     }
3233
3234   FOR_ALL_BB (bb)
3235     {
3236       dataflow_set_destroy (&VTI (bb)->in);
3237       dataflow_set_destroy (&VTI (bb)->out);
3238     }
3239   free_aux_for_blocks ();
3240   free_alloc_pool (attrs_pool);
3241   free_alloc_pool (var_pool);
3242   free_alloc_pool (loc_chain_pool);
3243   htab_delete (changed_variables);
3244 }
3245
3246 /* The entry point to variable tracking pass.  */
3247
3248 unsigned int
3249 variable_tracking_main (void)
3250 {
3251   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
3252     return 0;
3253
3254   mark_dfs_back_edges ();
3255   vt_initialize ();
3256   if (!frame_pointer_needed)
3257     {
3258       if (!vt_stack_adjustments ())
3259         {
3260           vt_finalize ();
3261           return 0;
3262         }
3263     }
3264
3265   vt_find_locations ();
3266   vt_emit_notes ();
3267
3268   if (dump_file && (dump_flags & TDF_DETAILS))
3269     {
3270       dump_dataflow_sets ();
3271       dump_flow_info (dump_file, dump_flags);
3272     }
3273
3274   vt_finalize ();
3275   return 0;
3276 }
3277 \f
3278 static bool
3279 gate_handle_var_tracking (void)
3280 {
3281   return (flag_var_tracking);
3282 }
3283
3284
3285
3286 struct tree_opt_pass pass_variable_tracking =
3287 {
3288   "vartrack",                           /* name */
3289   gate_handle_var_tracking,             /* gate */
3290   variable_tracking_main,               /* execute */
3291   NULL,                                 /* sub */
3292   NULL,                                 /* next */
3293   0,                                    /* static_pass_number */
3294   TV_VAR_TRACKING,                      /* tv_id */
3295   0,                                    /* properties_required */
3296   0,                                    /* properties_provided */
3297   0,                                    /* properties_destroyed */
3298   0,                                    /* todo_flags_start */
3299   TODO_dump_func,                       /* todo_flags_finish */
3300   'V'                                   /* letter */
3301 };
3302