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