gcc/var-tracking.c

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