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