gcc/var-tracking.c

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