gcc/var-tracking.c

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