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