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                     {
1225                       if (node2->init < node->init)
1226                         node2->init = node->init;
1227                       break;
1228                     }
1229                 }
1230               if (node || node2)
1231                 dst = unshare_variable (set, dst, VAR_INIT_STATUS_UNKNOWN);
1232             }
1233
1234           src_l = 0;
1235           for (node = src->var_part[i].loc_chain; node; node = node->next)
1236             src_l++;
1237           dst_l = 0;
1238           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1239             dst_l++;
1240           vui = XCNEWVEC (struct variable_union_info, src_l + dst_l);
1241
1242           /* Fill in the locations from DST.  */
1243           for (node = dst->var_part[j].loc_chain, jj = 0; node;
1244                node = node->next, jj++)
1245             {
1246               vui[jj].lc = node;
1247               vui[jj].pos_dst = jj;
1248
1249               /* Value larger than a sum of 2 valid positions.  */
1250               vui[jj].pos_src = src_l + dst_l;
1251             }
1252
1253           /* Fill in the locations from SRC.  */
1254           n = dst_l;
1255           for (node = src->var_part[i].loc_chain, ii = 0; node;
1256                node = node->next, ii++)
1257             {
1258               /* Find location from NODE.  */
1259               for (jj = 0; jj < dst_l; jj++)
1260                 {
1261                   if ((REG_P (vui[jj].lc->loc)
1262                        && REG_P (node->loc)
1263                        && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
1264                       || rtx_equal_p (vui[jj].lc->loc, node->loc))
1265                     {
1266                       vui[jj].pos_src = ii;
1267                       break;
1268                     }
1269                 }
1270               if (jj >= dst_l)  /* The location has not been found.  */
1271                 {
1272                   location_chain new_node;
1273
1274                   /* Copy the location from SRC.  */
1275                   new_node = pool_alloc (loc_chain_pool);
1276                   new_node->loc = node->loc;
1277                   new_node->init = node->init;
1278                   if (!node->set_src || MEM_P (node->set_src))
1279                     new_node->set_src = NULL;
1280                   else
1281                     new_node->set_src = node->set_src;
1282                   vui[n].lc = new_node;
1283                   vui[n].pos_src = ii;
1284                   vui[n].pos_dst = src_l + dst_l;
1285                   n++;
1286                 }
1287             }
1288
1289           for (ii = 0; ii < src_l + dst_l; ii++)
1290             vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst;
1291
1292           qsort (vui, n, sizeof (struct variable_union_info),
1293                  variable_union_info_cmp_pos);
1294
1295           /* Reconnect the nodes in sorted order.  */
1296           for (ii = 1; ii < n; ii++)
1297             vui[ii - 1].lc->next = vui[ii].lc;
1298           vui[n - 1].lc->next = NULL;
1299
1300           dst->var_part[k].loc_chain = vui[0].lc;
1301           dst->var_part[k].offset = dst->var_part[j].offset;
1302
1303           free (vui);
1304           i--;
1305           j--;
1306         }
1307       else if ((i >= 0 && j >= 0
1308                 && src->var_part[i].offset < dst->var_part[j].offset)
1309                || i < 0)
1310         {
1311           dst->var_part[k] = dst->var_part[j];
1312           j--;
1313         }
1314       else if ((i >= 0 && j >= 0
1315                 && src->var_part[i].offset > dst->var_part[j].offset)
1316                || j < 0)
1317         {
1318           location_chain *nextp;
1319
1320           /* Copy the chain from SRC.  */
1321           nextp = &dst->var_part[k].loc_chain;
1322           for (node = src->var_part[i].loc_chain; node; node = node->next)
1323             {
1324               location_chain new_lc;
1325
1326               new_lc = pool_alloc (loc_chain_pool);
1327               new_lc->next = NULL;
1328               new_lc->init = node->init;
1329               if (!node->set_src || MEM_P (node->set_src))
1330                 new_lc->set_src = NULL;
1331               else
1332                 new_lc->set_src = node->set_src;
1333               new_lc->loc = node->loc;
1334
1335               *nextp = new_lc;
1336               nextp = &new_lc->next;
1337             }
1338
1339           dst->var_part[k].offset = src->var_part[i].offset;
1340           i--;
1341         }
1342
1343       /* We are at the basic block boundary when computing union
1344          so set the CUR_LOC to be the first element of the chain.  */
1345       if (dst->var_part[k].loc_chain)
1346         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
1347       else
1348         dst->var_part[k].cur_loc = NULL;
1349     }
1350
1351   for (i = 0; i < src->n_var_parts && i < dst->n_var_parts; i++)
1352     {
1353       location_chain node, node2;
1354       for (node = src->var_part[i].loc_chain; node; node = node->next)
1355         for (node2 = dst->var_part[i].loc_chain; node2; node2 = node2->next)
1356           if (rtx_equal_p (node->loc, node2->loc))
1357             {
1358               if (node->init > node2->init)
1359                 node2->init = node->init;
1360             }
1361     }
1362
1363   /* Continue traversing the hash table.  */
1364   return 1;
1365 }
1366
1367 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
1368
1369 static void
1370 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
1371 {
1372   int i;
1373
1374   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1375     attrs_list_union (&dst->regs[i], src->regs[i]);
1376
1377   htab_traverse (src->vars, variable_union, dst);
1378 }
1379
1380 /* Flag whether two dataflow sets being compared contain different data.  */
1381 static bool
1382 dataflow_set_different_value;
1383
1384 static bool
1385 variable_part_different_p (variable_part *vp1, variable_part *vp2)
1386 {
1387   location_chain lc1, lc2;
1388
1389   for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
1390     {
1391       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
1392         {
1393           if (REG_P (lc1->loc) && REG_P (lc2->loc))
1394             {
1395               if (REGNO (lc1->loc) == REGNO (lc2->loc))
1396                 break;
1397             }
1398           if (rtx_equal_p (lc1->loc, lc2->loc))
1399             break;
1400         }
1401       if (!lc2)
1402         return true;
1403     }
1404   return false;
1405 }
1406
1407 /* Return true if variables VAR1 and VAR2 are different.
1408    If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
1409    variable part.  */
1410
1411 static bool
1412 variable_different_p (variable var1, variable var2,
1413                       bool compare_current_location)
1414 {
1415   int i;
1416
1417   if (var1 == var2)
1418     return false;
1419
1420   if (var1->n_var_parts != var2->n_var_parts)
1421     return true;
1422
1423   for (i = 0; i < var1->n_var_parts; i++)
1424     {
1425       if (var1->var_part[i].offset != var2->var_part[i].offset)
1426         return true;
1427       if (compare_current_location)
1428         {
1429           if (!((REG_P (var1->var_part[i].cur_loc)
1430                  && REG_P (var2->var_part[i].cur_loc)
1431                  && (REGNO (var1->var_part[i].cur_loc)
1432                      == REGNO (var2->var_part[i].cur_loc)))
1433                 || rtx_equal_p (var1->var_part[i].cur_loc,
1434                                 var2->var_part[i].cur_loc)))
1435             return true;
1436         }
1437       if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
1438         return true;
1439       if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
1440         return true;
1441     }
1442   return false;
1443 }
1444
1445 /* Compare variable *SLOT with the same variable in hash table DATA
1446    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1447
1448 static int
1449 dataflow_set_different_1 (void **slot, void *data)
1450 {
1451   htab_t htab = (htab_t) data;
1452   variable var1, var2;
1453
1454   var1 = *(variable *) slot;
1455   var2 = htab_find_with_hash (htab, var1->decl,
1456                               VARIABLE_HASH_VAL (var1->decl));
1457   if (!var2)
1458     {
1459       dataflow_set_different_value = true;
1460
1461       /* Stop traversing the hash table.  */
1462       return 0;
1463     }
1464
1465   if (variable_different_p (var1, var2, false))
1466     {
1467       dataflow_set_different_value = true;
1468
1469       /* Stop traversing the hash table.  */
1470       return 0;
1471     }
1472
1473   /* Continue traversing the hash table.  */
1474   return 1;
1475 }
1476
1477 /* Compare variable *SLOT with the same variable in hash table DATA
1478    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1479
1480 static int
1481 dataflow_set_different_2 (void **slot, void *data)
1482 {
1483   htab_t htab = (htab_t) data;
1484   variable var1, var2;
1485
1486   var1 = *(variable *) slot;
1487   var2 = htab_find_with_hash (htab, var1->decl,
1488                               VARIABLE_HASH_VAL (var1->decl));
1489   if (!var2)
1490     {
1491       dataflow_set_different_value = true;
1492
1493       /* Stop traversing the hash table.  */
1494       return 0;
1495     }
1496
1497   /* If both variables are defined they have been already checked for
1498      equivalence.  */
1499   gcc_assert (!variable_different_p (var1, var2, false));
1500
1501   /* Continue traversing the hash table.  */
1502   return 1;
1503 }
1504
1505 /* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
1506
1507 static bool
1508 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
1509 {
1510   dataflow_set_different_value = false;
1511
1512   htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars);
1513   if (!dataflow_set_different_value)
1514     {
1515       /* We have compared the variables which are in both hash tables
1516          so now only check whether there are some variables in NEW_SET->VARS
1517          which are not in OLD_SET->VARS.  */
1518       htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars);
1519     }
1520   return dataflow_set_different_value;
1521 }
1522
1523 /* Free the contents of dataflow set SET.  */
1524
1525 static void
1526 dataflow_set_destroy (dataflow_set *set)
1527 {
1528   int i;
1529
1530   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1531     attrs_list_clear (&set->regs[i]);
1532
1533   htab_delete (set->vars);
1534   set->vars = NULL;
1535 }
1536
1537 /* Return true if RTL X contains a SYMBOL_REF.  */
1538
1539 static bool
1540 contains_symbol_ref (rtx x)
1541 {
1542   const char *fmt;
1543   RTX_CODE code;
1544   int i;
1545
1546   if (!x)
1547     return false;
1548
1549   code = GET_CODE (x);
1550   if (code == SYMBOL_REF)
1551     return true;
1552
1553   fmt = GET_RTX_FORMAT (code);
1554   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1555     {
1556       if (fmt[i] == 'e')
1557         {
1558           if (contains_symbol_ref (XEXP (x, i)))
1559             return true;
1560         }
1561       else if (fmt[i] == 'E')
1562         {
1563           int j;
1564           for (j = 0; j < XVECLEN (x, i); j++)
1565             if (contains_symbol_ref (XVECEXP (x, i, j)))
1566               return true;
1567         }
1568     }
1569
1570   return false;
1571 }
1572
1573 /* Shall EXPR be tracked?  */
1574
1575 static bool
1576 track_expr_p (tree expr)
1577 {
1578   rtx decl_rtl;
1579   tree realdecl;
1580
1581   /* If EXPR is not a parameter or a variable do not track it.  */
1582   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
1583     return 0;
1584
1585   /* It also must have a name...  */
1586   if (!DECL_NAME (expr))
1587     return 0;
1588
1589   /* ... and a RTL assigned to it.  */
1590   decl_rtl = DECL_RTL_IF_SET (expr);
1591   if (!decl_rtl)
1592     return 0;
1593
1594   /* If this expression is really a debug alias of some other declaration, we
1595      don't need to track this expression if the ultimate declaration is
1596      ignored.  */
1597   realdecl = expr;
1598   if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
1599     {
1600       realdecl = DECL_DEBUG_EXPR (realdecl);
1601       /* ??? We don't yet know how to emit DW_OP_piece for variable
1602          that has been SRA'ed.  */
1603       if (!DECL_P (realdecl))
1604         return 0;
1605     }
1606
1607   /* Do not track EXPR if REALDECL it should be ignored for debugging
1608      purposes.  */
1609   if (DECL_IGNORED_P (realdecl))
1610     return 0;
1611
1612   /* Do not track global variables until we are able to emit correct location
1613      list for them.  */
1614   if (TREE_STATIC (realdecl))
1615     return 0;
1616
1617   /* When the EXPR is a DECL for alias of some variable (see example)
1618      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
1619      DECL_RTL contains SYMBOL_REF.
1620
1621      Example:
1622      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
1623      char **_dl_argv;
1624   */
1625   if (MEM_P (decl_rtl)
1626       && contains_symbol_ref (XEXP (decl_rtl, 0)))
1627     return 0;
1628
1629   /* If RTX is a memory it should not be very large (because it would be
1630      an array or struct).  */
1631   if (MEM_P (decl_rtl))
1632     {
1633       /* Do not track structures and arrays.  */
1634       if (GET_MODE (decl_rtl) == BLKmode
1635           || AGGREGATE_TYPE_P (TREE_TYPE (realdecl)))
1636         return 0;
1637       if (MEM_SIZE (decl_rtl)
1638           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
1639         return 0;
1640     }
1641
1642   return 1;
1643 }
1644
1645 /* Determine whether a given LOC refers to the same variable part as
1646    EXPR+OFFSET.  */
1647
1648 static bool
1649 same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset)
1650 {
1651   tree expr2;
1652   HOST_WIDE_INT offset2;
1653
1654   if (! DECL_P (expr))
1655     return false;
1656
1657   if (REG_P (loc))
1658     {
1659       expr2 = REG_EXPR (loc);
1660       offset2 = REG_OFFSET (loc);
1661     }
1662   else if (MEM_P (loc))
1663     {
1664       expr2 = MEM_EXPR (loc);
1665       offset2 = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0;
1666     }
1667   else
1668     return false;
1669
1670   if (! expr2 || ! DECL_P (expr2))
1671     return false;
1672
1673   expr = var_debug_decl (expr);
1674   expr2 = var_debug_decl (expr2);
1675
1676   return (expr == expr2 && offset == offset2);
1677 }
1678
1679 /* REG is a register we want to track.  If not all of REG contains useful
1680    information, return the mode of the lowpart that does contain useful
1681    information, otherwise return the mode of REG.
1682
1683    If REG was a paradoxical subreg, its REG_ATTRS will describe the
1684    whole subreg, but only the old inner part is really relevant.  */
1685
1686 static enum machine_mode
1687 mode_for_reg_attrs (rtx reg)
1688 {
1689   enum machine_mode mode;
1690
1691   mode = GET_MODE (reg);
1692   if (!HARD_REGISTER_NUM_P (ORIGINAL_REGNO (reg)))
1693     {
1694       enum machine_mode pseudo_mode;
1695
1696       pseudo_mode = PSEUDO_REGNO_MODE (ORIGINAL_REGNO (reg));
1697       if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (pseudo_mode))
1698         mode = pseudo_mode;
1699     }
1700   return mode;
1701 }
1702
1703 /* Return the MODE lowpart of LOC, or null if LOC is not something we
1704    want to track.  When returning nonnull, make sure that the attributes
1705    on the returned value are updated.  */
1706
1707 static rtx
1708 var_lowpart (enum machine_mode mode, rtx loc)
1709 {
1710   unsigned int offset, regno;
1711
1712   if (!REG_P (loc) && !MEM_P (loc))
1713     return NULL;
1714
1715   if (GET_MODE (loc) == mode)
1716     return loc;
1717
1718   offset = subreg_lowpart_offset (mode, GET_MODE (loc));
1719
1720   if (MEM_P (loc))
1721     return adjust_address_nv (loc, mode, offset);
1722
1723   regno = REGNO (loc) + subreg_regno_offset (REGNO (loc), GET_MODE (loc),
1724                                              offset, mode);
1725   return gen_rtx_REG_offset (loc, mode, regno, offset);
1726 }
1727
1728 /* Count uses (register and memory references) LOC which will be tracked.
1729    INSN is instruction which the LOC is part of.  */
1730
1731 static int
1732 count_uses (rtx *loc, void *insn)
1733 {
1734   basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1735
1736   if (REG_P (*loc))
1737     {
1738       gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER);
1739       VTI (bb)->n_mos++;
1740     }
1741   else if (MEM_P (*loc)
1742            && MEM_EXPR (*loc)
1743            && track_expr_p (MEM_EXPR (*loc)))
1744     {
1745       VTI (bb)->n_mos++;
1746     }
1747
1748   return 0;
1749 }
1750
1751 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1752
1753 static void
1754 count_uses_1 (rtx *x, void *insn)
1755 {
1756   for_each_rtx (x, count_uses, insn);
1757 }
1758
1759 /* Count stores (register and memory references) LOC which will be tracked.
1760    INSN is instruction which the LOC is part of.  */
1761
1762 static void
1763 count_stores (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *insn)
1764 {
1765   count_uses (&loc, insn);
1766 }
1767
1768 /* Add uses (register and memory references) LOC which will be tracked
1769    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
1770
1771 static int
1772 add_uses (rtx *loc, void *insn)
1773 {
1774   if (REG_P (*loc))
1775     {
1776       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1777       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1778
1779       if (REG_EXPR (*loc) && track_expr_p (REG_EXPR (*loc)))
1780         {
1781           mo->type = MO_USE;
1782           mo->u.loc = var_lowpart (mode_for_reg_attrs (*loc), *loc);
1783         }
1784       else
1785         {
1786           mo->type = MO_USE_NO_VAR;
1787           mo->u.loc = *loc;
1788         }
1789       mo->insn = (rtx) insn;
1790     }
1791   else if (MEM_P (*loc)
1792            && MEM_EXPR (*loc)
1793            && track_expr_p (MEM_EXPR (*loc)))
1794     {
1795       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1796       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1797
1798       mo->type = MO_USE;
1799       mo->u.loc = *loc;
1800       mo->insn = (rtx) insn;
1801     }
1802
1803   return 0;
1804 }
1805
1806 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1807
1808 static void
1809 add_uses_1 (rtx *x, void *insn)
1810 {
1811   for_each_rtx (x, add_uses, insn);
1812 }
1813
1814 /* Add stores (register and memory references) LOC which will be tracked
1815    to VTI (bb)->mos. EXPR is the RTL expression containing the store.
1816    INSN is instruction which the LOC is part of.  */
1817
1818 static void
1819 add_stores (rtx loc, const_rtx expr, void *insn)
1820 {
1821   if (REG_P (loc))
1822     {
1823       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1824       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1825
1826       if (GET_CODE (expr) == CLOBBER
1827           || ! REG_EXPR (loc)
1828           || ! track_expr_p (REG_EXPR (loc)))
1829         {
1830           mo->type = MO_CLOBBER;
1831           mo->u.loc = loc;
1832         }
1833       else
1834         {
1835           enum machine_mode mode = mode_for_reg_attrs (loc);
1836           rtx src = NULL;
1837
1838           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
1839             src = var_lowpart (mode, SET_SRC (expr));
1840           loc = var_lowpart (mode, loc);
1841
1842           if (src == NULL)
1843             {
1844               mo->type = MO_SET;
1845               mo->u.loc = loc;
1846             }
1847           else
1848             {
1849               if (SET_SRC (expr) != src)
1850                 expr = gen_rtx_SET (VOIDmode, loc, src);
1851               if (same_variable_part_p (src, REG_EXPR (loc), REG_OFFSET (loc)))
1852                 mo->type = MO_COPY;
1853               else
1854                 mo->type = MO_SET;
1855               mo->u.loc = CONST_CAST_RTX (expr);
1856             }
1857         }
1858       mo->insn = (rtx) insn;
1859     }
1860   else if (MEM_P (loc)
1861            && MEM_EXPR (loc)
1862            && track_expr_p (MEM_EXPR (loc)))
1863     {
1864       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1865       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1866
1867       if (GET_CODE (expr) == CLOBBER)
1868         {
1869           mo->type = MO_CLOBBER;
1870           mo->u.loc = loc;
1871         }
1872       else
1873         {
1874           rtx src = NULL;
1875
1876           if (GET_CODE (expr) == SET && SET_DEST (expr) == loc)
1877             src = var_lowpart (GET_MODE (loc), SET_SRC (expr));
1878
1879           if (src == NULL)
1880             {
1881               mo->type = MO_SET;
1882               mo->u.loc = loc;
1883             }
1884           else
1885             {
1886               if (same_variable_part_p (SET_SRC (expr),
1887                                         MEM_EXPR (loc),
1888                                         MEM_OFFSET (loc)
1889                                         ? INTVAL (MEM_OFFSET (loc)) : 0))
1890                 mo->type = MO_COPY;
1891               else
1892                 mo->type = MO_SET;
1893               mo->u.loc = CONST_CAST_RTX (expr);
1894             }
1895         }
1896       mo->insn = (rtx) insn;
1897     }
1898 }
1899
1900 static enum var_init_status
1901 find_src_status (dataflow_set *in, rtx src)
1902 {
1903   tree decl = NULL_TREE;
1904   enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
1905
1906   if (! flag_var_tracking_uninit)
1907     status = VAR_INIT_STATUS_INITIALIZED;
1908
1909   if (src && REG_P (src))
1910     decl = var_debug_decl (REG_EXPR (src));
1911   else if (src && MEM_P (src))
1912     decl = var_debug_decl (MEM_EXPR (src));
1913
1914   if (src && decl)
1915     status = get_init_value (in, src, decl);
1916
1917   return status;
1918 }
1919
1920 /* SRC is the source of an assignment.  Use SET to try to find what
1921    was ultimately assigned to SRC.  Return that value if known,
1922    otherwise return SRC itself.  */
1923
1924 static rtx
1925 find_src_set_src (dataflow_set *set, rtx src)
1926 {
1927   tree decl = NULL_TREE;   /* The variable being copied around.          */
1928   rtx set_src = NULL_RTX;  /* The value for "decl" stored in "src".      */
1929   void **slot;
1930   variable var;
1931   location_chain nextp;
1932   int i;
1933   bool found;
1934
1935   if (src && REG_P (src))
1936     decl = var_debug_decl (REG_EXPR (src));
1937   else if (src && MEM_P (src))
1938     decl = var_debug_decl (MEM_EXPR (src));
1939
1940   if (src && decl)
1941     {
1942       slot = htab_find_slot_with_hash (set->vars, decl,
1943                                        VARIABLE_HASH_VAL (decl), NO_INSERT);
1944
1945       if (slot)
1946         {
1947           var = *(variable *) slot;
1948           found = false;
1949           for (i = 0; i < var->n_var_parts && !found; i++)
1950             for (nextp = var->var_part[i].loc_chain; nextp && !found;
1951                  nextp = nextp->next)
1952               if (rtx_equal_p (nextp->loc, src))
1953                 {
1954                   set_src = nextp->set_src;
1955                   found = true;
1956                 }
1957
1958         }
1959     }
1960
1961   return set_src;
1962 }
1963
1964 /* Compute the changes of variable locations in the basic block BB.  */
1965
1966 static bool
1967 compute_bb_dataflow (basic_block bb)
1968 {
1969   int i, n, r;
1970   bool changed;
1971   dataflow_set old_out;
1972   dataflow_set *in = &VTI (bb)->in;
1973   dataflow_set *out = &VTI (bb)->out;
1974
1975   dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
1976   dataflow_set_copy (&old_out, out);
1977   dataflow_set_copy (out, in);
1978
1979   n = VTI (bb)->n_mos;
1980   for (i = 0; i < n; i++)
1981     {
1982       switch (VTI (bb)->mos[i].type)
1983         {
1984           case MO_CALL:
1985             for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1986               if (TEST_HARD_REG_BIT (call_used_reg_set, r))
1987                 var_regno_delete (out, r);
1988             break;
1989
1990           case MO_USE:
1991             {
1992               rtx loc = VTI (bb)->mos[i].u.loc;
1993               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
1994
1995               if (! flag_var_tracking_uninit)
1996                 status = VAR_INIT_STATUS_INITIALIZED;
1997
1998               if (GET_CODE (loc) == REG)
1999                 var_reg_set (out, loc, status, NULL);
2000               else if (GET_CODE (loc) == MEM)
2001                 var_mem_set (out, loc, status, NULL);
2002             }
2003             break;
2004
2005           case MO_SET:
2006             {
2007               rtx loc = VTI (bb)->mos[i].u.loc;
2008               rtx set_src = NULL;
2009
2010               if (GET_CODE (loc) == SET)
2011                 {
2012                   set_src = SET_SRC (loc);
2013                   loc = SET_DEST (loc);
2014                 }
2015
2016               if (REG_P (loc))
2017                 var_reg_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
2018                                         set_src);
2019               else if (MEM_P (loc))
2020                 var_mem_delete_and_set (out, loc, true, VAR_INIT_STATUS_INITIALIZED,
2021                                         set_src);
2022             }
2023             break;
2024
2025           case MO_COPY:
2026             {
2027               rtx loc = VTI (bb)->mos[i].u.loc;
2028               enum var_init_status src_status;
2029               rtx set_src = NULL;
2030
2031               if (GET_CODE (loc) == SET)
2032                 {
2033                   set_src = SET_SRC (loc);
2034                   loc = SET_DEST (loc);
2035                 }
2036
2037               if (! flag_var_tracking_uninit)
2038                 src_status = VAR_INIT_STATUS_INITIALIZED;
2039               else
2040                 src_status = find_src_status (in, set_src);
2041
2042               if (src_status == VAR_INIT_STATUS_UNKNOWN)
2043                 src_status = find_src_status (out, set_src);
2044
2045               set_src = find_src_set_src (in, set_src);
2046
2047               if (REG_P (loc))
2048                 var_reg_delete_and_set (out, loc, false, src_status, set_src);
2049               else if (MEM_P (loc))
2050                 var_mem_delete_and_set (out, loc, false, src_status, set_src);
2051             }
2052             break;
2053
2054           case MO_USE_NO_VAR:
2055             {
2056               rtx loc = VTI (bb)->mos[i].u.loc;
2057
2058               if (REG_P (loc))
2059                 var_reg_delete (out, loc, false);
2060               else if (MEM_P (loc))
2061                 var_mem_delete (out, loc, false);
2062             }
2063             break;
2064
2065           case MO_CLOBBER:
2066             {
2067               rtx loc = VTI (bb)->mos[i].u.loc;
2068
2069               if (REG_P (loc))
2070                 var_reg_delete (out, loc, true);
2071               else if (MEM_P (loc))
2072                 var_mem_delete (out, loc, true);
2073             }
2074             break;
2075
2076           case MO_ADJUST:
2077             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
2078             break;
2079         }
2080     }
2081
2082   changed = dataflow_set_different (&old_out, out);
2083   dataflow_set_destroy (&old_out);
2084   return changed;
2085 }
2086
2087 /* Find the locations of variables in the whole function.  */
2088
2089 static void
2090 vt_find_locations (void)
2091 {
2092   fibheap_t worklist, pending, fibheap_swap;
2093   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
2094   basic_block bb;
2095   edge e;
2096   int *bb_order;
2097   int *rc_order;
2098   int i;
2099
2100   /* Compute reverse completion order of depth first search of the CFG
2101      so that the data-flow runs faster.  */
2102   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
2103   bb_order = XNEWVEC (int, last_basic_block);
2104   pre_and_rev_post_order_compute (NULL, rc_order, false);
2105   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
2106     bb_order[rc_order[i]] = i;
2107   free (rc_order);
2108
2109   worklist = fibheap_new ();
2110   pending = fibheap_new ();
2111   visited = sbitmap_alloc (last_basic_block);
2112   in_worklist = sbitmap_alloc (last_basic_block);
2113   in_pending = sbitmap_alloc (last_basic_block);
2114   sbitmap_zero (in_worklist);
2115
2116   FOR_EACH_BB (bb)
2117     fibheap_insert (pending, bb_order[bb->index], bb);
2118   sbitmap_ones (in_pending);
2119
2120   while (!fibheap_empty (pending))
2121     {
2122       fibheap_swap = pending;
2123       pending = worklist;
2124       worklist = fibheap_swap;
2125       sbitmap_swap = in_pending;
2126       in_pending = in_worklist;
2127       in_worklist = sbitmap_swap;
2128
2129       sbitmap_zero (visited);
2130
2131       while (!fibheap_empty (worklist))
2132         {
2133           bb = fibheap_extract_min (worklist);
2134           RESET_BIT (in_worklist, bb->index);
2135           if (!TEST_BIT (visited, bb->index))
2136             {
2137               bool changed;
2138               edge_iterator ei;
2139
2140               SET_BIT (visited, bb->index);
2141
2142               /* Calculate the IN set as union of predecessor OUT sets.  */
2143               dataflow_set_clear (&VTI (bb)->in);
2144               FOR_EACH_EDGE (e, ei, bb->preds)
2145                 {
2146                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
2147                 }
2148
2149               changed = compute_bb_dataflow (bb);
2150               if (changed)
2151                 {
2152                   FOR_EACH_EDGE (e, ei, bb->succs)
2153                     {
2154                       if (e->dest == EXIT_BLOCK_PTR)
2155                         continue;
2156
2157                       if (e->dest == bb)
2158                         continue;
2159
2160                       if (TEST_BIT (visited, e->dest->index))
2161                         {
2162                           if (!TEST_BIT (in_pending, e->dest->index))
2163                             {
2164                               /* Send E->DEST to next round.  */
2165                               SET_BIT (in_pending, e->dest->index);
2166                               fibheap_insert (pending,
2167                                               bb_order[e->dest->index],
2168                                               e->dest);
2169                             }
2170                         }
2171                       else if (!TEST_BIT (in_worklist, e->dest->index))
2172                         {
2173                           /* Add E->DEST to current round.  */
2174                           SET_BIT (in_worklist, e->dest->index);
2175                           fibheap_insert (worklist, bb_order[e->dest->index],
2176                                           e->dest);
2177                         }
2178                     }
2179                 }
2180             }
2181         }
2182     }
2183
2184   free (bb_order);
2185   fibheap_delete (worklist);
2186   fibheap_delete (pending);
2187   sbitmap_free (visited);
2188   sbitmap_free (in_worklist);
2189   sbitmap_free (in_pending);
2190 }
2191
2192 /* Print the content of the LIST to dump file.  */
2193
2194 static void
2195 dump_attrs_list (attrs list)
2196 {
2197   for (; list; list = list->next)
2198     {
2199       print_mem_expr (dump_file, list->decl);
2200       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
2201     }
2202   fprintf (dump_file, "\n");
2203 }
2204
2205 /* Print the information about variable *SLOT to dump file.  */
2206
2207 static int
2208 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
2209 {
2210   variable var = *(variable *) slot;
2211   int i;
2212   location_chain node;
2213
2214   fprintf (dump_file, "  name: %s",
2215            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
2216   if (dump_flags & TDF_UID)
2217     fprintf (dump_file, " D.%u\n", DECL_UID (var->decl));
2218   else
2219     fprintf (dump_file, "\n");
2220
2221   for (i = 0; i < var->n_var_parts; i++)
2222     {
2223       fprintf (dump_file, "    offset %ld\n",
2224                (long) var->var_part[i].offset);
2225       for (node = var->var_part[i].loc_chain; node; node = node->next)
2226         {
2227           fprintf (dump_file, "      ");
2228           if (node->init == VAR_INIT_STATUS_UNINITIALIZED)
2229             fprintf (dump_file, "[uninit]");
2230           print_rtl_single (dump_file, node->loc);
2231         }
2232     }
2233
2234   /* Continue traversing the hash table.  */
2235   return 1;
2236 }
2237
2238 /* Print the information about variables from hash table VARS to dump file.  */
2239
2240 static void
2241 dump_vars (htab_t vars)
2242 {
2243   if (htab_elements (vars) > 0)
2244     {
2245       fprintf (dump_file, "Variables:\n");
2246       htab_traverse (vars, dump_variable, NULL);
2247     }
2248 }
2249
2250 /* Print the dataflow set SET to dump file.  */
2251
2252 static void
2253 dump_dataflow_set (dataflow_set *set)
2254 {
2255   int i;
2256
2257   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
2258            set->stack_adjust);
2259   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2260     {
2261       if (set->regs[i])
2262         {
2263           fprintf (dump_file, "Reg %d:", i);
2264           dump_attrs_list (set->regs[i]);
2265         }
2266     }
2267   dump_vars (set->vars);
2268   fprintf (dump_file, "\n");
2269 }
2270
2271 /* Print the IN and OUT sets for each basic block to dump file.  */
2272
2273 static void
2274 dump_dataflow_sets (void)
2275 {
2276   basic_block bb;
2277
2278   FOR_EACH_BB (bb)
2279     {
2280       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
2281       fprintf (dump_file, "IN:\n");
2282       dump_dataflow_set (&VTI (bb)->in);
2283       fprintf (dump_file, "OUT:\n");
2284       dump_dataflow_set (&VTI (bb)->out);
2285     }
2286 }
2287
2288 /* Add variable VAR to the hash table of changed variables and
2289    if it has no locations delete it from hash table HTAB.  */
2290
2291 static void
2292 variable_was_changed (variable var, htab_t htab)
2293 {
2294   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
2295
2296   if (emit_notes)
2297     {
2298       variable *slot;
2299
2300       slot = (variable *) htab_find_slot_with_hash (changed_variables,
2301                                                     var->decl, hash, INSERT);
2302
2303       if (htab && var->n_var_parts == 0)
2304         {
2305           variable empty_var;
2306           void **old;
2307
2308           empty_var = pool_alloc (var_pool);
2309           empty_var->decl = var->decl;
2310           empty_var->refcount = 1;
2311           empty_var->n_var_parts = 0;
2312           *slot = empty_var;
2313
2314           old = htab_find_slot_with_hash (htab, var->decl, hash,
2315                                           NO_INSERT);
2316           if (old)
2317             htab_clear_slot (htab, old);
2318         }
2319       else
2320         {
2321           *slot = var;
2322         }
2323     }
2324   else
2325     {
2326       gcc_assert (htab);
2327       if (var->n_var_parts == 0)
2328         {
2329           void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
2330                                                   NO_INSERT);
2331           if (slot)
2332             htab_clear_slot (htab, slot);
2333         }
2334     }
2335 }
2336
2337 /* Look for the index in VAR->var_part corresponding to OFFSET.
2338    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
2339    referenced int will be set to the index that the part has or should
2340    have, if it should be inserted.  */
2341
2342 static inline int
2343 find_variable_location_part (variable var, HOST_WIDE_INT offset,
2344                              int *insertion_point)
2345 {
2346   int pos, low, high;
2347
2348   /* Find the location part.  */
2349   low = 0;
2350   high = var->n_var_parts;
2351   while (low != high)
2352     {
2353       pos = (low + high) / 2;
2354       if (var->var_part[pos].offset < offset)
2355         low = pos + 1;
2356       else
2357         high = pos;
2358     }
2359   pos = low;
2360
2361   if (insertion_point)
2362     *insertion_point = pos;
2363
2364   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2365     return pos;
2366
2367   return -1;
2368 }
2369
2370 /* Set the part of variable's location in the dataflow set SET.  The variable
2371    part is specified by variable's declaration DECL and offset OFFSET and the
2372    part's location by LOC.  */
2373
2374 static void
2375 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset,
2376                    enum var_init_status initialized, rtx set_src)
2377 {
2378   int pos;
2379   location_chain node, next;
2380   location_chain *nextp;
2381   variable var;
2382   void **slot;
2383
2384   slot = htab_find_slot_with_hash (set->vars, decl,
2385                                    VARIABLE_HASH_VAL (decl), INSERT);
2386   if (!*slot)
2387     {
2388       /* Create new variable information.  */
2389       var = pool_alloc (var_pool);
2390       var->decl = decl;
2391       var->refcount = 1;
2392       var->n_var_parts = 1;
2393       var->var_part[0].offset = offset;
2394       var->var_part[0].loc_chain = NULL;
2395       var->var_part[0].cur_loc = NULL;
2396       *slot = var;
2397       pos = 0;
2398     }
2399   else
2400     {
2401       int inspos = 0;
2402
2403       var = (variable) *slot;
2404
2405       pos = find_variable_location_part (var, offset, &inspos);
2406
2407       if (pos >= 0)
2408         {
2409           node = var->var_part[pos].loc_chain;
2410
2411           if (node
2412               && ((REG_P (node->loc) && REG_P (loc)
2413                    && REGNO (node->loc) == REGNO (loc))
2414                   || rtx_equal_p (node->loc, loc)))
2415             {
2416               /* LOC is in the beginning of the chain so we have nothing
2417                  to do.  */
2418               if (node->init < initialized)
2419                 node->init = initialized;
2420               if (set_src != NULL)
2421                 node->set_src = set_src;
2422
2423               *slot = var;
2424               return;
2425             }
2426           else
2427             {
2428               /* We have to make a copy of a shared variable.  */
2429               if (var->refcount > 1)
2430                 var = unshare_variable (set, var, initialized);
2431             }
2432         }
2433       else
2434         {
2435           /* We have not found the location part, new one will be created.  */
2436
2437           /* We have to make a copy of the shared variable.  */
2438           if (var->refcount > 1)
2439             var = unshare_variable (set, var, initialized);
2440
2441           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2442              thus there are at most MAX_VAR_PARTS different offsets.  */
2443           gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
2444
2445           /* We have to move the elements of array starting at index
2446              inspos to the next position.  */
2447           for (pos = var->n_var_parts; pos > inspos; pos--)
2448             var->var_part[pos] = var->var_part[pos - 1];
2449
2450           var->n_var_parts++;
2451           var->var_part[pos].offset = offset;
2452           var->var_part[pos].loc_chain = NULL;
2453           var->var_part[pos].cur_loc = NULL;
2454         }
2455     }
2456
2457   /* Delete the location from the list.  */
2458   nextp = &var->var_part[pos].loc_chain;
2459   for (node = var->var_part[pos].loc_chain; node; node = next)
2460     {
2461       next = node->next;
2462       if ((REG_P (node->loc) && REG_P (loc)
2463            && REGNO (node->loc) == REGNO (loc))
2464           || rtx_equal_p (node->loc, loc))
2465         {
2466           /* Save these values, to assign to the new node, before
2467              deleting this one.  */
2468           if (node->init > initialized)
2469             initialized = node->init;
2470           if (node->set_src != NULL && set_src == NULL)
2471             set_src = node->set_src;
2472           pool_free (loc_chain_pool, node);
2473           *nextp = next;
2474           break;
2475         }
2476       else
2477         nextp = &node->next;
2478     }
2479
2480   /* Add the location to the beginning.  */
2481   node = pool_alloc (loc_chain_pool);
2482   node->loc = loc;
2483   node->init = initialized;
2484   node->set_src = set_src;
2485   node->next = var->var_part[pos].loc_chain;
2486   var->var_part[pos].loc_chain = node;
2487
2488   /* If no location was emitted do so.  */
2489   if (var->var_part[pos].cur_loc == NULL)
2490     {
2491       var->var_part[pos].cur_loc = loc;
2492       variable_was_changed (var, set->vars);
2493     }
2494 }
2495
2496 /* Remove all recorded register locations for the given variable part
2497    from dataflow set SET, except for those that are identical to loc.
2498    The variable part is specified by variable's declaration DECL and
2499    offset OFFSET.  */
2500
2501 static void
2502 clobber_variable_part (dataflow_set *set, rtx loc, tree decl,
2503                        HOST_WIDE_INT offset, rtx set_src)
2504 {
2505   void **slot;
2506
2507   if (! decl || ! DECL_P (decl))
2508     return;
2509
2510   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2511                                    NO_INSERT);
2512   if (slot)
2513     {
2514       variable var = (variable) *slot;
2515       int pos = find_variable_location_part (var, offset, NULL);
2516
2517       if (pos >= 0)
2518         {
2519           location_chain node, next;
2520
2521           /* Remove the register locations from the dataflow set.  */
2522           next = var->var_part[pos].loc_chain;
2523           for (node = next; node; node = next)
2524             {
2525               next = node->next;
2526               if (node->loc != loc
2527                   && (!flag_var_tracking_uninit
2528                       || !set_src
2529                       || MEM_P (set_src)
2530                       || !rtx_equal_p (set_src, node->set_src)))
2531                 {
2532                   if (REG_P (node->loc))
2533                     {
2534                       attrs anode, anext;
2535                       attrs *anextp;
2536
2537                       /* Remove the variable part from the register's
2538                          list, but preserve any other variable parts
2539                          that might be regarded as live in that same
2540                          register.  */
2541                       anextp = &set->regs[REGNO (node->loc)];
2542                       for (anode = *anextp; anode; anode = anext)
2543                         {
2544                           anext = anode->next;
2545                           if (anode->decl == decl
2546                               && anode->offset == offset)
2547                             {
2548                               pool_free (attrs_pool, anode);
2549                               *anextp = anext;
2550                             }
2551                         }
2552                     }
2553
2554                   delete_variable_part (set, node->loc, decl, offset);
2555                 }
2556             }
2557         }
2558     }
2559 }
2560
2561 /* Delete the part of variable's location from dataflow set SET.  The variable
2562    part is specified by variable's declaration DECL and offset OFFSET and the
2563    part's location by LOC.  */
2564
2565 static void
2566 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2567                       HOST_WIDE_INT offset)
2568 {
2569   void **slot;
2570
2571   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2572                                    NO_INSERT);
2573   if (slot)
2574     {
2575       variable var = (variable) *slot;
2576       int pos = find_variable_location_part (var, offset, NULL);
2577
2578       if (pos >= 0)
2579         {
2580           location_chain node, next;
2581           location_chain *nextp;
2582           bool changed;
2583
2584           if (var->refcount > 1)
2585             {
2586               /* If the variable contains the location part we have to
2587                  make a copy of the variable.  */
2588               for (node = var->var_part[pos].loc_chain; node;
2589                    node = node->next)
2590                 {
2591                   if ((REG_P (node->loc) && REG_P (loc)
2592                        && REGNO (node->loc) == REGNO (loc))
2593                       || rtx_equal_p (node->loc, loc))
2594                     {
2595                       enum var_init_status status = VAR_INIT_STATUS_UNKNOWN;
2596                       if (! flag_var_tracking_uninit)
2597                         status = VAR_INIT_STATUS_INITIALIZED;
2598                       var = unshare_variable (set, var, status);
2599                       break;
2600                     }
2601                 }
2602             }
2603
2604           /* Delete the location part.  */
2605           nextp = &var->var_part[pos].loc_chain;
2606           for (node = *nextp; node; node = next)
2607             {
2608               next = node->next;
2609               if ((REG_P (node->loc) && REG_P (loc)
2610                    && REGNO (node->loc) == REGNO (loc))
2611                   || rtx_equal_p (node->loc, loc))
2612                 {
2613                   pool_free (loc_chain_pool, node);
2614                   *nextp = next;
2615                   break;
2616                 }
2617               else
2618                 nextp = &node->next;
2619             }
2620
2621           /* If we have deleted the location which was last emitted
2622              we have to emit new location so add the variable to set
2623              of changed variables.  */
2624           if (var->var_part[pos].cur_loc
2625               && ((REG_P (loc)
2626                    && REG_P (var->var_part[pos].cur_loc)
2627                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2628                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2629             {
2630               changed = true;
2631               if (var->var_part[pos].loc_chain)
2632                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2633             }
2634           else
2635             changed = false;
2636
2637           if (var->var_part[pos].loc_chain == NULL)
2638             {
2639               var->n_var_parts--;
2640               while (pos < var->n_var_parts)
2641                 {
2642                   var->var_part[pos] = var->var_part[pos + 1];
2643                   pos++;
2644                 }
2645             }
2646           if (changed)
2647             variable_was_changed (var, set->vars);
2648         }
2649     }
2650 }
2651
2652 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2653    additional parameters: WHERE specifies whether the note shall be emitted
2654    before of after instruction INSN.  */
2655
2656 static int
2657 emit_note_insn_var_location (void **varp, void *data)
2658 {
2659   variable var = *(variable *) varp;
2660   rtx insn = ((emit_note_data *)data)->insn;
2661   enum emit_note_where where = ((emit_note_data *)data)->where;
2662   rtx note;
2663   int i, j, n_var_parts;
2664   bool complete;
2665   enum var_init_status initialized = VAR_INIT_STATUS_UNINITIALIZED;
2666   HOST_WIDE_INT last_limit;
2667   tree type_size_unit;
2668   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2669   rtx loc[MAX_VAR_PARTS];
2670
2671   gcc_assert (var->decl);
2672
2673   if (! flag_var_tracking_uninit)
2674     initialized = VAR_INIT_STATUS_INITIALIZED;
2675
2676   complete = true;
2677   last_limit = 0;
2678   n_var_parts = 0;
2679   for (i = 0; i < var->n_var_parts; i++)
2680     {
2681       enum machine_mode mode, wider_mode;
2682
2683       if (last_limit < var->var_part[i].offset)
2684         {
2685           complete = false;
2686           break;
2687         }
2688       else if (last_limit > var->var_part[i].offset)
2689         continue;
2690       offsets[n_var_parts] = var->var_part[i].offset;
2691       loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2692       mode = GET_MODE (loc[n_var_parts]);
2693       initialized = var->var_part[i].loc_chain->init;
2694       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2695
2696       /* Attempt to merge adjacent registers or memory.  */
2697       wider_mode = GET_MODE_WIDER_MODE (mode);
2698       for (j = i + 1; j < var->n_var_parts; j++)
2699         if (last_limit <= var->var_part[j].offset)
2700           break;
2701       if (j < var->n_var_parts
2702           && wider_mode != VOIDmode
2703           && GET_CODE (loc[n_var_parts])
2704              == GET_CODE (var->var_part[j].loc_chain->loc)
2705           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2706           && last_limit == var->var_part[j].offset)
2707         {
2708           rtx new_loc = NULL;
2709           rtx loc2 = var->var_part[j].loc_chain->loc;
2710
2711           if (REG_P (loc[n_var_parts])
2712               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2713                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2714               && end_hard_regno (mode, REGNO (loc[n_var_parts]))
2715                  == REGNO (loc2))
2716             {
2717               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2718                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2719                                            mode, 0);
2720               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2721                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2722               if (new_loc)
2723                 {
2724                   if (!REG_P (new_loc)
2725                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2726                     new_loc = NULL;
2727                   else
2728                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2729                 }
2730             }
2731           else if (MEM_P (loc[n_var_parts])
2732                    && GET_CODE (XEXP (loc2, 0)) == PLUS
2733                    && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2734                    && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2735             {
2736               if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2737                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2738                                    XEXP (XEXP (loc2, 0), 0))
2739                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
2740                       == GET_MODE_SIZE (mode))
2741                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2742                       && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2743                          == CONST_INT
2744                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2745                                       XEXP (XEXP (loc2, 0), 0))
2746                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2747                          + GET_MODE_SIZE (mode)
2748                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2749                 new_loc = adjust_address_nv (loc[n_var_parts],
2750                                              wider_mode, 0);
2751             }
2752
2753           if (new_loc)
2754             {
2755               loc[n_var_parts] = new_loc;
2756               mode = wider_mode;
2757               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2758               i = j;
2759             }
2760         }
2761       ++n_var_parts;
2762     }
2763   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2764   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2765     complete = false;
2766
2767   if (where == EMIT_NOTE_AFTER_INSN)
2768     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2769   else
2770     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2771
2772   if (! flag_var_tracking_uninit)
2773     initialized = VAR_INIT_STATUS_INITIALIZED;
2774
2775   if (!complete)
2776     {
2777       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2778                                                        NULL_RTX, (int) initialized);
2779     }
2780   else if (n_var_parts == 1)
2781     {
2782       rtx expr_list
2783         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
2784
2785       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2786                                                        expr_list,
2787                                                        (int) initialized);
2788     }
2789   else if (n_var_parts)
2790     {
2791       rtx parallel;
2792
2793       for (i = 0; i < n_var_parts; i++)
2794         loc[i]
2795           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
2796
2797       parallel = gen_rtx_PARALLEL (VOIDmode,
2798                                    gen_rtvec_v (n_var_parts, loc));
2799       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2800                                                        parallel,
2801                                                        (int) initialized);
2802     }
2803
2804   htab_clear_slot (changed_variables, varp);
2805
2806   /* When there are no location parts the variable has been already
2807      removed from hash table and a new empty variable was created.
2808      Free the empty variable.  */
2809   if (var->n_var_parts == 0)
2810     {
2811       pool_free (var_pool, var);
2812     }
2813
2814   /* Continue traversing the hash table.  */
2815   return 1;
2816 }
2817
2818 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2819    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
2820    shall be emitted before of after instruction INSN.  */
2821
2822 static void
2823 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2824 {
2825   emit_note_data data;
2826
2827   data.insn = insn;
2828   data.where = where;
2829   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2830 }
2831
2832 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2833    same variable in hash table DATA or is not there at all.  */
2834
2835 static int
2836 emit_notes_for_differences_1 (void **slot, void *data)
2837 {
2838   htab_t new_vars = (htab_t) data;
2839   variable old_var, new_var;
2840
2841   old_var = *(variable *) slot;
2842   new_var = htab_find_with_hash (new_vars, old_var->decl,
2843                                  VARIABLE_HASH_VAL (old_var->decl));
2844
2845   if (!new_var)
2846     {
2847       /* Variable has disappeared.  */
2848       variable empty_var;
2849
2850       empty_var = pool_alloc (var_pool);
2851       empty_var->decl = old_var->decl;
2852       empty_var->refcount = 1;
2853       empty_var->n_var_parts = 0;
2854       variable_was_changed (empty_var, NULL);
2855     }
2856   else if (variable_different_p (old_var, new_var, true))
2857     {
2858       variable_was_changed (new_var, NULL);
2859     }
2860
2861   /* Continue traversing the hash table.  */
2862   return 1;
2863 }
2864
2865 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2866    table DATA.  */
2867
2868 static int
2869 emit_notes_for_differences_2 (void **slot, void *data)
2870 {
2871   htab_t old_vars = (htab_t) data;
2872   variable old_var, new_var;
2873
2874   new_var = *(variable *) slot;
2875   old_var = htab_find_with_hash (old_vars, new_var->decl,
2876                                  VARIABLE_HASH_VAL (new_var->decl));
2877   if (!old_var)
2878     {
2879       /* Variable has appeared.  */
2880       variable_was_changed (new_var, NULL);
2881     }
2882
2883   /* Continue traversing the hash table.  */
2884   return 1;
2885 }
2886
2887 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2888    NEW_SET.  */
2889
2890 static void
2891 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2892                             dataflow_set *new_set)
2893 {
2894   htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2895   htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2896   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2897 }
2898
2899 /* Emit the notes for changes of location parts in the basic block BB.  */
2900
2901 static void
2902 emit_notes_in_bb (basic_block bb)
2903 {
2904   int i;
2905   dataflow_set set;
2906
2907   dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2908   dataflow_set_copy (&set, &VTI (bb)->in);
2909
2910   for (i = 0; i < VTI (bb)->n_mos; i++)
2911     {
2912       rtx insn = VTI (bb)->mos[i].insn;
2913
2914       switch (VTI (bb)->mos[i].type)
2915         {
2916           case MO_CALL:
2917             {
2918               int r;
2919
2920               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2921                 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2922                   {
2923                     var_regno_delete (&set, r);
2924                   }
2925               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2926             }
2927             break;
2928
2929           case MO_USE:
2930             {
2931               rtx loc = VTI (bb)->mos[i].u.loc;
2932
2933               enum var_init_status status = VAR_INIT_STATUS_UNINITIALIZED;
2934               if (! flag_var_tracking_uninit)
2935                 status = VAR_INIT_STATUS_INITIALIZED;
2936               if (GET_CODE (loc) == REG)
2937                 var_reg_set (&set, loc, status, NULL);
2938               else
2939                 var_mem_set (&set, loc, status, NULL);
2940
2941               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2942             }
2943             break;
2944
2945           case MO_SET:
2946             {
2947               rtx loc = VTI (bb)->mos[i].u.loc;
2948               rtx set_src = NULL;
2949
2950               if (GET_CODE (loc) == SET)
2951                 {
2952                   set_src = SET_SRC (loc);
2953                   loc = SET_DEST (loc);
2954                 }
2955
2956               if (REG_P (loc))
2957                 var_reg_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
2958                                         set_src);
2959               else
2960                 var_mem_delete_and_set (&set, loc, true, VAR_INIT_STATUS_INITIALIZED,
2961                                         set_src);
2962
2963               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
2964             }
2965             break;
2966
2967           case MO_COPY:
2968             {
2969               rtx loc = VTI (bb)->mos[i].u.loc;
2970               enum var_init_status src_status;
2971               rtx set_src = NULL;
2972
2973               if (GET_CODE (loc) == SET)
2974                 {
2975                   set_src = SET_SRC (loc);
2976                   loc = SET_DEST (loc);
2977                 }
2978
2979               src_status = find_src_status (&set, set_src);
2980               set_src = find_src_set_src (&set, set_src);
2981
2982               if (REG_P (loc))
2983                 var_reg_delete_and_set (&set, loc, false, src_status, set_src);
2984               else
2985                 var_mem_delete_and_set (&set, loc, false, src_status, set_src);
2986
2987               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
2988             }
2989             break;
2990
2991           case MO_USE_NO_VAR:
2992             {
2993               rtx loc = VTI (bb)->mos[i].u.loc;
2994
2995               if (REG_P (loc))
2996                 var_reg_delete (&set, loc, false);
2997               else
2998                 var_mem_delete (&set, loc, false);
2999
3000               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
3001             }
3002             break;
3003
3004           case MO_CLOBBER:
3005             {
3006               rtx loc = VTI (bb)->mos[i].u.loc;
3007
3008               if (REG_P (loc))
3009                 var_reg_delete (&set, loc, true);
3010               else
3011                 var_mem_delete (&set, loc, true);
3012
3013               emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN);
3014             }
3015             break;
3016
3017           case MO_ADJUST:
3018             set.stack_adjust += VTI (bb)->mos[i].u.adjust;
3019             break;
3020         }
3021     }
3022   dataflow_set_destroy (&set);
3023 }
3024
3025 /* Emit notes for the whole function.  */
3026
3027 static void
3028 vt_emit_notes (void)
3029 {
3030   basic_block bb;
3031   dataflow_set *last_out;
3032   dataflow_set empty;
3033
3034   gcc_assert (!htab_elements (changed_variables));
3035
3036   /* Enable emitting notes by functions (mainly by set_variable_part and
3037      delete_variable_part).  */
3038   emit_notes = true;
3039
3040   dataflow_set_init (&empty, 7);
3041   last_out = &empty;
3042
3043   FOR_EACH_BB (bb)
3044     {
3045       /* Emit the notes for changes of variable locations between two
3046          subsequent basic blocks.  */
3047       emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
3048
3049       /* Emit the notes for the changes in the basic block itself.  */
3050       emit_notes_in_bb (bb);
3051
3052       last_out = &VTI (bb)->out;
3053     }
3054   dataflow_set_destroy (&empty);
3055   emit_notes = false;
3056 }
3057
3058 /* If there is a declaration and offset associated with register/memory RTL
3059    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
3060
3061 static bool
3062 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
3063 {
3064   if (REG_P (rtl))
3065     {
3066       if (REG_ATTRS (rtl))
3067         {
3068           *declp = REG_EXPR (rtl);
3069           *offsetp = REG_OFFSET (rtl);
3070           return true;
3071         }
3072     }
3073   else if (MEM_P (rtl))
3074     {
3075       if (MEM_ATTRS (rtl))
3076         {
3077           *declp = MEM_EXPR (rtl);
3078           *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0;
3079           return true;
3080         }
3081     }
3082   return false;
3083 }
3084
3085 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
3086
3087 static void
3088 vt_add_function_parameters (void)
3089 {
3090   tree parm;
3091
3092   for (parm = DECL_ARGUMENTS (current_function_decl);
3093        parm; parm = TREE_CHAIN (parm))
3094     {
3095       rtx decl_rtl = DECL_RTL_IF_SET (parm);
3096       rtx incoming = DECL_INCOMING_RTL (parm);
3097       tree decl;
3098       HOST_WIDE_INT offset;
3099       dataflow_set *out;
3100
3101       if (TREE_CODE (parm) != PARM_DECL)
3102         continue;
3103
3104       if (!DECL_NAME (parm))
3105         continue;
3106
3107       if (!decl_rtl || !incoming)
3108         continue;
3109
3110       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
3111         continue;
3112
3113       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
3114         if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
3115           continue;
3116
3117       if (!decl)
3118         continue;
3119
3120       gcc_assert (parm == decl);
3121
3122       out = &VTI (ENTRY_BLOCK_PTR)->out;
3123
3124       if (REG_P (incoming))
3125         {
3126           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
3127           attrs_list_insert (&out->regs[REGNO (incoming)],
3128                              parm, offset, incoming);
3129           set_variable_part (out, incoming, parm, offset, VAR_INIT_STATUS_INITIALIZED,
3130                              NULL);
3131         }
3132       else if (MEM_P (incoming))
3133         set_variable_part (out, incoming, parm, offset, VAR_INIT_STATUS_INITIALIZED,
3134                            NULL);
3135     }
3136 }
3137
3138 /* Allocate and initialize the data structures for variable tracking
3139    and parse the RTL to get the micro operations.  */
3140
3141 static void
3142 vt_initialize (void)
3143 {
3144   basic_block bb;
3145
3146   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
3147
3148   FOR_EACH_BB (bb)
3149     {
3150       rtx insn;
3151       HOST_WIDE_INT pre, post = 0;
3152
3153       /* Count the number of micro operations.  */
3154       VTI (bb)->n_mos = 0;
3155       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3156            insn = NEXT_INSN (insn))
3157         {
3158           if (INSN_P (insn))
3159             {
3160               if (!frame_pointer_needed)
3161                 {
3162                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3163                   if (pre)
3164                     VTI (bb)->n_mos++;
3165                   if (post)
3166                     VTI (bb)->n_mos++;
3167                 }
3168               note_uses (&PATTERN (insn), count_uses_1, insn);
3169               note_stores (PATTERN (insn), count_stores, insn);
3170               if (CALL_P (insn))
3171                 VTI (bb)->n_mos++;
3172             }
3173         }
3174
3175       /* Add the micro-operations to the array.  */
3176       VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
3177       VTI (bb)->n_mos = 0;
3178       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
3179            insn = NEXT_INSN (insn))
3180         {
3181           if (INSN_P (insn))
3182             {
3183               int n1, n2;
3184
3185               if (!frame_pointer_needed)
3186                 {
3187                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
3188                   if (pre)
3189                     {
3190                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3191
3192                       mo->type = MO_ADJUST;
3193                       mo->u.adjust = pre;
3194                       mo->insn = insn;
3195                     }
3196                 }
3197
3198               n1 = VTI (bb)->n_mos;
3199               note_uses (&PATTERN (insn), add_uses_1, insn);
3200               n2 = VTI (bb)->n_mos - 1;
3201
3202               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
3203               while (n1 < n2)
3204                 {
3205                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
3206                     n1++;
3207                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
3208                     n2--;
3209                   if (n1 < n2)
3210                     {
3211                       micro_operation sw;
3212
3213                       sw = VTI (bb)->mos[n1];
3214                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3215                       VTI (bb)->mos[n2] = sw;
3216                     }
3217                 }
3218
3219               if (CALL_P (insn))
3220                 {
3221                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3222
3223                   mo->type = MO_CALL;
3224                   mo->insn = insn;
3225                 }
3226
3227               n1 = VTI (bb)->n_mos;
3228               /* This will record NEXT_INSN (insn), such that we can
3229                  insert notes before it without worrying about any
3230                  notes that MO_USEs might emit after the insn.  */
3231               note_stores (PATTERN (insn), add_stores, insn);
3232               n2 = VTI (bb)->n_mos - 1;
3233
3234               /* Order the MO_CLOBBERs to be before MO_SETs.  */
3235               while (n1 < n2)
3236                 {
3237                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
3238                     n1++;
3239                   while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET
3240                                      || VTI (bb)->mos[n2].type == MO_COPY))
3241                     n2--;
3242                   if (n1 < n2)
3243                     {
3244                       micro_operation sw;
3245
3246                       sw = VTI (bb)->mos[n1];
3247                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
3248                       VTI (bb)->mos[n2] = sw;
3249                     }
3250                 }
3251
3252               if (!frame_pointer_needed && post)
3253                 {
3254                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
3255
3256                   mo->type = MO_ADJUST;
3257                   mo->u.adjust = post;
3258                   mo->insn = insn;
3259                 }
3260             }
3261         }
3262     }
3263
3264   /* Init the IN and OUT sets.  */
3265   FOR_ALL_BB (bb)
3266     {
3267       VTI (bb)->visited = false;
3268       dataflow_set_init (&VTI (bb)->in, 7);
3269       dataflow_set_init (&VTI (bb)->out, 7);
3270     }
3271
3272   attrs_pool = create_alloc_pool ("attrs_def pool",
3273                                   sizeof (struct attrs_def), 1024);
3274   var_pool = create_alloc_pool ("variable_def pool",
3275                                 sizeof (struct variable_def), 64);
3276   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
3277                                       sizeof (struct location_chain_def),
3278                                       1024);
3279   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
3280                                    NULL);
3281   vt_add_function_parameters ();
3282 }
3283
3284 /* Free the data structures needed for variable tracking.  */
3285
3286 static void
3287 vt_finalize (void)
3288 {
3289   basic_block bb;
3290
3291   FOR_EACH_BB (bb)
3292     {
3293       free (VTI (bb)->mos);
3294     }
3295
3296   FOR_ALL_BB (bb)
3297     {
3298       dataflow_set_destroy (&VTI (bb)->in);
3299       dataflow_set_destroy (&VTI (bb)->out);
3300     }
3301   free_aux_for_blocks ();
3302   free_alloc_pool (attrs_pool);
3303   free_alloc_pool (var_pool);
3304   free_alloc_pool (loc_chain_pool);
3305   htab_delete (changed_variables);
3306 }
3307
3308 /* The entry point to variable tracking pass.  */
3309
3310 unsigned int
3311 variable_tracking_main (void)
3312 {
3313   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
3314     return 0;
3315
3316   mark_dfs_back_edges ();
3317   vt_initialize ();
3318   if (!frame_pointer_needed)
3319     {
3320       if (!vt_stack_adjustments ())
3321         {
3322           vt_finalize ();
3323           return 0;
3324         }
3325     }
3326
3327   vt_find_locations ();
3328   vt_emit_notes ();
3329
3330   if (dump_file && (dump_flags & TDF_DETAILS))
3331     {
3332       dump_dataflow_sets ();
3333       dump_flow_info (dump_file, dump_flags);
3334     }
3335
3336   vt_finalize ();
3337   return 0;
3338 }
3339 \f
3340 static bool
3341 gate_handle_var_tracking (void)
3342 {
3343   return (flag_var_tracking);
3344 }
3345
3346
3347
3348 struct tree_opt_pass pass_variable_tracking =
3349 {
3350   "vartrack",                           /* name */
3351   gate_handle_var_tracking,             /* gate */
3352   variable_tracking_main,               /* execute */
3353   NULL,                                 /* sub */
3354   NULL,                                 /* next */
3355   0,                                    /* static_pass_number */
3356   TV_VAR_TRACKING,                      /* tv_id */
3357   0,                                    /* properties_required */
3358   0,                                    /* properties_provided */
3359   0,                                    /* properties_destroyed */
3360   0,                                    /* todo_flags_start */
3361   TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
3362   'V'                                   /* letter */
3363 };
3364