gcc/var-tracking.c

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