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