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 flow_depth_first_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 = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 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   adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl);
 561   cfa = plus_constant (arg_pointer_rtx, adjustment);
 562
 563   addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa);
 564   tmp = simplify_rtx (addr);
 565   if (tmp)
 566     addr = tmp;
 567
 568   return replace_equiv_address_nv (mem, addr);
 569 }
 570
 571 /* The hash function for variable_htab, computes the hash value
 572    from the declaration of variable X.  */
 573
 574 static hashval_t
 575 variable_htab_hash (const void *x)
 576 {
 577   const variable v = (const variable) x;
 578
 579   return (VARIABLE_HASH_VAL (v->decl));
 580 }
 581
 582 /* Compare the declaration of variable X with declaration Y.  */
 583
 584 static int
 585 variable_htab_eq (const void *x, const void *y)
 586 {
 587   const variable v = (const variable) x;
 588   const tree decl = (const tree) y;
 589
 590   return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl));
 591 }
 592
 593 /* Free the element of VARIABLE_HTAB (its type is struct variable_def).  */
 594
 595 static void
 596 variable_htab_free (void *elem)
 597 {
 598   int i;
 599   variable var = (variable) elem;
 600   location_chain node, next;
 601
 602   gcc_assert (var->refcount > 0);
 603
 604   var->refcount--;
 605   if (var->refcount > 0)
 606     return;
 607
 608   for (i = 0; i < var->n_var_parts; i++)
 609     {
 610       for (node = var->var_part[i].loc_chain; node; node = next)
 611         {
 612           next = node->next;
 613           pool_free (loc_chain_pool, node);
 614         }
 615       var->var_part[i].loc_chain = NULL;
 616     }
 617   pool_free (var_pool, var);
 618 }
 619
 620 /* Initialize the set (array) SET of attrs to empty lists.  */
 621
 622 static void
 623 init_attrs_list_set (attrs *set)
 624 {
 625   int i;
 626
 627   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 628     set[i] = NULL;
 629 }
 630
 631 /* Make the list *LISTP empty.  */
 632
 633 static void
 634 attrs_list_clear (attrs *listp)
 635 {
 636   attrs list, next;
 637
 638   for (list = *listp; list; list = next)
 639     {
 640       next = list->next;
 641       pool_free (attrs_pool, list);
 642     }
 643   *listp = NULL;
 644 }
 645
 646 /* Return true if the pair of DECL and OFFSET is the member of the LIST.  */
 647
 648 static attrs
 649 attrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset)
 650 {
 651   for (; list; list = list->next)
 652     if (list->decl == decl && list->offset == offset)
 653       return list;
 654   return NULL;
 655 }
 656
 657 /* Insert the triplet DECL, OFFSET, LOC to the list *LISTP.  */
 658
 659 static void
 660 attrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc)
 661 {
 662   attrs list;
 663
 664   list = pool_alloc (attrs_pool);
 665   list->loc = loc;
 666   list->decl = decl;
 667   list->offset = offset;
 668   list->next = *listp;
 669   *listp = list;
 670 }
 671
 672 /* Copy all nodes from SRC and create a list *DSTP of the copies.  */
 673
 674 static void
 675 attrs_list_copy (attrs *dstp, attrs src)
 676 {
 677   attrs n;
 678
 679   attrs_list_clear (dstp);
 680   for (; src; src = src->next)
 681     {
 682       n = pool_alloc (attrs_pool);
 683       n->loc = src->loc;
 684       n->decl = src->decl;
 685       n->offset = src->offset;
 686       n->next = *dstp;
 687       *dstp = n;
 688     }
 689 }
 690
 691 /* Add all nodes from SRC which are not in *DSTP to *DSTP.  */
 692
 693 static void
 694 attrs_list_union (attrs *dstp, attrs src)
 695 {
 696   for (; src; src = src->next)
 697     {
 698       if (!attrs_list_member (*dstp, src->decl, src->offset))
 699         attrs_list_insert (dstp, src->decl, src->offset, src->loc);
 700     }
 701 }
 702
 703 /* Delete all variables from hash table VARS.  */
 704
 705 static void
 706 vars_clear (htab_t vars)
 707 {
 708   htab_empty (vars);
 709 }
 710
 711 /* Return a copy of a variable VAR and insert it to dataflow set SET.  */
 712
 713 static variable
 714 unshare_variable (dataflow_set *set, variable var)
 715 {
 716   void **slot;
 717   variable new_var;
 718   int i;
 719
 720   new_var = pool_alloc (var_pool);
 721   new_var->decl = var->decl;
 722   new_var->refcount = 1;
 723   var->refcount--;
 724   new_var->n_var_parts = var->n_var_parts;
 725
 726   for (i = 0; i < var->n_var_parts; i++)
 727     {
 728       location_chain node;
 729       location_chain *nextp;
 730
 731       new_var->var_part[i].offset = var->var_part[i].offset;
 732       nextp = &new_var->var_part[i].loc_chain;
 733       for (node = var->var_part[i].loc_chain; node; node = node->next)
 734         {
 735           location_chain new_lc;
 736
 737           new_lc = pool_alloc (loc_chain_pool);
 738           new_lc->next = NULL;
 739           new_lc->loc = node->loc;
 740
 741           *nextp = new_lc;
 742           nextp = &new_lc->next;
 743         }
 744
 745       /* We are at the basic block boundary when copying variable description
 746          so set the CUR_LOC to be the first element of the chain.  */
 747       if (new_var->var_part[i].loc_chain)
 748         new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc;
 749       else
 750         new_var->var_part[i].cur_loc = NULL;
 751     }
 752
 753   slot = htab_find_slot_with_hash (set->vars, new_var->decl,
 754                                    VARIABLE_HASH_VAL (new_var->decl),
 755                                    INSERT);
 756   *slot = new_var;
 757   return new_var;
 758 }
 759
 760 /* Add a variable from *SLOT to hash table DATA and increase its reference
 761    count.  */
 762
 763 static int
 764 vars_copy_1 (void **slot, void *data)
 765 {
 766   htab_t dst = (htab_t) data;
 767   variable src, *dstp;
 768
 769   src = *(variable *) slot;
 770   src->refcount++;
 771
 772   dstp = (variable *) htab_find_slot_with_hash (dst, src->decl,
 773                                                 VARIABLE_HASH_VAL (src->decl),
 774                                                 INSERT);
 775   *dstp = src;
 776
 777   /* Continue traversing the hash table.  */
 778   return 1;
 779 }
 780
 781 /* Copy all variables from hash table SRC to hash table DST.  */
 782
 783 static void
 784 vars_copy (htab_t dst, htab_t src)
 785 {
 786   vars_clear (dst);
 787   htab_traverse (src, vars_copy_1, dst);
 788 }
 789
 790 /* Delete current content of register LOC in dataflow set SET
 791    and set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC).  */
 792
 793 static void
 794 var_reg_delete_and_set (dataflow_set *set, rtx loc)
 795 {
 796   tree decl = REG_EXPR (loc);
 797   HOST_WIDE_INT offset = REG_OFFSET (loc);
 798   attrs node, next;
 799   attrs *nextp;
 800
 801   nextp = &set->regs[REGNO (loc)];
 802   for (node = *nextp; node; node = next)
 803     {
 804       next = node->next;
 805       if (node->decl != decl || node->offset != offset)
 806         {
 807           delete_variable_part (set, node->loc, node->decl, node->offset);
 808           pool_free (attrs_pool, node);
 809           *nextp = next;
 810         }
 811       else
 812         {
 813           node->loc = loc;
 814           nextp = &node->next;
 815         }
 816     }
 817   if (set->regs[REGNO (loc)] == NULL)
 818     attrs_list_insert (&set->regs[REGNO (loc)], decl, offset, loc);
 819   set_variable_part (set, loc, decl, offset);
 820 }
 821
 822 /* Delete current content of register LOC in dataflow set SET.  */
 823
 824 static void
 825 var_reg_delete (dataflow_set *set, rtx loc)
 826 {
 827   attrs *reg = &set->regs[REGNO (loc)];
 828   attrs node, next;
 829
 830   for (node = *reg; node; node = next)
 831     {
 832       next = node->next;
 833       delete_variable_part (set, node->loc, node->decl, node->offset);
 834       pool_free (attrs_pool, node);
 835     }
 836   *reg = NULL;
 837 }
 838
 839 /* Delete content of register with number REGNO in dataflow set SET.  */
 840
 841 static void
 842 var_regno_delete (dataflow_set *set, int regno)
 843 {
 844   attrs *reg = &set->regs[regno];
 845   attrs node, next;
 846
 847   for (node = *reg; node; node = next)
 848     {
 849       next = node->next;
 850       delete_variable_part (set, node->loc, node->decl, node->offset);
 851       pool_free (attrs_pool, node);
 852     }
 853   *reg = NULL;
 854 }
 855
 856 /* Delete and set the location part of variable MEM_EXPR (LOC)
 857    in dataflow set SET to LOC.
 858    Adjust the address first if it is stack pointer based.  */
 859
 860 static void
 861 var_mem_delete_and_set (dataflow_set *set, rtx loc)
 862 {
 863   tree decl = MEM_EXPR (loc);
 864   HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0;
 865
 866   set_variable_part (set, loc, decl, offset);
 867 }
 868
 869 /* Delete the location part LOC from dataflow set SET.
 870    Adjust the address first if it is stack pointer based.  */
 871
 872 static void
 873 var_mem_delete (dataflow_set *set, rtx loc)
 874 {
 875   tree decl = MEM_EXPR (loc);
 876   HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0;
 877
 878   delete_variable_part (set, loc, decl, offset);
 879 }
 880
 881 /* Initialize dataflow set SET to be empty.
 882    VARS_SIZE is the initial size of hash table VARS.  */
 883
 884 static void
 885 dataflow_set_init (dataflow_set *set, int vars_size)
 886 {
 887   init_attrs_list_set (set->regs);
 888   set->vars = htab_create (vars_size, variable_htab_hash, variable_htab_eq,
 889                            variable_htab_free);
 890   set->stack_adjust = 0;
 891 }
 892
 893 /* Delete the contents of dataflow set SET.  */
 894
 895 static void
 896 dataflow_set_clear (dataflow_set *set)
 897 {
 898   int i;
 899
 900   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 901     attrs_list_clear (&set->regs[i]);
 902
 903   vars_clear (set->vars);
 904 }
 905
 906 /* Copy the contents of dataflow set SRC to DST.  */
 907
 908 static void
 909 dataflow_set_copy (dataflow_set *dst, dataflow_set *src)
 910 {
 911   int i;
 912
 913   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 914     attrs_list_copy (&dst->regs[i], src->regs[i]);
 915
 916   vars_copy (dst->vars, src->vars);
 917   dst->stack_adjust = src->stack_adjust;
 918 }
 919
 920 /* Information for merging lists of locations for a given offset of variable.
 921  */
 922 struct variable_union_info
 923 {
 924   /* Node of the location chain.  */
 925   location_chain lc;
 926
 927   /* The sum of positions in the input chains.  */
 928   int pos;
 929
 930   /* The position in the chains of SRC and DST dataflow sets.  */
 931   int pos_src;
 932   int pos_dst;
 933 };
 934
 935 /* Compare function for qsort, order the structures by POS element.  */
 936
 937 static int
 938 variable_union_info_cmp_pos (const void *n1, const void *n2)
 939 {
 940   const struct variable_union_info *i1 = n1;
 941   const struct variable_union_info *i2 = n2;
 942
 943   if (i1->pos != i2->pos)
 944     return i1->pos - i2->pos;
 945
 946   return (i1->pos_dst - i2->pos_dst);
 947 }
 948
 949 /* Compute union of location parts of variable *SLOT and the same variable
 950    from hash table DATA.  Compute "sorted" union of the location chains
 951    for common offsets, i.e. the locations of a variable part are sorted by
 952    a priority where the priority is the sum of the positions in the 2 chains
 953    (if a location is only in one list the position in the second list is
 954    defined to be larger than the length of the chains).
 955    When we are updating the location parts the newest location is in the
 956    beginning of the chain, so when we do the described "sorted" union
 957    we keep the newest locations in the beginning.  */
 958
 959 static int
 960 variable_union (void **slot, void *data)
 961 {
 962   variable src, dst, *dstp;
 963   dataflow_set *set = (dataflow_set *) data;
 964   int i, j, k;
 965
 966   src = *(variable *) slot;
 967   dstp = (variable *) htab_find_slot_with_hash (set->vars, src->decl,
 968                                                 VARIABLE_HASH_VAL (src->decl),
 969                                                 INSERT);
 970   if (!*dstp)
 971     {
 972       src->refcount++;
 973
 974       /* If CUR_LOC of some variable part is not the first element of
 975          the location chain we are going to change it so we have to make
 976          a copy of the variable.  */
 977       for (k = 0; k < src->n_var_parts; k++)
 978         {
 979           gcc_assert (!src->var_part[k].loc_chain
 980                       == !src->var_part[k].cur_loc);
 981           if (src->var_part[k].loc_chain)
 982             {
 983               gcc_assert (src->var_part[k].cur_loc);
 984               if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc)
 985                 break;
 986             }
 987         }
 988       if (k < src->n_var_parts)
 989         unshare_variable (set, src);
 990       else
 991         *dstp = src;
 992
 993       /* Continue traversing the hash table.  */
 994       return 1;
 995     }
 996   else
 997     dst = *dstp;
 998
 999   gcc_assert (src->n_var_parts);
