gcc/var-tracking.c

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