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