1000
1001   /* Count the number of location parts, result is K.  */
1002   for (i = 0, j = 0, k = 0;
1003        i < src->n_var_parts && j < dst->n_var_parts; k++)
1004     {
1005       if (src->var_part[i].offset == dst->var_part[j].offset)
1006         {
1007           i++;
1008           j++;
1009         }
1010       else if (src->var_part[i].offset < dst->var_part[j].offset)
1011         i++;
1012       else
1013         j++;
1014     }
1015   k += src->n_var_parts - i;
1016   k += dst->n_var_parts - j;
1017
1018   /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1019      thus there are at most MAX_VAR_PARTS different offsets.  */
1020   gcc_assert (k <= MAX_VAR_PARTS);
1021
1022   if (dst->refcount > 1 && dst->n_var_parts != k)
1023     dst = unshare_variable (set, dst);
1024
1025   i = src->n_var_parts - 1;
1026   j = dst->n_var_parts - 1;
1027   dst->n_var_parts = k;
1028
1029   for (k--; k >= 0; k--)
1030     {
1031       location_chain node, node2;
1032
1033       if (i >= 0 && j >= 0
1034           && src->var_part[i].offset == dst->var_part[j].offset)
1035         {
1036           /* Compute the "sorted" union of the chains, i.e. the locations which
1037              are in both chains go first, they are sorted by the sum of
1038              positions in the chains.  */
1039           int dst_l, src_l;
1040           int ii, jj, n;
1041           struct variable_union_info *vui;
1042
1043           /* If DST is shared compare the location chains.
1044              If they are different we will modify the chain in DST with
1045              high probability so make a copy of DST.  */
1046           if (dst->refcount > 1)
1047             {
1048               for (node = src->var_part[i].loc_chain,
1049                    node2 = dst->var_part[j].loc_chain; node && node2;
1050                    node = node->next, node2 = node2->next)
1051                 {
1052                   if (!((REG_P (node2->loc)
1053                          && REG_P (node->loc)
1054                          && REGNO (node2->loc) == REGNO (node->loc))
1055                         || rtx_equal_p (node2->loc, node->loc)))
1056                     break;
1057                 }
1058               if (node || node2)
1059                 dst = unshare_variable (set, dst);
1060             }
1061
1062           src_l = 0;
1063           for (node = src->var_part[i].loc_chain; node; node = node->next)
1064             src_l++;
1065           dst_l = 0;
1066           for (node = dst->var_part[j].loc_chain; node; node = node->next)
1067             dst_l++;
1068           vui = xcalloc (src_l + dst_l, sizeof (struct variable_union_info));
1069
1070           /* Fill in the locations from DST.  */
1071           for (node = dst->var_part[j].loc_chain, jj = 0; node;
1072                node = node->next, jj++)
1073             {
1074               vui[jj].lc = node;
1075               vui[jj].pos_dst = jj;
1076
1077               /* Value larger than a sum of 2 valid positions.  */
1078               vui[jj].pos_src = src_l + dst_l;
1079             }
1080
1081           /* Fill in the locations from SRC.  */
1082           n = dst_l;
1083           for (node = src->var_part[i].loc_chain, ii = 0; node;
1084                node = node->next, ii++)
1085             {
1086               /* Find location from NODE.  */
1087               for (jj = 0; jj < dst_l; jj++)
1088                 {
1089                   if ((REG_P (vui[jj].lc->loc)
1090                        && REG_P (node->loc)
1091                        && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
1092                       || rtx_equal_p (vui[jj].lc->loc, node->loc))
1093                     {
1094                       vui[jj].pos_src = ii;
1095                       break;
1096                     }
1097                 }
1098               if (jj >= dst_l)  /* The location has not been found.  */
1099                 {
1100                   location_chain new_node;
1101
1102                   /* Copy the location from SRC.  */
1103                   new_node = pool_alloc (loc_chain_pool);
1104                   new_node->loc = node->loc;
1105                   vui[n].lc = new_node;
1106                   vui[n].pos_src = ii;
1107                   vui[n].pos_dst = src_l + dst_l;
1108                   n++;
1109                 }
1110             }
1111
1112           for (ii = 0; ii < src_l + dst_l; ii++)
1113             vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst;
1114
1115           qsort (vui, n, sizeof (struct variable_union_info),
1116                  variable_union_info_cmp_pos);
1117
1118           /* Reconnect the nodes in sorted order.  */
1119           for (ii = 1; ii < n; ii++)
1120             vui[ii - 1].lc->next = vui[ii].lc;
1121           vui[n - 1].lc->next = NULL;
1122
1123           dst->var_part[k].loc_chain = vui[0].lc;
1124           dst->var_part[k].offset = dst->var_part[j].offset;
1125
1126           free (vui);
1127           i--;
1128           j--;
1129         }
1130       else if ((i >= 0 && j >= 0
1131                 && src->var_part[i].offset < dst->var_part[j].offset)
1132                || i < 0)
1133         {
1134           dst->var_part[k] = dst->var_part[j];
1135           j--;
1136         }
1137       else if ((i >= 0 && j >= 0
1138                 && src->var_part[i].offset > dst->var_part[j].offset)
1139                || j < 0)
1140         {
1141           location_chain *nextp;
1142
1143           /* Copy the chain from SRC.  */
1144           nextp = &dst->var_part[k].loc_chain;
1145           for (node = src->var_part[i].loc_chain; node; node = node->next)
1146             {
1147               location_chain new_lc;
1148
1149               new_lc = pool_alloc (loc_chain_pool);
1150               new_lc->next = NULL;
1151               new_lc->loc = node->loc;
1152
1153               *nextp = new_lc;
1154               nextp = &new_lc->next;
1155             }
1156
1157           dst->var_part[k].offset = src->var_part[i].offset;
1158           i--;
1159         }
1160
1161       /* We are at the basic block boundary when computing union
1162          so set the CUR_LOC to be the first element of the chain.  */
1163       if (dst->var_part[k].loc_chain)
1164         dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc;
1165       else
1166         dst->var_part[k].cur_loc = NULL;
1167     }
1168
1169   /* Continue traversing the hash table.  */
1170   return 1;
1171 }
1172
1173 /* Compute union of dataflow sets SRC and DST and store it to DST.  */
1174
1175 static void
1176 dataflow_set_union (dataflow_set *dst, dataflow_set *src)
1177 {
1178   int i;
1179
1180   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1181     attrs_list_union (&dst->regs[i], src->regs[i]);
1182
1183   htab_traverse (src->vars, variable_union, dst);
1184 }
1185
1186 /* Flag whether two dataflow sets being compared contain different data.  */
1187 static bool
1188 dataflow_set_different_value;
1189
1190 static bool
1191 variable_part_different_p (variable_part *vp1, variable_part *vp2)
1192 {
1193   location_chain lc1, lc2;
1194
1195   for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next)
1196     {
1197       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
1198         {
1199           if (REG_P (lc1->loc) && REG_P (lc2->loc))
1200             {
1201               if (REGNO (lc1->loc) == REGNO (lc2->loc))
1202                 break;
1203             }
1204           if (rtx_equal_p (lc1->loc, lc2->loc))
1205             break;
1206         }
1207       if (!lc2)
1208         return true;
1209     }
1210   return false;
1211 }
1212
1213 /* Return true if variables VAR1 and VAR2 are different.
1214    If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each
1215    variable part.  */
1216
1217 static bool
1218 variable_different_p (variable var1, variable var2,
1219                       bool compare_current_location)
1220 {
1221   int i;
1222
1223   if (var1 == var2)
1224     return false;
1225
1226   if (var1->n_var_parts != var2->n_var_parts)
1227     return true;
1228
1229   for (i = 0; i < var1->n_var_parts; i++)
1230     {
1231       if (var1->var_part[i].offset != var2->var_part[i].offset)
1232         return true;
1233       if (compare_current_location)
1234         {
1235           if (!((REG_P (var1->var_part[i].cur_loc)
1236                  && REG_P (var2->var_part[i].cur_loc)
1237                  && (REGNO (var1->var_part[i].cur_loc)
1238                      == REGNO (var2->var_part[i].cur_loc)))
1239                 || rtx_equal_p (var1->var_part[i].cur_loc,
1240                                 var2->var_part[i].cur_loc)))
1241             return true;
1242         }
1243       if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i]))
1244         return true;
1245       if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i]))
1246         return true;
1247     }
1248   return false;
1249 }
1250
1251 /* Compare variable *SLOT with the same variable in hash table DATA
1252    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1253
1254 static int
1255 dataflow_set_different_1 (void **slot, void *data)
1256 {
1257   htab_t htab = (htab_t) data;
1258   variable var1, var2;
1259
1260   var1 = *(variable *) slot;
1261   var2 = htab_find_with_hash (htab, var1->decl,
1262                               VARIABLE_HASH_VAL (var1->decl));
1263   if (!var2)
1264     {
1265       dataflow_set_different_value = true;
1266
1267       /* Stop traversing the hash table.  */
1268       return 0;
1269     }
1270
1271   if (variable_different_p (var1, var2, false))
1272     {
1273       dataflow_set_different_value = true;
1274
1275       /* Stop traversing the hash table.  */
1276       return 0;
1277     }
1278
1279   /* Continue traversing the hash table.  */
1280   return 1;
1281 }
1282
1283 /* Compare variable *SLOT with the same variable in hash table DATA
1284    and set DATAFLOW_SET_DIFFERENT_VALUE if they are different.  */
1285
1286 static int
1287 dataflow_set_different_2 (void **slot, void *data)
1288 {
1289   htab_t htab = (htab_t) data;
1290   variable var1, var2;
1291
1292   var1 = *(variable *) slot;
1293   var2 = htab_find_with_hash (htab, var1->decl,
1294                               VARIABLE_HASH_VAL (var1->decl));
1295   if (!var2)
1296     {
1297       dataflow_set_different_value = true;
1298
1299       /* Stop traversing the hash table.  */
1300       return 0;
1301     }
1302
1303   /* If both variables are defined they have been already checked for
1304      equivalence.  */
1305   gcc_assert (!variable_different_p (var1, var2, false));
1306
1307   /* Continue traversing the hash table.  */
1308   return 1;
1309 }
1310
1311 /* Return true if dataflow sets OLD_SET and NEW_SET differ.  */
1312
1313 static bool
1314 dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set)
1315 {
1316   dataflow_set_different_value = false;
1317
1318   htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars);
1319   if (!dataflow_set_different_value)
1320     {
1321       /* We have compared the variables which are in both hash tables
1322          so now only check whether there are some variables in NEW_SET->VARS
1323          which are not in OLD_SET->VARS.  */
1324       htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars);
1325     }
1326   return dataflow_set_different_value;
1327 }
1328
1329 /* Free the contents of dataflow set SET.  */
1330
1331 static void
1332 dataflow_set_destroy (dataflow_set *set)
1333 {
1334   int i;
1335
1336   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1337     attrs_list_clear (&set->regs[i]);
1338
1339   htab_delete (set->vars);
1340   set->vars = NULL;
1341 }
1342
1343 /* Return true if RTL X contains a SYMBOL_REF.  */
1344
1345 static bool
1346 contains_symbol_ref (rtx x)
1347 {
1348   const char *fmt;
1349   RTX_CODE code;
1350   int i;
1351
1352   if (!x)
1353     return false;
1354
1355   code = GET_CODE (x);
1356   if (code == SYMBOL_REF)
1357     return true;
1358
1359   fmt = GET_RTX_FORMAT (code);
1360   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1361     {
1362       if (fmt[i] == 'e')
1363         {
1364           if (contains_symbol_ref (XEXP (x, i)))
1365             return true;
1366         }
1367       else if (fmt[i] == 'E')
1368         {
1369           int j;
1370           for (j = 0; j < XVECLEN (x, i); j++)
1371             if (contains_symbol_ref (XVECEXP (x, i, j)))
1372               return true;
1373         }
1374     }
1375
1376   return false;
1377 }
1378
1379 /* Shall EXPR be tracked?  */
1380
1381 static bool
1382 track_expr_p (tree expr)
1383 {
1384   rtx decl_rtl;
1385   tree realdecl;
1386
1387   /* If EXPR is not a parameter or a variable do not track it.  */
1388   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
1389     return 0;
1390
1391   /* It also must have a name...  */
1392   if (!DECL_NAME (expr))
1393     return 0;
1394
1395   /* ... and a RTL assigned to it.  */
1396   decl_rtl = DECL_RTL_IF_SET (expr);
1397   if (!decl_rtl)
1398     return 0;
1399
1400   /* If this expression is really a debug alias of some other declaration, we
1401      don't need to track this expression if the ultimate declaration is
1402      ignored.  */
1403   realdecl = expr;
1404   if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl))
1405     {
1406       realdecl = DECL_DEBUG_EXPR (realdecl);
1407       /* ??? We don't yet know how to emit DW_OP_piece for variable
1408          that has been SRA'ed.  */
1409       if (!DECL_P (realdecl))
1410         return 0;
1411     }
1412
1413   /* Do not track EXPR if REALDECL it should be ignored for debugging
1414      purposes.  */
1415   if (DECL_IGNORED_P (realdecl))
1416     return 0;
1417
1418   /* Do not track global variables until we are able to emit correct location
1419      list for them.  */
1420   if (TREE_STATIC (realdecl))
1421     return 0;
1422
1423   /* When the EXPR is a DECL for alias of some variable (see example)
1424      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
1425      DECL_RTL contains SYMBOL_REF.
1426
1427      Example:
1428      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
1429      char **_dl_argv;
1430   */
1431   if (MEM_P (decl_rtl)
1432       && contains_symbol_ref (XEXP (decl_rtl, 0)))
1433     return 0;
1434
1435   /* If RTX is a memory it should not be very large (because it would be
1436      an array or struct).  */
1437   if (MEM_P (decl_rtl))
1438     {
1439       /* Do not track structures and arrays.  */
1440       if (GET_MODE (decl_rtl) == BLKmode)
1441         return 0;
1442       if (MEM_SIZE (decl_rtl)
1443           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
1444         return 0;
1445     }
1446
1447   return 1;
1448 }
1449
1450 /* Count uses (register and memory references) LOC which will be tracked.
1451    INSN is instruction which the LOC is part of.  */
1452
1453 static int
1454 count_uses (rtx *loc, void *insn)
1455 {
1456   basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1457
1458   if (REG_P (*loc))
1459     {
1460       gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER);
1461       VTI (bb)->n_mos++;
1462     }
1463   else if (MEM_P (*loc)
1464            && MEM_EXPR (*loc)
1465            && track_expr_p (MEM_EXPR (*loc)))
1466     {
1467       VTI (bb)->n_mos++;
1468     }
1469
1470   return 0;
1471 }
1472
1473 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1474
1475 static void
1476 count_uses_1 (rtx *x, void *insn)
1477 {
1478   for_each_rtx (x, count_uses, insn);
1479 }
1480
1481 /* Count stores (register and memory references) LOC which will be tracked.
1482    INSN is instruction which the LOC is part of.  */
1483
1484 static void
1485 count_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn)
1486 {
1487   count_uses (&loc, insn);
1488 }
1489
1490 /* Add uses (register and memory references) LOC which will be tracked
1491    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
1492
1493 static int
1494 add_uses (rtx *loc, void *insn)
1495 {
1496   if (REG_P (*loc))
1497     {
1498       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1499       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1500
1501       mo->type = ((REG_EXPR (*loc) && track_expr_p (REG_EXPR (*loc)))
1502                   ? MO_USE : MO_USE_NO_VAR);
1503       mo->u.loc = *loc;
1504       mo->insn = (rtx) insn;
1505     }
1506   else if (MEM_P (*loc)
1507            && MEM_EXPR (*loc)
1508            && track_expr_p (MEM_EXPR (*loc)))
1509     {
1510       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1511       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1512
1513       mo->type = MO_USE;
1514       mo->u.loc = *loc;
1515       mo->insn = (rtx) insn;
1516     }
1517
1518   return 0;
1519 }
1520
1521 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1522
1523 static void
1524 add_uses_1 (rtx *x, void *insn)
1525 {
1526   for_each_rtx (x, add_uses, insn);
1527 }
1528
1529 /* Add stores (register and memory references) LOC which will be tracked
1530    to VTI (bb)->mos. EXPR is the RTL expression containing the store.
1531    INSN is instruction which the LOC is part of.  */
1532
1533 static void
1534 add_stores (rtx loc, rtx expr, void *insn)
1535 {
1536   if (REG_P (loc))
1537     {
1538       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1539       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1540
1541       mo->type = ((GET_CODE (expr) != CLOBBER && REG_EXPR (loc)
1542                    && track_expr_p (REG_EXPR (loc)))
1543                   ? MO_SET : MO_CLOBBER);
1544       mo->u.loc = loc;
1545       mo->insn = (rtx) insn;
1546     }
1547   else if (MEM_P (loc)
1548            && MEM_EXPR (loc)
1549            && track_expr_p (MEM_EXPR (loc)))
1550     {
1551       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1552       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1553
1554       mo->type = GET_CODE (expr) == CLOBBER ? MO_CLOBBER : MO_SET;
1555       mo->u.loc = loc;
1556       mo->insn = (rtx) insn;
1557     }
1558 }
1559
1560 /* Compute the changes of variable locations in the basic block BB.  */
1561
1562 static bool
1563 compute_bb_dataflow (basic_block bb)
1564 {
1565   int i, n, r;
1566   bool changed;
1567   dataflow_set old_out;
1568   dataflow_set *in = &VTI (bb)->in;
1569   dataflow_set *out = &VTI (bb)->out;
1570
1571   dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
1572   dataflow_set_copy (&old_out, out);
1573   dataflow_set_copy (out, in);
1574
1575   n = VTI (bb)->n_mos;
1576   for (i = 0; i < n; i++)
1577     {
1578       switch (VTI (bb)->mos[i].type)
1579         {
1580           case MO_CALL:
1581             for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1582               if (TEST_HARD_REG_BIT (call_used_reg_set, r))
1583                 var_regno_delete (out, r);
1584             break;
1585
1586           case MO_USE:
1587           case MO_SET:
1588             {
1589               rtx loc = VTI (bb)->mos[i].u.loc;
1590
1591               if (REG_P (loc))
1592                 var_reg_delete_and_set (out, loc);
1593               else if (MEM_P (loc))
1594                 var_mem_delete_and_set (out, loc);
1595             }
1596             break;
1597
1598           case MO_USE_NO_VAR:
1599           case MO_CLOBBER:
1600             {
1601               rtx loc = VTI (bb)->mos[i].u.loc;
1602
1603               if (REG_P (loc))
1604                 var_reg_delete (out, loc);
1605               else if (MEM_P (loc))
1606                 var_mem_delete (out, loc);
1607             }
1608             break;
1609
1610           case MO_ADJUST:
1611             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
1612             break;
1613         }
1614     }
1615
1616   changed = dataflow_set_different (&old_out, out);
1617   dataflow_set_destroy (&old_out);
1618   return changed;
1619 }
1620
1621 /* Find the locations of variables in the whole function.  */
1622
1623 static void
1624 vt_find_locations (void)
1625 {
1626   fibheap_t worklist, pending, fibheap_swap;
1627   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
1628   basic_block bb;
1629   edge e;
1630   int *bb_order;
1631   int *rc_order;
1632   int i;
1633
1634   /* Compute reverse completion order of depth first search of the CFG
1635      so that the data-flow runs faster.  */
1636   rc_order = xmalloc (n_basic_blocks * sizeof (int));
1637   bb_order = xmalloc (last_basic_block * sizeof (int));
1638   flow_depth_first_order_compute (NULL, rc_order);
1639   for (i = 0; i < n_basic_blocks; i++)
1640     bb_order[rc_order[i]] = i;
1641   free (rc_order);
1642
1643   worklist = fibheap_new ();
1644   pending = fibheap_new ();
1645   visited = sbitmap_alloc (last_basic_block);
1646   in_worklist = sbitmap_alloc (last_basic_block);
1647   in_pending = sbitmap_alloc (last_basic_block);
1648   sbitmap_zero (in_worklist);
1649
1650   FOR_EACH_BB (bb)
1651     fibheap_insert (pending, bb_order[bb->index], bb);
1652   sbitmap_ones (in_pending);
1653
1654   while (!fibheap_empty (pending))
1655     {
1656       fibheap_swap = pending;
1657       pending = worklist;
1658       worklist = fibheap_swap;
1659       sbitmap_swap = in_pending;
1660       in_pending = in_worklist;
1661       in_worklist = sbitmap_swap;
1662
1663       sbitmap_zero (visited);
1664
1665       while (!fibheap_empty (worklist))
1666         {
1667           bb = fibheap_extract_min (worklist);
1668           RESET_BIT (in_worklist, bb->index);
1669           if (!TEST_BIT (visited, bb->index))
1670             {
1671               bool changed;
1672               edge_iterator ei;
1673
1674               SET_BIT (visited, bb->index);
1675
1676               /* Calculate the IN set as union of predecessor OUT sets.  */
1677               dataflow_set_clear (&VTI (bb)->in);
1678               FOR_EACH_EDGE (e, ei, bb->preds)
1679                 {
1680                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
1681                 }
1682
1683               changed = compute_bb_dataflow (bb);
1684               if (changed)
1685                 {
1686                   FOR_EACH_EDGE (e, ei, bb->succs)
1687                     {
1688                       if (e->dest == EXIT_BLOCK_PTR)
1689                         continue;
1690
1691                       if (e->dest == bb)
1692                         continue;
1693
1694                       if (TEST_BIT (visited, e->dest->index))
1695                         {
1696                           if (!TEST_BIT (in_pending, e->dest->index))
1697                             {
1698                               /* Send E->DEST to next round.  */
1699                               SET_BIT (in_pending, e->dest->index);
1700                               fibheap_insert (pending,
1701                                               bb_order[e->dest->index],
1702                                               e->dest);
1703                             }
1704                         }
1705                       else if (!TEST_BIT (in_worklist, e->dest->index))
1706                         {
1707                           /* Add E->DEST to current round.  */
1708                           SET_BIT (in_worklist, e->dest->index);
1709                           fibheap_insert (worklist, bb_order[e->dest->index],
1710                                           e->dest);
1711                         }
1712                     }
1713                 }
1714             }
1715         }
1716     }
1717
1718   free (bb_order);
1719   fibheap_delete (worklist);
1720   fibheap_delete (pending);
1721   sbitmap_free (visited);
1722   sbitmap_free (in_worklist);
1723   sbitmap_free (in_pending);
1724 }
1725
1726 /* Print the content of the LIST to dump file.  */
1727
1728 static void
1729 dump_attrs_list (attrs list)
1730 {
1731   for (; list; list = list->next)
1732     {
1733       print_mem_expr (dump_file, list->decl);
1734       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
1735     }
1736   fprintf (dump_file, "\n");
1737 }
1738
1739 /* Print the information about variable *SLOT to dump file.  */
1740
1741 static int
1742 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1743 {
1744   variable var = *(variable *) slot;
1745   int i;
1746   location_chain node;
1747
1748   fprintf (dump_file, "  name: %s\n",
1749            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
1750   for (i = 0; i < var->n_var_parts; i++)
1751     {
1752       fprintf (dump_file, "    offset %ld\n",
1753                (long) var->var_part[i].offset);
1754       for (node = var->var_part[i].loc_chain; node; node = node->next)
1755         {
1756           fprintf (dump_file, "      ");
1757           print_rtl_single (dump_file, node->loc);
1758         }
1759     }
1760
1761   /* Continue traversing the hash table.  */
1762   return 1;
1763 }
1764
1765 /* Print the information about variables from hash table VARS to dump file.  */
1766
1767 static void
1768 dump_vars (htab_t vars)
1769 {
1770   if (htab_elements (vars) > 0)
1771     {
1772       fprintf (dump_file, "Variables:\n");
1773       htab_traverse (vars, dump_variable, NULL);
1774     }
1775 }
1776
1777 /* Print the dataflow set SET to dump file.  */
1778
1779 static void
1780 dump_dataflow_set (dataflow_set *set)
1781 {
1782   int i;
1783
1784   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
1785            set->stack_adjust);
1786   for (i = 1; i < FIRST_PSEUDO_REGISTER; i++)
1787     {
1788       if (set->regs[i])
1789         {
1790           fprintf (dump_file, "Reg %d:", i);
1791           dump_attrs_list (set->regs[i]);
1792         }
1793     }
1794   dump_vars (set->vars);
1795   fprintf (dump_file, "\n");
1796 }
1797
1798 /* Print the IN and OUT sets for each basic block to dump file.  */
1799
1800 static void
1801 dump_dataflow_sets (void)
1802 {
1803   basic_block bb;
1804
1805   FOR_EACH_BB (bb)
1806     {
1807       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
1808       fprintf (dump_file, "IN:\n");
1809       dump_dataflow_set (&VTI (bb)->in);
1810       fprintf (dump_file, "OUT:\n");
1811       dump_dataflow_set (&VTI (bb)->out);
1812     }
1813 }
1814
1815 /* Add variable VAR to the hash table of changed variables and
1816    if it has no locations delete it from hash table HTAB.  */
1817
1818 static void
1819 variable_was_changed (variable var, htab_t htab)
1820 {
1821   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
1822
1823   if (emit_notes)
1824     {
1825       variable *slot;
1826
1827       slot = (variable *) htab_find_slot_with_hash (changed_variables,
1828                                                     var->decl, hash, INSERT);
1829
1830       if (htab && var->n_var_parts == 0)
1831         {
1832           variable empty_var;
1833           void **old;
1834
1835           empty_var = pool_alloc (var_pool);
1836           empty_var->decl = var->decl;
1837           empty_var->refcount = 1;
1838           empty_var->n_var_parts = 0;
1839           *slot = empty_var;
1840
1841           old = htab_find_slot_with_hash (htab, var->decl, hash,
1842                                           NO_INSERT);
1843           if (old)
1844             htab_clear_slot (htab, old);
1845         }
1846       else
1847         {
1848           *slot = var;
1849         }
1850     }
1851   else
1852     {
1853       gcc_assert (htab);
1854       if (var->n_var_parts == 0)
1855         {
1856           void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
1857                                                   NO_INSERT);
1858           if (slot)
1859             htab_clear_slot (htab, slot);
1860         }
1861     }
1862 }
1863
1864 /* Set the part of variable's location in the dataflow set SET.  The variable
1865    part is specified by variable's declaration DECL and offset OFFSET and the
1866    part's location by LOC.  */
1867
1868 static void
1869 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset)
1870 {
1871   int pos, low, high;
1872   location_chain node, next;
1873   location_chain *nextp;
1874   variable var;
1875   void **slot;
1876
1877   slot = htab_find_slot_with_hash (set->vars, decl,
1878                                    VARIABLE_HASH_VAL (decl), INSERT);
1879   if (!*slot)
1880     {
1881       /* Create new variable information.  */
1882       var = pool_alloc (var_pool);
1883       var->decl = decl;
1884       var->refcount = 1;
1885       var->n_var_parts = 1;
1886       var->var_part[0].offset = offset;
1887       var->var_part[0].loc_chain = NULL;
1888       var->var_part[0].cur_loc = NULL;
1889       *slot = var;
1890       pos = 0;
1891     }
1892   else
1893     {
1894       var = (variable) *slot;
1895
1896       /* Find the location part.  */
1897       low = 0;
1898       high = var->n_var_parts;
1899       while (low != high)
1900         {
1901           pos = (low + high) / 2;
1902           if (var->var_part[pos].offset < offset)
1903             low = pos + 1;
1904           else
1905             high = pos;
1906         }
1907       pos = low;
1908
1909       if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
1910         {
1911           node = var->var_part[pos].loc_chain;
1912
1913           if (node
1914               && ((REG_P (node->loc) && REG_P (loc)
1915                    && REGNO (node->loc) == REGNO (loc))
1916                   || rtx_equal_p (node->loc, loc)))
1917             {
1918               /* LOC is in the beginning of the chain so we have nothing
1919                  to do.  */
1920               return;
1921             }
1922           else
1923             {
1924               /* We have to make a copy of a shared variable.  */
1925               if (var->refcount > 1)
1926                 var = unshare_variable (set, var);
1927             }
1928         }
1929       else
1930         {
1931           /* We have not found the location part, new one will be created.  */
1932
1933           /* We have to make a copy of the shared variable.  */
1934           if (var->refcount > 1)
1935             var = unshare_variable (set, var);
1936
1937           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
1938              thus there are at most MAX_VAR_PARTS different offsets.  */
1939           gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
1940
1941           /* We have to move the elements of array starting at index low to the
1942              next position.  */
1943           for (high = var->n_var_parts; high > low; high--)
1944             var->var_part[high] = var->var_part[high - 1];
1945
1946           var->n_var_parts++;
1947           var->var_part[pos].offset = offset;
1948           var->var_part[pos].loc_chain = NULL;
1949           var->var_part[pos].cur_loc = NULL;
1950         }
1951     }
1952
1953   /* Delete the location from the list.  */
1954   nextp = &var->var_part[pos].loc_chain;
1955   for (node = var->var_part[pos].loc_chain; node; node = next)
1956     {
1957       next = node->next;
1958       if ((REG_P (node->loc) && REG_P (loc)
1959            && REGNO (node->loc) == REGNO (loc))
1960           || rtx_equal_p (node->loc, loc))
1961         {
1962           pool_free (loc_chain_pool, node);
1963           *nextp = next;
1964           break;
1965         }
1966       else
1967         nextp = &node->next;
1968     }
1969
1970   /* Add the location to the beginning.  */
1971   node = pool_alloc (loc_chain_pool);
1972   node->loc = loc;
1973   node->next = var->var_part[pos].loc_chain;
1974   var->var_part[pos].loc_chain = node;
1975
1976   /* If no location was emitted do so.  */
1977   if (var->var_part[pos].cur_loc == NULL)
1978     {
1979       var->var_part[pos].cur_loc = loc;
1980       variable_was_changed (var, set->vars);
1981     }
1982 }
1983
1984 /* Delete the part of variable's location from dataflow set SET.  The variable
1985    part is specified by variable's declaration DECL and offset OFFSET and the
1986    part's location by LOC.  */
1987
1988 static void
1989 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
1990                       HOST_WIDE_INT offset)
1991 {
1992   int pos, low, high;
1993   void **slot;
1994
1995   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
1996                                    NO_INSERT);
1997   if (slot)
1998     {
1999       variable var = (variable) *slot;
2000
2001       /* Find the location part.  */
2002       low = 0;
2003       high = var->n_var_parts;
2004       while (low != high)
2005         {
2006           pos = (low + high) / 2;
2007           if (var->var_part[pos].offset < offset)
2008             low = pos + 1;
2009           else
2010             high = pos;
2011         }
2012       pos = low;
2013
2014       if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2015         {
2016           location_chain node, next;
2017           location_chain *nextp;
2018           bool changed;
2019
2020           if (var->refcount > 1)
2021             {
2022               /* If the variable contains the location part we have to
2023                  make a copy of the variable.  */
2024               for (node = var->var_part[pos].loc_chain; node;
2025                    node = node->next)
2026                 {
2027                   if ((REG_P (node->loc) && REG_P (loc)
2028                        && REGNO (node->loc) == REGNO (loc))
2029                       || rtx_equal_p (node->loc, loc))
2030                     {
2031                       var = unshare_variable (set, var);
2032                       break;
2033                     }
2034                 }
2035             }
2036
2037           /* Delete the location part.  */
2038           nextp = &var->var_part[pos].loc_chain;
2039           for (node = *nextp; node; node = next)
2040             {
2041               next = node->next;
2042               if ((REG_P (node->loc) && REG_P (loc)
2043                    && REGNO (node->loc) == REGNO (loc))
2044                   || rtx_equal_p (node->loc, loc))
2045                 {
2046                   pool_free (loc_chain_pool, node);
2047                   *nextp = next;
2048                   break;
2049                 }
2050               else
2051                 nextp = &node->next;
2052             }
2053
2054           /* If we have deleted the location which was last emitted
2055              we have to emit new location so add the variable to set
2056              of changed variables.  */
2057           if (var->var_part[pos].cur_loc
2058               && ((REG_P (loc)
2059                    && REG_P (var->var_part[pos].cur_loc)
2060                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2061                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2062             {
2063               changed = true;
2064               if (var->var_part[pos].loc_chain)
2065                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2066             }
2067           else
2068             changed = false;
2069
2070           if (var->var_part[pos].loc_chain == NULL)
2071             {
2072               var->n_var_parts--;
2073               while (pos < var->n_var_parts)
2074                 {
2075                   var->var_part[pos] = var->var_part[pos + 1];
2076                   pos++;
2077                 }
2078             }
2079           if (changed)
2080               variable_was_changed (var, set->vars);
2081         }
2082     }
2083 }
2084
2085 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2086    additional parameters: WHERE specifies whether the note shall be emitted
2087    before of after instruction INSN.  */
2088
2089 static int
2090 emit_note_insn_var_location (void **varp, void *data)
2091 {
2092   variable var = *(variable *) varp;
2093   rtx insn = ((emit_note_data *)data)->insn;
2094   enum emit_note_where where = ((emit_note_data *)data)->where;
2095   rtx note;
2096   int i, j, n_var_parts;
2097   bool complete;
2098   HOST_WIDE_INT last_limit;
2099   tree type_size_unit;
2100   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2101   rtx loc[MAX_VAR_PARTS];
2102
2103   gcc_assert (var->decl);
2104
2105   complete = true;
2106   last_limit = 0;
2107   n_var_parts = 0;
2108   for (i = 0; i < var->n_var_parts; i++)
2109     {
2110       enum machine_mode mode, wider_mode;
2111
2112       if (last_limit < var->var_part[i].offset)
2113         {
2114           complete = false;
2115           break;
2116         }
2117       else if (last_limit > var->var_part[i].offset)
2118         continue;
2119       offsets[n_var_parts] = var->var_part[i].offset;
2120       loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2121       mode = GET_MODE (loc[n_var_parts]);
2122       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2123
2124       /* Attempt to merge adjacent registers or memory.  */
2125       wider_mode = GET_MODE_WIDER_MODE (mode);
2126       for (j = i + 1; j < var->n_var_parts; j++)
2127         if (last_limit <= var->var_part[j].offset)
2128           break;
2129       if (j < var->n_var_parts
2130           && wider_mode != VOIDmode
2131           && GET_CODE (loc[n_var_parts])
2132              == GET_CODE (var->var_part[j].loc_chain->loc)
2133           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2134           && last_limit == var->var_part[j].offset)
2135         {
2136           rtx new_loc = NULL;
2137           rtx loc2 = var->var_part[j].loc_chain->loc;
2138
2139           if (REG_P (loc[n_var_parts])
2140               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2141                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2142               && REGNO (loc[n_var_parts])
2143                  + hard_regno_nregs[REGNO (loc[n_var_parts])][mode]
2144                  == REGNO (loc2))
2145             {
2146               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2147                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2148                                            mode, 0);
2149               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2150                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2151               if (new_loc)
2152                 {
2153                   if (!REG_P (new_loc)
2154                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2155                     new_loc = NULL;
2156                   else
2157                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2158                 }
2159             }
2160           else if (MEM_P (loc[n_var_parts])
2161                    && GET_CODE (XEXP (loc2, 0)) == PLUS
2162                    && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2163                    && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2164             {
2165               if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2166                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2167                                    XEXP (XEXP (loc2, 0), 0))
2168                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
2169                       == GET_MODE_SIZE (mode))
2170                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2171                       && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2172                          == CONST_INT
2173                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2174                                       XEXP (XEXP (loc2, 0), 0))
2175                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2176                          + GET_MODE_SIZE (mode)
2177                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2178                 new_loc = adjust_address_nv (loc[n_var_parts],
2179                                              wider_mode, 0);
2180             }
2181
2182           if (new_loc)
2183             {
2184               loc[n_var_parts] = new_loc;
2185               mode = wider_mode;
2186               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2187               i = j;
2188             }
2189         }
2190       ++n_var_parts;
2191     }
2192   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2193   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2194     complete = false;
2195
2196   if (where == EMIT_NOTE_AFTER_INSN)
2197     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2198   else
2199     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2200
2201   if (!complete)
2202     {
2203       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2204                                                        NULL_RTX);
2205     }
2206   else if (n_var_parts == 1)
2207     {
2208       rtx expr_list
2209         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
2210
2211       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2212                                                        expr_list);
2213     }
2214   else if (n_var_parts)
2215     {
2216       rtx parallel;
2217
2218       for (i = 0; i < n_var_parts; i++)
2219         loc[i]
2220           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
2221
2222       parallel = gen_rtx_PARALLEL (VOIDmode,
2223                                    gen_rtvec_v (n_var_parts, loc));
2224       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2225                                                        parallel);
2226     }
2227
2228   htab_clear_slot (changed_variables, varp);
2229
2230   /* When there are no location parts the variable has been already
2231      removed from hash table and a new empty variable was created.
2232      Free the empty variable.  */
2233   if (var->n_var_parts == 0)
2234     {
2235       pool_free (var_pool, var);
2236     }
2237
2238   /* Continue traversing the hash table.  */
2239   return 1;
2240 }
2241
2242 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2243    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
2244    shall be emitted before of after instruction INSN.  */
2245
2246 static void
2247 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2248 {
2249   emit_note_data data;
2250
2251   data.insn = insn;
2252   data.where = where;
2253   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2254 }
2255
2256 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2257    same variable in hash table DATA or is not there at all.  */
2258
2259 static int
2260 emit_notes_for_differences_1 (void **slot, void *data)
2261 {
2262   htab_t new_vars = (htab_t) data;
2263   variable old_var, new_var;
2264
2265   old_var = *(variable *) slot;
2266   new_var = htab_find_with_hash (new_vars, old_var->decl,
2267                                  VARIABLE_HASH_VAL (old_var->decl));
2268
2269   if (!new_var)
2270     {
2271       /* Variable has disappeared.  */
2272       variable empty_var;
2273
2274       empty_var = pool_alloc (var_pool);
2275       empty_var->decl = old_var->decl;
2276       empty_var->refcount = 1;
2277       empty_var->n_var_parts = 0;
2278       variable_was_changed (empty_var, NULL);
2279     }
2280   else if (variable_different_p (old_var, new_var, true))
2281     {
2282       variable_was_changed (new_var, NULL);
2283     }
2284
2285   /* Continue traversing the hash table.  */
2286   return 1;
2287 }
2288
2289 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2290    table DATA.  */
2291
2292 static int
2293 emit_notes_for_differences_2 (void **slot, void *data)
2294 {
2295   htab_t old_vars = (htab_t) data;
2296   variable old_var, new_var;
2297
2298   new_var = *(variable *) slot;
2299   old_var = htab_find_with_hash (old_vars, new_var->decl,
2300                                  VARIABLE_HASH_VAL (new_var->decl));
2301   if (!old_var)
2302     {
2303       /* Variable has appeared.  */
2304       variable_was_changed (new_var, NULL);
2305     }
2306
2307   /* Continue traversing the hash table.  */
2308   return 1;
2309 }
2310
2311 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2312    NEW_SET.  */
2313
2314 static void
2315 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2316                             dataflow_set *new_set)
2317 {
2318   htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2319   htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2320   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2321 }
2322
2323 /* Emit the notes for changes of location parts in the basic block BB.  */
2324
2325 static void
2326 emit_notes_in_bb (basic_block bb)
2327 {
2328   int i;
2329   dataflow_set set;
2330
2331   dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2332   dataflow_set_copy (&set, &VTI (bb)->in);
2333
2334   for (i = 0; i < VTI (bb)->n_mos; i++)
2335     {
2336       rtx insn = VTI (bb)->mos[i].insn;
2337
2338       switch (VTI (bb)->mos[i].type)
2339         {
2340           case MO_CALL:
2341             {
2342               int r;
2343
2344               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2345                 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2346                   {
2347                     var_regno_delete (&set, r);
2348                   }
2349               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2350             }
2351             break;
2352
2353           case MO_USE:
2354           case MO_SET:
2355             {
2356               rtx loc = VTI (bb)->mos[i].u.loc;
2357
2358               if (REG_P (loc))
2359                 var_reg_delete_and_set (&set, loc);
2360               else
2361                 var_mem_delete_and_set (&set, loc);
2362
2363               if (VTI (bb)->mos[i].type == MO_USE)
2364                 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2365               else
2366                 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2367             }
2368             break;
2369
2370           case MO_USE_NO_VAR:
2371           case MO_CLOBBER:
2372             {
2373               rtx loc = VTI (bb)->mos[i].u.loc;
2374
2375               if (REG_P (loc))
2376                 var_reg_delete (&set, loc);
2377               else
2378                 var_mem_delete (&set, loc);
2379
2380               if (VTI (bb)->mos[i].type == MO_USE_NO_VAR)
2381                 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2382               else
2383                 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2384             }
2385             break;
2386
2387           case MO_ADJUST:
2388             set.stack_adjust += VTI (bb)->mos[i].u.adjust;
2389             break;
2390         }
2391     }
2392   dataflow_set_destroy (&set);
2393 }
2394
2395 /* Emit notes for the whole function.  */
2396
2397 static void
2398 vt_emit_notes (void)
2399 {
2400   basic_block bb;
2401   dataflow_set *last_out;
2402   dataflow_set empty;
2403
2404   gcc_assert (!htab_elements (changed_variables));
2405
2406   /* Enable emitting notes by functions (mainly by set_variable_part and
2407      delete_variable_part).  */
2408   emit_notes = true;
2409
2410   dataflow_set_init (&empty, 7);
2411   last_out = &empty;
2412
2413   FOR_EACH_BB (bb)
2414     {
2415       /* Emit the notes for changes of variable locations between two
2416          subsequent basic blocks.  */
2417       emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
2418
2419       /* Emit the notes for the changes in the basic block itself.  */
2420       emit_notes_in_bb (bb);
2421
2422       last_out = &VTI (bb)->out;
2423     }
2424   dataflow_set_destroy (&empty);
2425   emit_notes = false;
2426 }
2427
2428 /* If there is a declaration and offset associated with register/memory RTL
2429    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
2430
2431 static bool
2432 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
2433 {
2434   if (REG_P (rtl))
2435     {
2436       if (REG_ATTRS (rtl))
2437         {
2438           *declp = REG_EXPR (rtl);
2439           *offsetp = REG_OFFSET (rtl);
2440           return true;
2441         }
2442     }
2443   else if (MEM_P (rtl))
2444     {
2445       if (MEM_ATTRS (rtl))
2446         {
2447           *declp = MEM_EXPR (rtl);
2448           *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0;
2449           return true;
2450         }
2451     }
2452   return false;
2453 }
2454
2455 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
2456
2457 static void
2458 vt_add_function_parameters (void)
2459 {
2460   tree parm;
2461
2462   for (parm = DECL_ARGUMENTS (current_function_decl);
2463        parm; parm = TREE_CHAIN (parm))
2464     {
2465       rtx decl_rtl = DECL_RTL_IF_SET (parm);
2466       rtx incoming = DECL_INCOMING_RTL (parm);
2467       tree decl;
2468       HOST_WIDE_INT offset;
2469       dataflow_set *out;
2470
2471       if (TREE_CODE (parm) != PARM_DECL)
2472         continue;
2473
2474       if (!DECL_NAME (parm))
2475         continue;
2476
2477       if (!decl_rtl || !incoming)
2478         continue;
2479
2480       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
2481         continue;
2482
2483       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
2484         if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
2485           continue;
2486
2487       if (!decl)
2488         continue;
2489
2490       gcc_assert (parm == decl);
2491
2492       out = &VTI (ENTRY_BLOCK_PTR)->out;
2493
2494       if (REG_P (incoming))
2495         {
2496           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
2497           attrs_list_insert (&out->regs[REGNO (incoming)],
2498                              parm, offset, incoming);
2499           set_variable_part (out, incoming, parm, offset);
2500         }
2501       else if (MEM_P (incoming))
2502         set_variable_part (out, incoming, parm, offset);
2503     }
2504 }
2505
2506 /* Allocate and initialize the data structures for variable tracking
2507    and parse the RTL to get the micro operations.  */
2508
2509 static void
2510 vt_initialize (void)
2511 {
2512   basic_block bb;
2513
2514   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
2515
2516   FOR_EACH_BB (bb)
2517     {
2518       rtx insn;
2519       HOST_WIDE_INT pre, post;
2520
2521       /* Count the number of micro operations.  */
2522       VTI (bb)->n_mos = 0;
2523       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2524            insn = NEXT_INSN (insn))
2525         {
2526           if (INSN_P (insn))
2527             {
2528               if (!frame_pointer_needed)
2529                 {
2530                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2531                   if (pre)
2532                     VTI (bb)->n_mos++;
2533                   if (post)
2534                     VTI (bb)->n_mos++;
2535                 }
2536               note_uses (&PATTERN (insn), count_uses_1, insn);
2537               note_stores (PATTERN (insn), count_stores, insn);
2538               if (CALL_P (insn))
2539                 VTI (bb)->n_mos++;
2540             }
2541         }
2542
2543       /* Add the micro-operations to the array.  */
2544       VTI (bb)->mos = xmalloc (VTI (bb)->n_mos
2545                                * sizeof (struct micro_operation_def));
2546       VTI (bb)->n_mos = 0;
2547       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2548            insn = NEXT_INSN (insn))
2549         {
2550           if (INSN_P (insn))
2551             {
2552               int n1, n2;
2553
2554               if (!frame_pointer_needed)
2555                 {
2556                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2557                   if (pre)
2558                     {
2559                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2560
2561                       mo->type = MO_ADJUST;
2562                       mo->u.adjust = pre;
2563                       mo->insn = insn;
2564                     }
2565                 }
2566
2567               n1 = VTI (bb)->n_mos;
2568               note_uses (&PATTERN (insn), add_uses_1, insn);
2569               n2 = VTI (bb)->n_mos - 1;
2570
2571               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
2572               while (n1 < n2)
2573                 {
2574                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
2575                     n1++;
2576                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
2577                     n2--;
2578                   if (n1 < n2)
2579                     {
2580                       micro_operation sw;
2581
2582                       sw = VTI (bb)->mos[n1];
2583                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2584                       VTI (bb)->mos[n2] = sw;
2585                     }
2586                 }
2587
2588               if (CALL_P (insn))
2589                 {
2590                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2591
2592                   mo->type = MO_CALL;
2593                   mo->insn = insn;
2594                 }
2595
2596               n1 = VTI (bb)->n_mos;
2597               note_stores (PATTERN (insn), add_stores, insn);
2598               n2 = VTI (bb)->n_mos - 1;
2599
2600               /* Order the MO_SETs to be before MO_CLOBBERs.  */
2601               while (n1 < n2)
2602                 {
2603                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_SET)
2604                     n1++;
2605                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_CLOBBER)
2606                     n2--;
2607                   if (n1 < n2)
2608                     {
2609                       micro_operation sw;
2610
2611                       sw = VTI (bb)->mos[n1];
2612                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2613                       VTI (bb)->mos[n2] = sw;
2614                     }
2615                 }
2616
2617               if (!frame_pointer_needed && post)
2618                 {
2619                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2620
2621                   mo->type = MO_ADJUST;
2622                   mo->u.adjust = post;
2623                   mo->insn = insn;
2624                 }
2625             }
2626         }
2627     }
2628
2629   /* Init the IN and OUT sets.  */
2630   FOR_ALL_BB (bb)
2631     {
2632       VTI (bb)->visited = false;
2633       dataflow_set_init (&VTI (bb)->in, 7);
2634       dataflow_set_init (&VTI (bb)->out, 7);
2635     }
2636
2637   attrs_pool = create_alloc_pool ("attrs_def pool",
2638                                   sizeof (struct attrs_def), 1024);
2639   var_pool = create_alloc_pool ("variable_def pool",
2640                                 sizeof (struct variable_def), 64);
2641   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
2642                                       sizeof (struct location_chain_def),
2643                                       1024);
2644   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
2645                                    NULL);
2646   vt_add_function_parameters ();
2647 }
2648
2649 /* Free the data structures needed for variable tracking.  */
2650
2651 static void
2652 vt_finalize (void)
2653 {
2654   basic_block bb;
2655
2656   FOR_EACH_BB (bb)
2657     {
2658       free (VTI (bb)->mos);
2659     }
2660
2661   FOR_ALL_BB (bb)
2662     {
2663       dataflow_set_destroy (&VTI (bb)->in);
2664       dataflow_set_destroy (&VTI (bb)->out);
2665     }
2666   free_aux_for_blocks ();
2667   free_alloc_pool (attrs_pool);
2668   free_alloc_pool (var_pool);
2669   free_alloc_pool (loc_chain_pool);
2670   htab_delete (changed_variables);
2671 }
2672
2673 /* The entry point to variable tracking pass.  */
2674
2675 void
2676 variable_tracking_main (void)
2677 {
2678   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
2679     return;
2680
2681   mark_dfs_back_edges ();
2682   vt_initialize ();
2683   if (!frame_pointer_needed)
2684     {
2685       if (!vt_stack_adjustments ())
2686         {
2687           vt_finalize ();
2688           return;
2689         }
2690     }
2691
2692   vt_find_locations ();
2693   vt_emit_notes ();
2694
2695   if (dump_file)
2696     {
2697       dump_dataflow_sets ();
2698       dump_flow_info (dump_file);
2699     }
2700
2701   vt_finalize ();
2702 }
2703 \f
2704 static bool
2705 gate_handle_var_tracking (void)
2706 {
2707   return (flag_var_tracking);
2708 }
2709
2710
2711
2712 struct tree_opt_pass pass_variable_tracking =
2713 {
2714   "vartrack",                           /* name */
2715   gate_handle_var_tracking,             /* gate */
2716   variable_tracking_main,               /* execute */
2717   NULL,                                 /* sub */
2718   NULL,                                 /* next */
2719   0,                                    /* static_pass_number */
2720   TV_VAR_TRACKING,                      /* tv_id */
2721   0,                                    /* properties_required */
2722   0,                                    /* properties_provided */
2723   0,                                    /* properties_destroyed */
2724   0,                                    /* todo_flags_start */
2725   TODO_dump_func,                       /* todo_flags_finish */
2726   'V'                                   /* letter */
2727 };
2728