gcc/var-tracking.c

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