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