gcc/var-tracking.c

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