contrib/gcc/var-tracking.c

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