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             {
1728               HARD_REG_SET used_regs;
1729
1730               get_call_invalidated_used_regs (VTI (bb)->mos[i].insn,
1731                                               &used_regs, false);
1732               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1733                 if (TEST_HARD_REG_BIT (used_regs, r))
1734                   var_regno_delete (out, r);
1735             }
1736             break;
1737
1738           case MO_USE:
1739             {
1740               rtx loc = VTI (bb)->mos[i].u.loc;
1741
1742               if (GET_CODE (loc) == REG)
1743                 var_reg_set (out, loc);
1744               else if (GET_CODE (loc) == MEM)
1745                 var_mem_set (out, loc);
1746             }
1747             break;
1748
1749           case MO_SET:
1750             {
1751               rtx loc = VTI (bb)->mos[i].u.loc;
1752
1753               if (REG_P (loc))
1754                 var_reg_delete_and_set (out, loc, true);
1755               else if (MEM_P (loc))
1756                 var_mem_delete_and_set (out, loc, true);
1757             }
1758             break;
1759
1760           case MO_COPY:
1761             {
1762               rtx loc = VTI (bb)->mos[i].u.loc;
1763
1764               if (REG_P (loc))
1765                 var_reg_delete_and_set (out, loc, false);
1766               else if (MEM_P (loc))
1767                 var_mem_delete_and_set (out, loc, false);
1768             }
1769             break;
1770
1771           case MO_USE_NO_VAR:
1772             {
1773               rtx loc = VTI (bb)->mos[i].u.loc;
1774
1775               if (REG_P (loc))
1776                 var_reg_delete (out, loc, false);
1777               else if (MEM_P (loc))
1778                 var_mem_delete (out, loc, false);
1779             }
1780             break;
1781
1782           case MO_CLOBBER:
1783             {
1784               rtx loc = VTI (bb)->mos[i].u.loc;
1785
1786               if (REG_P (loc))
1787                 var_reg_delete (out, loc, true);
1788               else if (MEM_P (loc))
1789                 var_mem_delete (out, loc, true);
1790             }
1791             break;
1792
1793           case MO_ADJUST:
1794             out->stack_adjust += VTI (bb)->mos[i].u.adjust;
1795             break;
1796         }
1797     }
1798
1799   changed = dataflow_set_different (&old_out, out);
1800   dataflow_set_destroy (&old_out);
1801   return changed;
1802 }
1803
1804 /* Find the locations of variables in the whole function.  */
1805
1806 static void
1807 vt_find_locations (void)
1808 {
1809   fibheap_t worklist, pending, fibheap_swap;
1810   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
1811   basic_block bb;
1812   edge e;
1813   int *bb_order;
1814   int *rc_order;
1815   int i;
1816
1817   /* Compute reverse completion order of depth first search of the CFG
1818      so that the data-flow runs faster.  */
1819   rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
1820   bb_order = XNEWVEC (int, last_basic_block);
1821   pre_and_rev_post_order_compute (NULL, rc_order, false);
1822   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
1823     bb_order[rc_order[i]] = i;
1824   free (rc_order);
1825
1826   worklist = fibheap_new ();
1827   pending = fibheap_new ();
1828   visited = sbitmap_alloc (last_basic_block);
1829   in_worklist = sbitmap_alloc (last_basic_block);
1830   in_pending = sbitmap_alloc (last_basic_block);
1831   sbitmap_zero (in_worklist);
1832
1833   FOR_EACH_BB (bb)
1834     fibheap_insert (pending, bb_order[bb->index], bb);
1835   sbitmap_ones (in_pending);
1836
1837   while (!fibheap_empty (pending))
1838     {
1839       fibheap_swap = pending;
1840       pending = worklist;
1841       worklist = fibheap_swap;
1842       sbitmap_swap = in_pending;
1843       in_pending = in_worklist;
1844       in_worklist = sbitmap_swap;
1845
1846       sbitmap_zero (visited);
1847
1848       while (!fibheap_empty (worklist))
1849         {
1850           bb = fibheap_extract_min (worklist);
1851           RESET_BIT (in_worklist, bb->index);
1852           if (!TEST_BIT (visited, bb->index))
1853             {
1854               bool changed;
1855               edge_iterator ei;
1856
1857               SET_BIT (visited, bb->index);
1858
1859               /* Calculate the IN set as union of predecessor OUT sets.  */
1860               dataflow_set_clear (&VTI (bb)->in);
1861               FOR_EACH_EDGE (e, ei, bb->preds)
1862                 {
1863                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
1864                 }
1865
1866               changed = compute_bb_dataflow (bb);
1867               if (changed)
1868                 {
1869                   FOR_EACH_EDGE (e, ei, bb->succs)
1870                     {
1871                       if (e->dest == EXIT_BLOCK_PTR)
1872                         continue;
1873
1874                       if (e->dest == bb)
1875                         continue;
1876
1877                       if (TEST_BIT (visited, e->dest->index))
1878                         {
1879                           if (!TEST_BIT (in_pending, e->dest->index))
1880                             {
1881                               /* Send E->DEST to next round.  */
1882                               SET_BIT (in_pending, e->dest->index);
1883                               fibheap_insert (pending,
1884                                               bb_order[e->dest->index],
1885                                               e->dest);
1886                             }
1887                         }
1888                       else if (!TEST_BIT (in_worklist, e->dest->index))
1889                         {
1890                           /* Add E->DEST to current round.  */
1891                           SET_BIT (in_worklist, e->dest->index);
1892                           fibheap_insert (worklist, bb_order[e->dest->index],
1893                                           e->dest);
1894                         }
1895                     }
1896                 }
1897             }
1898         }
1899     }
1900
1901   free (bb_order);
1902   fibheap_delete (worklist);
1903   fibheap_delete (pending);
1904   sbitmap_free (visited);
1905   sbitmap_free (in_worklist);
1906   sbitmap_free (in_pending);
1907 }
1908
1909 /* Print the content of the LIST to dump file.  */
1910
1911 static void
1912 dump_attrs_list (attrs list)
1913 {
1914   for (; list; list = list->next)
1915     {
1916       print_mem_expr (dump_file, list->decl);
1917       fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset);
1918     }
1919   fprintf (dump_file, "\n");
1920 }
1921
1922 /* Print the information about variable *SLOT to dump file.  */
1923
1924 static int
1925 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1926 {
1927   variable var = *(variable *) slot;
1928   int i;
1929   location_chain node;
1930
1931   fprintf (dump_file, "  name: %s\n",
1932            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
1933   for (i = 0; i < var->n_var_parts; i++)
1934     {
1935       fprintf (dump_file, "    offset %ld\n",
1936                (long) var->var_part[i].offset);
1937       for (node = var->var_part[i].loc_chain; node; node = node->next)
1938         {
1939           fprintf (dump_file, "      ");
1940           print_rtl_single (dump_file, node->loc);
1941         }
1942     }
1943
1944   /* Continue traversing the hash table.  */
1945   return 1;
1946 }
1947
1948 /* Print the information about variables from hash table VARS to dump file.  */
1949
1950 static void
1951 dump_vars (htab_t vars)
1952 {
1953   if (htab_elements (vars) > 0)
1954     {
1955       fprintf (dump_file, "Variables:\n");
1956       htab_traverse (vars, dump_variable, NULL);
1957     }
1958 }
1959
1960 /* Print the dataflow set SET to dump file.  */
1961
1962 static void
1963 dump_dataflow_set (dataflow_set *set)
1964 {
1965   int i;
1966
1967   fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n",
1968            set->stack_adjust);
1969   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1970     {
1971       if (set->regs[i])
1972         {
1973           fprintf (dump_file, "Reg %d:", i);
1974           dump_attrs_list (set->regs[i]);
1975         }
1976     }
1977   dump_vars (set->vars);
1978   fprintf (dump_file, "\n");
1979 }
1980
1981 /* Print the IN and OUT sets for each basic block to dump file.  */
1982
1983 static void
1984 dump_dataflow_sets (void)
1985 {
1986   basic_block bb;
1987
1988   FOR_EACH_BB (bb)
1989     {
1990       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
1991       fprintf (dump_file, "IN:\n");
1992       dump_dataflow_set (&VTI (bb)->in);
1993       fprintf (dump_file, "OUT:\n");
1994       dump_dataflow_set (&VTI (bb)->out);
1995     }
1996 }
1997
1998 /* Add variable VAR to the hash table of changed variables and
1999    if it has no locations delete it from hash table HTAB.  */
2000
2001 static void
2002 variable_was_changed (variable var, htab_t htab)
2003 {
2004   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
2005
2006   if (emit_notes)
2007     {
2008       variable *slot;
2009
2010       slot = (variable *) htab_find_slot_with_hash (changed_variables,
2011                                                     var->decl, hash, INSERT);
2012
2013       if (htab && var->n_var_parts == 0)
2014         {
2015           variable empty_var;
2016           void **old;
2017
2018           empty_var = pool_alloc (var_pool);
2019           empty_var->decl = var->decl;
2020           empty_var->refcount = 1;
2021           empty_var->n_var_parts = 0;
2022           *slot = empty_var;
2023
2024           old = htab_find_slot_with_hash (htab, var->decl, hash,
2025                                           NO_INSERT);
2026           if (old)
2027             htab_clear_slot (htab, old);
2028         }
2029       else
2030         {
2031           *slot = var;
2032         }
2033     }
2034   else
2035     {
2036       gcc_assert (htab);
2037       if (var->n_var_parts == 0)
2038         {
2039           void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
2040                                                   NO_INSERT);
2041           if (slot)
2042             htab_clear_slot (htab, slot);
2043         }
2044     }
2045 }
2046
2047 /* Look for the index in VAR->var_part corresponding to OFFSET.
2048    Return -1 if not found.  If INSERTION_POINT is non-NULL, the
2049    referenced int will be set to the index that the part has or should
2050    have, if it should be inserted.  */
2051
2052 static inline int
2053 find_variable_location_part (variable var, HOST_WIDE_INT offset,
2054                              int *insertion_point)
2055 {
2056   int pos, low, high;
2057
2058   /* Find the location part.  */
2059   low = 0;
2060   high = var->n_var_parts;
2061   while (low != high)
2062     {
2063       pos = (low + high) / 2;
2064       if (var->var_part[pos].offset < offset)
2065         low = pos + 1;
2066       else
2067         high = pos;
2068     }
2069   pos = low;
2070
2071   if (insertion_point)
2072     *insertion_point = pos;
2073
2074   if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2075     return pos;
2076
2077   return -1;
2078 }
2079
2080 /* Set the part of variable's location in the dataflow set SET.  The variable
2081    part is specified by variable's declaration DECL and offset OFFSET and the
2082    part's location by LOC.  */
2083
2084 static void
2085 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset)
2086 {
2087   int pos;
2088   location_chain node, next;
2089   location_chain *nextp;
2090   variable var;
2091   void **slot;
2092
2093   slot = htab_find_slot_with_hash (set->vars, decl,
2094                                    VARIABLE_HASH_VAL (decl), INSERT);
2095   if (!*slot)
2096     {
2097       /* Create new variable information.  */
2098       var = pool_alloc (var_pool);
2099       var->decl = decl;
2100       var->refcount = 1;
2101       var->n_var_parts = 1;
2102       var->var_part[0].offset = offset;
2103       var->var_part[0].loc_chain = NULL;
2104       var->var_part[0].cur_loc = NULL;
2105       *slot = var;
2106       pos = 0;
2107     }
2108   else
2109     {
2110       int inspos = 0;
2111
2112       var = (variable) *slot;
2113
2114       pos = find_variable_location_part (var, offset, &inspos);
2115
2116       if (pos >= 0)
2117         {
2118           node = var->var_part[pos].loc_chain;
2119
2120           if (node
2121               && ((REG_P (node->loc) && REG_P (loc)
2122                    && REGNO (node->loc) == REGNO (loc))
2123                   || rtx_equal_p (node->loc, loc)))
2124             {
2125               /* LOC is in the beginning of the chain so we have nothing
2126                  to do.  */
2127               return;
2128             }
2129           else
2130             {
2131               /* We have to make a copy of a shared variable.  */
2132               if (var->refcount > 1)
2133                 var = unshare_variable (set, var);
2134             }
2135         }
2136       else
2137         {
2138           /* We have not found the location part, new one will be created.  */
2139
2140           /* We have to make a copy of the shared variable.  */
2141           if (var->refcount > 1)
2142             var = unshare_variable (set, var);
2143
2144           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2145              thus there are at most MAX_VAR_PARTS different offsets.  */
2146           gcc_assert (var->n_var_parts < MAX_VAR_PARTS);
2147
2148           /* We have to move the elements of array starting at index
2149              inspos to the next position.  */
2150           for (pos = var->n_var_parts; pos > inspos; pos--)
2151             var->var_part[pos] = var->var_part[pos - 1];
2152
2153           var->n_var_parts++;
2154           var->var_part[pos].offset = offset;
2155           var->var_part[pos].loc_chain = NULL;
2156           var->var_part[pos].cur_loc = NULL;
2157         }
2158     }
2159
2160   /* Delete the location from the list.  */
2161   nextp = &var->var_part[pos].loc_chain;
2162   for (node = var->var_part[pos].loc_chain; node; node = next)
2163     {
2164       next = node->next;
2165       if ((REG_P (node->loc) && REG_P (loc)
2166            && REGNO (node->loc) == REGNO (loc))
2167           || rtx_equal_p (node->loc, loc))
2168         {
2169           pool_free (loc_chain_pool, node);
2170           *nextp = next;
2171           break;
2172         }
2173       else
2174         nextp = &node->next;
2175     }
2176
2177   /* Add the location to the beginning.  */
2178   node = pool_alloc (loc_chain_pool);
2179   node->loc = loc;
2180   node->next = var->var_part[pos].loc_chain;
2181   var->var_part[pos].loc_chain = node;
2182
2183   /* If no location was emitted do so.  */
2184   if (var->var_part[pos].cur_loc == NULL)
2185     {
2186       var->var_part[pos].cur_loc = loc;
2187       variable_was_changed (var, set->vars);
2188     }
2189 }
2190
2191 /* Remove all recorded register locations for the given variable part
2192    from dataflow set SET, except for those that are identical to loc.
2193    The variable part is specified by variable's declaration DECL and
2194    offset OFFSET.  */
2195
2196 static void
2197 clobber_variable_part (dataflow_set *set, rtx loc, tree decl,
2198                       HOST_WIDE_INT offset)
2199 {
2200   void **slot;
2201
2202   if (! decl || ! DECL_P (decl))
2203     return;
2204
2205   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2206                                    NO_INSERT);
2207   if (slot)
2208     {
2209       variable var = (variable) *slot;
2210       int pos = find_variable_location_part (var, offset, NULL);
2211
2212       if (pos >= 0)
2213         {
2214           location_chain node, next;
2215
2216           /* Remove the register locations from the dataflow set.  */
2217           next = var->var_part[pos].loc_chain;
2218           for (node = next; node; node = next)
2219             {
2220               next = node->next;
2221               if (node->loc != loc)
2222                 {
2223                   if (REG_P (node->loc))
2224                     {
2225                       attrs anode, anext;
2226                       attrs *anextp;
2227
2228                       /* Remove the variable part from the register's
2229                          list, but preserve any other variable parts
2230                          that might be regarded as live in that same
2231                          register.  */
2232                       anextp = &set->regs[REGNO (node->loc)];
2233                       for (anode = *anextp; anode; anode = anext)
2234                         {
2235                           anext = anode->next;
2236                           if (anode->decl == decl
2237                               && anode->offset == offset)
2238                             {
2239                               pool_free (attrs_pool, anode);
2240                               *anextp = anext;
2241                             }
2242                         }
2243                     }
2244
2245                   delete_variable_part (set, node->loc, decl, offset);
2246                 }
2247             }
2248         }
2249     }
2250 }
2251
2252 /* Delete the part of variable's location from dataflow set SET.  The variable
2253    part is specified by variable's declaration DECL and offset OFFSET and the
2254    part's location by LOC.  */
2255
2256 static void
2257 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2258                       HOST_WIDE_INT offset)
2259 {
2260   void **slot;
2261
2262   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2263                                    NO_INSERT);
2264   if (slot)
2265     {
2266       variable var = (variable) *slot;
2267       int pos = find_variable_location_part (var, offset, NULL);
2268
2269       if (pos >= 0)
2270         {
2271           location_chain node, next;
2272           location_chain *nextp;
2273           bool changed;
2274
2275           if (var->refcount > 1)
2276             {
2277               /* If the variable contains the location part we have to
2278                  make a copy of the variable.  */
2279               for (node = var->var_part[pos].loc_chain; node;
2280                    node = node->next)
2281                 {
2282                   if ((REG_P (node->loc) && REG_P (loc)
2283                        && REGNO (node->loc) == REGNO (loc))
2284                       || rtx_equal_p (node->loc, loc))
2285                     {
2286                       var = unshare_variable (set, var);
2287                       break;
2288                     }
2289                 }
2290             }
2291
2292           /* Delete the location part.  */
2293           nextp = &var->var_part[pos].loc_chain;
2294           for (node = *nextp; node; node = next)
2295             {
2296               next = node->next;
2297               if ((REG_P (node->loc) && REG_P (loc)
2298                    && REGNO (node->loc) == REGNO (loc))
2299                   || rtx_equal_p (node->loc, loc))
2300                 {
2301                   pool_free (loc_chain_pool, node);
2302                   *nextp = next;
2303                   break;
2304                 }
2305               else
2306                 nextp = &node->next;
2307             }
2308
2309           /* If we have deleted the location which was last emitted
2310              we have to emit new location so add the variable to set
2311              of changed variables.  */
2312           if (var->var_part[pos].cur_loc
2313               && ((REG_P (loc)
2314                    && REG_P (var->var_part[pos].cur_loc)
2315                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2316                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2317             {
2318               changed = true;
2319               if (var->var_part[pos].loc_chain)
2320                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2321             }
2322           else
2323             changed = false;
2324
2325           if (var->var_part[pos].loc_chain == NULL)
2326             {
2327               var->n_var_parts--;
2328               while (pos < var->n_var_parts)
2329                 {
2330                   var->var_part[pos] = var->var_part[pos + 1];
2331                   pos++;
2332                 }
2333             }
2334           if (changed)
2335             variable_was_changed (var, set->vars);
2336         }
2337     }
2338 }
2339
2340 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2341    additional parameters: WHERE specifies whether the note shall be emitted
2342    before of after instruction INSN.  */
2343
2344 static int
2345 emit_note_insn_var_location (void **varp, void *data)
2346 {
2347   variable var = *(variable *) varp;
2348   rtx insn = ((emit_note_data *)data)->insn;
2349   enum emit_note_where where = ((emit_note_data *)data)->where;
2350   rtx note;
2351   int i, j, n_var_parts;
2352   bool complete;
2353   HOST_WIDE_INT last_limit;
2354   tree type_size_unit;
2355   HOST_WIDE_INT offsets[MAX_VAR_PARTS];
2356   rtx loc[MAX_VAR_PARTS];
2357
2358   gcc_assert (var->decl);
2359
2360   complete = true;
2361   last_limit = 0;
2362   n_var_parts = 0;
2363   for (i = 0; i < var->n_var_parts; i++)
2364     {
2365       enum machine_mode mode, wider_mode;
2366
2367       if (last_limit < var->var_part[i].offset)
2368         {
2369           complete = false;
2370           break;
2371         }
2372       else if (last_limit > var->var_part[i].offset)
2373         continue;
2374       offsets[n_var_parts] = var->var_part[i].offset;
2375       loc[n_var_parts] = var->var_part[i].loc_chain->loc;
2376       mode = GET_MODE (loc[n_var_parts]);
2377       last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2378
2379       /* Attempt to merge adjacent registers or memory.  */
2380       wider_mode = GET_MODE_WIDER_MODE (mode);
2381       for (j = i + 1; j < var->n_var_parts; j++)
2382         if (last_limit <= var->var_part[j].offset)
2383           break;
2384       if (j < var->n_var_parts
2385           && wider_mode != VOIDmode
2386           && GET_CODE (loc[n_var_parts])
2387              == GET_CODE (var->var_part[j].loc_chain->loc)
2388           && mode == GET_MODE (var->var_part[j].loc_chain->loc)
2389           && last_limit == var->var_part[j].offset)
2390         {
2391           rtx new_loc = NULL;
2392           rtx loc2 = var->var_part[j].loc_chain->loc;
2393
2394           if (REG_P (loc[n_var_parts])
2395               && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2
2396                  == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode]
2397               && REGNO (loc[n_var_parts])
2398                  + hard_regno_nregs[REGNO (loc[n_var_parts])][mode]
2399                  == REGNO (loc2))
2400             {
2401               if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN)
2402                 new_loc = simplify_subreg (wider_mode, loc[n_var_parts],
2403                                            mode, 0);
2404               else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN)
2405                 new_loc = simplify_subreg (wider_mode, loc2, mode, 0);
2406               if (new_loc)
2407                 {
2408                   if (!REG_P (new_loc)
2409                       || REGNO (new_loc) != REGNO (loc[n_var_parts]))
2410                     new_loc = NULL;
2411                   else
2412                     REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]);
2413                 }
2414             }
2415           else if (MEM_P (loc[n_var_parts])
2416                    && GET_CODE (XEXP (loc2, 0)) == PLUS
2417                    && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG
2418                    && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT)
2419             {
2420               if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG
2421                    && rtx_equal_p (XEXP (loc[n_var_parts], 0),
2422                                    XEXP (XEXP (loc2, 0), 0))
2423                    && INTVAL (XEXP (XEXP (loc2, 0), 1))
2424                       == GET_MODE_SIZE (mode))
2425                   || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS
2426                       && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1))
2427                          == CONST_INT
2428                       && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0),
2429                                       XEXP (XEXP (loc2, 0), 0))
2430                       && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1))
2431                          + GET_MODE_SIZE (mode)
2432                          == INTVAL (XEXP (XEXP (loc2, 0), 1))))
2433                 new_loc = adjust_address_nv (loc[n_var_parts],
2434                                              wider_mode, 0);
2435             }
2436
2437           if (new_loc)
2438             {
2439               loc[n_var_parts] = new_loc;
2440               mode = wider_mode;
2441               last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode);
2442               i = j;
2443             }
2444         }
2445       ++n_var_parts;
2446     }
2447   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2448   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2449     complete = false;
2450
2451   if (where == EMIT_NOTE_AFTER_INSN)
2452     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2453   else
2454     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2455
2456   if (!complete)
2457     {
2458       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2459                                                        NULL_RTX);
2460     }
2461   else if (n_var_parts == 1)
2462     {
2463       rtx expr_list
2464         = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0]));
2465
2466       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2467                                                        expr_list);
2468     }
2469   else if (n_var_parts)
2470     {
2471       rtx parallel;
2472
2473       for (i = 0; i < n_var_parts; i++)
2474         loc[i]
2475           = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i]));
2476
2477       parallel = gen_rtx_PARALLEL (VOIDmode,
2478                                    gen_rtvec_v (n_var_parts, loc));
2479       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2480                                                        parallel);
2481     }
2482
2483   htab_clear_slot (changed_variables, varp);
2484
2485   /* When there are no location parts the variable has been already
2486      removed from hash table and a new empty variable was created.
2487      Free the empty variable.  */
2488   if (var->n_var_parts == 0)
2489     {
2490       pool_free (var_pool, var);
2491     }
2492
2493   /* Continue traversing the hash table.  */
2494   return 1;
2495 }
2496
2497 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2498    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
2499    shall be emitted before of after instruction INSN.  */
2500
2501 static void
2502 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2503 {
2504   emit_note_data data;
2505
2506   data.insn = insn;
2507   data.where = where;
2508   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2509 }
2510
2511 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2512    same variable in hash table DATA or is not there at all.  */
2513
2514 static int
2515 emit_notes_for_differences_1 (void **slot, void *data)
2516 {
2517   htab_t new_vars = (htab_t) data;
2518   variable old_var, new_var;
2519
2520   old_var = *(variable *) slot;
2521   new_var = htab_find_with_hash (new_vars, old_var->decl,
2522                                  VARIABLE_HASH_VAL (old_var->decl));
2523
2524   if (!new_var)
2525     {
2526       /* Variable has disappeared.  */
2527       variable empty_var;
2528
2529       empty_var = pool_alloc (var_pool);
2530       empty_var->decl = old_var->decl;
2531       empty_var->refcount = 1;
2532       empty_var->n_var_parts = 0;
2533       variable_was_changed (empty_var, NULL);
2534     }
2535   else if (variable_different_p (old_var, new_var, true))
2536     {
2537       variable_was_changed (new_var, NULL);
2538     }
2539
2540   /* Continue traversing the hash table.  */
2541   return 1;
2542 }
2543
2544 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2545    table DATA.  */
2546
2547 static int
2548 emit_notes_for_differences_2 (void **slot, void *data)
2549 {
2550   htab_t old_vars = (htab_t) data;
2551   variable old_var, new_var;
2552
2553   new_var = *(variable *) slot;
2554   old_var = htab_find_with_hash (old_vars, new_var->decl,
2555                                  VARIABLE_HASH_VAL (new_var->decl));
2556   if (!old_var)
2557     {
2558       /* Variable has appeared.  */
2559       variable_was_changed (new_var, NULL);
2560     }
2561
2562   /* Continue traversing the hash table.  */
2563   return 1;
2564 }
2565
2566 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2567    NEW_SET.  */
2568
2569 static void
2570 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2571                             dataflow_set *new_set)
2572 {
2573   htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2574   htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2575   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2576 }
2577
2578 /* Emit the notes for changes of location parts in the basic block BB.  */
2579
2580 static void
2581 emit_notes_in_bb (basic_block bb)
2582 {
2583   int i;
2584   dataflow_set set;
2585
2586   dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2587   dataflow_set_copy (&set, &VTI (bb)->in);
2588
2589   for (i = 0; i < VTI (bb)->n_mos; i++)
2590     {
2591       rtx insn = VTI (bb)->mos[i].insn;
2592
2593       switch (VTI (bb)->mos[i].type)
2594         {
2595           case MO_CALL:
2596             {
2597               int r;
2598               HARD_REG_SET used_regs;
2599
2600               get_call_invalidated_used_regs (insn, &used_regs, false);
2601               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2602                 if (TEST_HARD_REG_BIT (used_regs, r))
2603                   {
2604                     var_regno_delete (&set, r);
2605                   }
2606               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2607             }
2608             break;
2609
2610           case MO_USE:
2611             {
2612               rtx loc = VTI (bb)->mos[i].u.loc;
2613
2614               if (GET_CODE (loc) == REG)
2615                 var_reg_set (&set, loc);
2616               else
2617                 var_mem_set (&set, loc);
2618
2619               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2620             }
2621             break;
2622
2623           case MO_SET:
2624             {
2625               rtx loc = VTI (bb)->mos[i].u.loc;
2626
2627               if (REG_P (loc))
2628                 var_reg_delete_and_set (&set, loc, true);
2629               else
2630                 var_mem_delete_and_set (&set, loc, true);
2631
2632               emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2633             }
2634             break;
2635
2636           case MO_COPY:
2637             {
2638               rtx loc = VTI (bb)->mos[i].u.loc;
2639
2640               if (REG_P (loc))
2641                 var_reg_delete_and_set (&set, loc, false);
2642               else
2643                 var_mem_delete_and_set (&set, loc, false);
2644
2645               emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2646             }
2647             break;
2648
2649           case MO_USE_NO_VAR:
2650             {
2651               rtx loc = VTI (bb)->mos[i].u.loc;
2652
2653               if (REG_P (loc))
2654                 var_reg_delete (&set, loc, false);
2655               else
2656                 var_mem_delete (&set, loc, false);
2657
2658               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2659             }
2660             break;
2661
2662           case MO_CLOBBER:
2663             {
2664               rtx loc = VTI (bb)->mos[i].u.loc;
2665
2666               if (REG_P (loc))
2667                 var_reg_delete (&set, loc, true);
2668               else
2669                 var_mem_delete (&set, loc, true);
2670
2671               emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2672             }
2673             break;
2674
2675           case MO_ADJUST:
2676             set.stack_adjust += VTI (bb)->mos[i].u.adjust;
2677             break;
2678         }
2679     }
2680   dataflow_set_destroy (&set);
2681 }
2682
2683 /* Emit notes for the whole function.  */
2684
2685 static void
2686 vt_emit_notes (void)
2687 {
2688   basic_block bb;
2689   dataflow_set *last_out;
2690   dataflow_set empty;
2691
2692   gcc_assert (!htab_elements (changed_variables));
2693
2694   /* Enable emitting notes by functions (mainly by set_variable_part and
2695      delete_variable_part).  */
2696   emit_notes = true;
2697
2698   dataflow_set_init (&empty, 7);
2699   last_out = &empty;
2700
2701   FOR_EACH_BB (bb)
2702     {
2703       /* Emit the notes for changes of variable locations between two
2704          subsequent basic blocks.  */
2705       emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in);
2706
2707       /* Emit the notes for the changes in the basic block itself.  */
2708       emit_notes_in_bb (bb);
2709
2710       last_out = &VTI (bb)->out;
2711     }
2712   dataflow_set_destroy (&empty);
2713   emit_notes = false;
2714 }
2715
2716 /* If there is a declaration and offset associated with register/memory RTL
2717    assign declaration to *DECLP and offset to *OFFSETP, and return true.  */
2718
2719 static bool
2720 vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp)
2721 {
2722   if (REG_P (rtl))
2723     {
2724       if (REG_ATTRS (rtl))
2725         {
2726           *declp = REG_EXPR (rtl);
2727           *offsetp = REG_OFFSET (rtl);
2728           return true;
2729         }
2730     }
2731   else if (MEM_P (rtl))
2732     {
2733       if (MEM_ATTRS (rtl))
2734         {
2735           *declp = MEM_EXPR (rtl);
2736           *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0;
2737           return true;
2738         }
2739     }
2740   return false;
2741 }
2742
2743 /* Insert function parameters to IN and OUT sets of ENTRY_BLOCK.  */
2744
2745 static void
2746 vt_add_function_parameters (void)
2747 {
2748   tree parm;
2749
2750   for (parm = DECL_ARGUMENTS (current_function_decl);
2751        parm; parm = TREE_CHAIN (parm))
2752     {
2753       rtx decl_rtl = DECL_RTL_IF_SET (parm);
2754       rtx incoming = DECL_INCOMING_RTL (parm);
2755       tree decl;
2756       HOST_WIDE_INT offset;
2757       dataflow_set *out;
2758
2759       if (TREE_CODE (parm) != PARM_DECL)
2760         continue;
2761
2762       if (!DECL_NAME (parm))
2763         continue;
2764
2765       if (!decl_rtl || !incoming)
2766         continue;
2767
2768       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
2769         continue;
2770
2771       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
2772         if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
2773           continue;
2774
2775       if (!decl)
2776         continue;
2777
2778       gcc_assert (parm == decl);
2779
2780       out = &VTI (ENTRY_BLOCK_PTR)->out;
2781
2782       if (REG_P (incoming))
2783         {
2784           gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER);
2785           attrs_list_insert (&out->regs[REGNO (incoming)],
2786                              parm, offset, incoming);
2787           set_variable_part (out, incoming, parm, offset);
2788         }
2789       else if (MEM_P (incoming))
2790         set_variable_part (out, incoming, parm, offset);
2791     }
2792 }
2793
2794 /* Allocate and initialize the data structures for variable tracking
2795    and parse the RTL to get the micro operations.  */
2796
2797 static void
2798 vt_initialize (void)
2799 {
2800   basic_block bb;
2801
2802   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
2803
2804   FOR_EACH_BB (bb)
2805     {
2806       rtx insn;
2807       HOST_WIDE_INT pre, post = 0;
2808
2809       /* Count the number of micro operations.  */
2810       VTI (bb)->n_mos = 0;
2811       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2812            insn = NEXT_INSN (insn))
2813         {
2814           if (INSN_P (insn))
2815             {
2816               if (!frame_pointer_needed)
2817                 {
2818                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2819                   if (pre)
2820                     VTI (bb)->n_mos++;
2821                   if (post)
2822                     VTI (bb)->n_mos++;
2823                 }
2824               note_uses (&PATTERN (insn), count_uses_1, insn);
2825               note_stores (PATTERN (insn), count_stores, insn);
2826               if (CALL_P (insn))
2827                 VTI (bb)->n_mos++;
2828             }
2829         }
2830
2831       /* Add the micro-operations to the array.  */
2832       VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos);
2833       VTI (bb)->n_mos = 0;
2834       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2835            insn = NEXT_INSN (insn))
2836         {
2837           if (INSN_P (insn))
2838             {
2839               int n1, n2;
2840
2841               if (!frame_pointer_needed)
2842                 {
2843                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2844                   if (pre)
2845                     {
2846                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2847
2848                       mo->type = MO_ADJUST;
2849                       mo->u.adjust = pre;
2850                       mo->insn = insn;
2851                     }
2852                 }
2853
2854               n1 = VTI (bb)->n_mos;
2855               note_uses (&PATTERN (insn), add_uses_1, insn);
2856               n2 = VTI (bb)->n_mos - 1;
2857
2858               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
2859               while (n1 < n2)
2860                 {
2861                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
2862                     n1++;
2863                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
2864                     n2--;
2865                   if (n1 < n2)
2866                     {
2867                       micro_operation sw;
2868
2869                       sw = VTI (bb)->mos[n1];
2870                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2871                       VTI (bb)->mos[n2] = sw;
2872                     }
2873                 }
2874
2875               if (CALL_P (insn))
2876                 {
2877                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2878
2879                   mo->type = MO_CALL;
2880                   mo->insn = insn;
2881                 }
2882
2883               n1 = VTI (bb)->n_mos;
2884               /* This will record NEXT_INSN (insn), such that we can
2885                  insert notes before it without worrying about any
2886                  notes that MO_USEs might emit after the insn.  */
2887               note_stores (PATTERN (insn), add_stores, insn);
2888               n2 = VTI (bb)->n_mos - 1;
2889
2890               /* Order the MO_CLOBBERs to be before MO_SETs.  */
2891               while (n1 < n2)
2892                 {
2893                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER)
2894                     n1++;
2895                   while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET
2896                                      || VTI (bb)->mos[n2].type == MO_COPY))
2897                     n2--;
2898                   if (n1 < n2)
2899                     {
2900                       micro_operation sw;
2901
2902                       sw = VTI (bb)->mos[n1];
2903                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2904                       VTI (bb)->mos[n2] = sw;
2905                     }
2906                 }
2907
2908               if (!frame_pointer_needed && post)
2909                 {
2910                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2911
2912                   mo->type = MO_ADJUST;
2913                   mo->u.adjust = post;
2914                   mo->insn = insn;
2915                 }
2916             }
2917         }
2918     }
2919
2920   /* Init the IN and OUT sets.  */
2921   FOR_ALL_BB (bb)
2922     {
2923       VTI (bb)->visited = false;
2924       dataflow_set_init (&VTI (bb)->in, 7);
2925       dataflow_set_init (&VTI (bb)->out, 7);
2926     }
2927
2928   attrs_pool = create_alloc_pool ("attrs_def pool",
2929                                   sizeof (struct attrs_def), 1024);
2930   var_pool = create_alloc_pool ("variable_def pool",
2931                                 sizeof (struct variable_def), 64);
2932   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
2933                                       sizeof (struct location_chain_def),
2934                                       1024);
2935   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
2936                                    NULL);
2937   vt_add_function_parameters ();
2938 }
2939
2940 /* Free the data structures needed for variable tracking.  */
2941
2942 static void
2943 vt_finalize (void)
2944 {
2945   basic_block bb;
2946
2947   FOR_EACH_BB (bb)
2948     {
2949       free (VTI (bb)->mos);
2950     }
2951
2952   FOR_ALL_BB (bb)
2953     {
2954       dataflow_set_destroy (&VTI (bb)->in);
2955       dataflow_set_destroy (&VTI (bb)->out);
2956     }
2957   free_aux_for_blocks ();
2958   free_alloc_pool (attrs_pool);
2959   free_alloc_pool (var_pool);
2960   free_alloc_pool (loc_chain_pool);
2961   htab_delete (changed_variables);
2962 }
2963
2964 /* The entry point to variable tracking pass.  */
2965
2966 unsigned int
2967 variable_tracking_main (void)
2968 {
2969   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
2970     return 0;
2971
2972   mark_dfs_back_edges ();
2973   vt_initialize ();
2974   if (!frame_pointer_needed)
2975     {
2976       if (!vt_stack_adjustments ())
2977         {
2978           vt_finalize ();
2979           return 0;
2980         }
2981     }
2982
2983   vt_find_locations ();
2984   vt_emit_notes ();
2985
2986   if (dump_file && (dump_flags & TDF_DETAILS))
2987     {
2988       dump_dataflow_sets ();
2989       dump_flow_info (dump_file, dump_flags);
2990     }
2991
2992   vt_finalize ();
2993   return 0;
2994 }
2995 \f
2996 static bool
2997 gate_handle_var_tracking (void)
2998 {
2999   return (flag_var_tracking);
3000 }
3001
3002
3003
3004 struct tree_opt_pass pass_variable_tracking =
3005 {
3006   "vartrack",                           /* name */
3007   gate_handle_var_tracking,             /* gate */
3008   variable_tracking_main,               /* execute */
3009   NULL,                                 /* sub */
3010   NULL,                                 /* next */
3011   0,                                    /* static_pass_number */
3012   TV_VAR_TRACKING,                      /* tv_id */
3013   0,                                    /* properties_required */
3014   0,                                    /* properties_provided */
3015   0,                                    /* properties_destroyed */
3016   0,                                    /* todo_flags_start */
3017   TODO_dump_func,                       /* todo_flags_finish */
3018   'V'                                   /* letter */
3019 };
3020