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 /* 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 *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));
 538   sp = 0;
 539
 540   /* Push the first edge on to the stack.  */
 541   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 542
 543   while (sp)
 544     {
 545       edge e;
 546       basic_block src;
 547       basic_block dest;
 548
 549       /* Look at the edge on the top of the stack.  */
 550       e = stack[sp - 1];
 551       src = e->src;
 552       dest = e->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 (dest->succ)
 562             /* Since the DEST node has been visited for the first
 563                time, check its successors.  */
 564             stack[sp++] = dest->succ;
 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 (e->succ_next)
 576             /* Go to the next edge.  */
 577             stack[sp - 1] = e->succ_next;
 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
1445   /* If EXPR is not a parameter or a variable do not track it.  */
1446   if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL)
1447     return 0;
1448
1449   /* It also must have a name...  */
1450   if (!DECL_NAME (expr))
1451     return 0;
1452
1453   /* ... and a RTL assigned to it.  */
1454   decl_rtl = DECL_RTL_IF_SET (expr);
1455   if (!decl_rtl)
1456     return 0;
1457
1458   /* Do not track EXPR if it should be ignored for debugging purposes.  */
1459   if (DECL_IGNORED_P (expr))
1460     return 0;
1461
1462   /* Do not track global variables until we are able to emit correct location
1463      list for them.  */
1464   if (TREE_STATIC (expr))
1465     return 0;
1466
1467   /* When the EXPR is a DECL for alias of some variable (see example)
1468      the TREE_STATIC flag is not used.  Disable tracking all DECLs whose
1469      DECL_RTL contains SYMBOL_REF.
1470
1471      Example:
1472      extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv")));
1473      char **_dl_argv;
1474   */
1475   if (MEM_P (decl_rtl)
1476       && contains_symbol_ref (XEXP (decl_rtl, 0)))
1477     return 0;
1478
1479   /* If RTX is a memory it should not be very large (because it would be
1480      an array or struct).  */
1481   if (MEM_P (decl_rtl))
1482     {
1483       /* Do not track structures and arrays.  */
1484       if (GET_MODE (decl_rtl) == BLKmode)
1485         return 0;
1486       if (MEM_SIZE (decl_rtl)
1487           && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS)
1488         return 0;
1489     }
1490
1491   return 1;
1492 }
1493
1494 /* Count uses (register and memory references) LOC which will be tracked.
1495    INSN is instruction which the LOC is part of.  */
1496
1497 static int
1498 count_uses (rtx *loc, void *insn)
1499 {
1500   basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1501
1502   if (REG_P (*loc))
1503     {
1504 #ifdef ENABLE_CHECKING
1505         if (REGNO (*loc) >= FIRST_PSEUDO_REGISTER)
1506           abort ();
1507 #endif
1508         VTI (bb)->n_mos++;
1509     }
1510   else if (MEM_P (*loc)
1511            && MEM_EXPR (*loc)
1512            && track_expr_p (MEM_EXPR (*loc)))
1513     {
1514           VTI (bb)->n_mos++;
1515     }
1516
1517   return 0;
1518 }
1519
1520 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1521
1522 static void
1523 count_uses_1 (rtx *x, void *insn)
1524 {
1525   for_each_rtx (x, count_uses, insn);
1526 }
1527
1528 /* Count stores (register and memory references) LOC which will be tracked.
1529    INSN is instruction which the LOC is part of.  */
1530
1531 static void
1532 count_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn)
1533 {
1534   count_uses (&loc, insn);
1535 }
1536
1537 /* Add uses (register and memory references) LOC which will be tracked
1538    to VTI (bb)->mos.  INSN is instruction which the LOC is part of.  */
1539
1540 static int
1541 add_uses (rtx *loc, void *insn)
1542 {
1543   if (REG_P (*loc))
1544     {
1545       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1546       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1547
1548       mo->type = ((REG_EXPR (*loc) && track_expr_p (REG_EXPR (*loc)))
1549                   ? MO_USE : MO_USE_NO_VAR);
1550       mo->u.loc = *loc;
1551       mo->insn = (rtx) insn;
1552     }
1553   else if (MEM_P (*loc)
1554            && MEM_EXPR (*loc)
1555            && track_expr_p (MEM_EXPR (*loc)))
1556     {
1557       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1558       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1559
1560       mo->type = MO_USE;
1561       mo->u.loc = *loc;
1562       mo->insn = (rtx) insn;
1563     }
1564
1565   return 0;
1566 }
1567
1568 /* Helper function for finding all uses of REG/MEM in X in insn INSN.  */
1569
1570 static void
1571 add_uses_1 (rtx *x, void *insn)
1572 {
1573   for_each_rtx (x, add_uses, insn);
1574 }
1575
1576 /* Add stores (register and memory references) LOC which will be tracked
1577    to VTI (bb)->mos. EXPR is the RTL expression containing the store.
1578    INSN is instruction which the LOC is part of.  */
1579
1580 static void
1581 add_stores (rtx loc, rtx expr, void *insn)
1582 {
1583   if (REG_P (loc))
1584     {
1585       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1586       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1587
1588       mo->type = ((GET_CODE (expr) != CLOBBER && REG_EXPR (loc)
1589                    && track_expr_p (REG_EXPR (loc)))
1590                   ? MO_SET : MO_CLOBBER);
1591       mo->u.loc = loc;
1592       mo->insn = (rtx) insn;
1593     }
1594   else if (MEM_P (loc)
1595            && MEM_EXPR (loc)
1596            && track_expr_p (MEM_EXPR (loc)))
1597     {
1598       basic_block bb = BLOCK_FOR_INSN ((rtx) insn);
1599       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
1600
1601       mo->type = GET_CODE (expr) == CLOBBER ? MO_CLOBBER : MO_SET;
1602       mo->u.loc = loc;
1603       mo->insn = (rtx) insn;
1604     }
1605 }
1606
1607 /* Compute the changes of variable locations in the basic block BB.  */
1608
1609 static bool
1610 compute_bb_dataflow (basic_block bb)
1611 {
1612   int i, n, r;
1613   bool changed;
1614   dataflow_set old_out;
1615   dataflow_set *in = &VTI (bb)->in;
1616   dataflow_set *out = &VTI (bb)->out;
1617
1618   dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3);
1619   dataflow_set_copy (&old_out, out);
1620   dataflow_set_copy (out, in);
1621
1622   n = VTI (bb)->n_mos;
1623   for (i = 0; i < n; i++)
1624     {
1625       switch (VTI (bb)->mos[i].type)
1626         {
1627           case MO_CALL:
1628             for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
1629               if (TEST_HARD_REG_BIT (call_used_reg_set, r))
1630                 var_regno_delete (out, r);
1631             break;
1632
1633           case MO_USE:
1634           case MO_SET:
1635             {
1636               rtx loc = VTI (bb)->mos[i].u.loc;
1637
1638               if (REG_P (loc))
1639                 var_reg_delete_and_set (out, loc);
1640               else if (MEM_P (loc))
1641                 var_mem_delete_and_set (out, loc);
1642             }
1643             break;
1644
1645           case MO_USE_NO_VAR:
1646           case MO_CLOBBER:
1647             {
1648               rtx loc = VTI (bb)->mos[i].u.loc;
1649
1650               if (REG_P (loc))
1651                 var_reg_delete (out, loc);
1652               else if (MEM_P (loc))
1653                 var_mem_delete (out, loc);
1654             }
1655             break;
1656
1657           case MO_ADJUST:
1658             {
1659               rtx base;
1660
1661               out->stack_adjust += VTI (bb)->mos[i].u.adjust;
1662               base = gen_rtx_MEM (Pmode, plus_constant (stack_pointer_rtx,
1663                                                         out->stack_adjust));
1664               set_frame_base_location (out, base);
1665             }
1666             break;
1667         }
1668     }
1669
1670   changed = dataflow_set_different (&old_out, out);
1671   dataflow_set_destroy (&old_out);
1672   return changed;
1673 }
1674
1675 /* Find the locations of variables in the whole function.  */
1676
1677 static void
1678 vt_find_locations (void)
1679 {
1680   fibheap_t worklist, pending, fibheap_swap;
1681   sbitmap visited, in_worklist, in_pending, sbitmap_swap;
1682   basic_block bb;
1683   edge e;
1684   int *bb_order;
1685   int *rc_order;
1686   int i;
1687
1688   /* Compute reverse completion order of depth first search of the CFG
1689      so that the data-flow runs faster.  */
1690   rc_order = xmalloc (n_basic_blocks * sizeof (int));
1691   bb_order = xmalloc (last_basic_block * sizeof (int));
1692   flow_depth_first_order_compute (NULL, rc_order);
1693   for (i = 0; i < n_basic_blocks; i++)
1694     bb_order[rc_order[i]] = i;
1695   free (rc_order);
1696
1697   worklist = fibheap_new ();
1698   pending = fibheap_new ();
1699   visited = sbitmap_alloc (last_basic_block);
1700   in_worklist = sbitmap_alloc (last_basic_block);
1701   in_pending = sbitmap_alloc (last_basic_block);
1702   sbitmap_zero (in_worklist);
1703
1704   FOR_EACH_BB (bb)
1705     fibheap_insert (pending, bb_order[bb->index], bb);
1706   sbitmap_ones (in_pending);
1707
1708   while (!fibheap_empty (pending))
1709     {
1710       fibheap_swap = pending;
1711       pending = worklist;
1712       worklist = fibheap_swap;
1713       sbitmap_swap = in_pending;
1714       in_pending = in_worklist;
1715       in_worklist = sbitmap_swap;
1716
1717       sbitmap_zero (visited);
1718
1719       while (!fibheap_empty (worklist))
1720         {
1721           bb = fibheap_extract_min (worklist);
1722           RESET_BIT (in_worklist, bb->index);
1723           if (!TEST_BIT (visited, bb->index))
1724             {
1725               bool changed;
1726
1727               SET_BIT (visited, bb->index);
1728
1729               /* Calculate the IN set as union of predecessor OUT sets.  */
1730               dataflow_set_clear (&VTI (bb)->in);
1731               for (e = bb->pred; e; e = e->pred_next)
1732                 {
1733                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
1734                 }
1735
1736               changed = compute_bb_dataflow (bb);
1737               if (changed)
1738                 {
1739                   for (e = bb->succ; e; e = e->succ_next)
1740                     {
1741                       if (e->dest == EXIT_BLOCK_PTR)
1742                         continue;
1743
1744                       if (e->dest == bb)
1745                         continue;
1746
1747                       if (TEST_BIT (visited, e->dest->index))
1748                         {
1749                           if (!TEST_BIT (in_pending, e->dest->index))
1750                             {
1751                               /* Send E->DEST to next round.  */
1752                               SET_BIT (in_pending, e->dest->index);
1753                               fibheap_insert (pending,
1754                                               bb_order[e->dest->index],
1755                                               e->dest);
1756                             }
1757                         }
1758                       else if (!TEST_BIT (in_worklist, e->dest->index))
1759                         {
1760                           /* Add E->DEST to current round.  */
1761                           SET_BIT (in_worklist, e->dest->index);
1762                           fibheap_insert (worklist, bb_order[e->dest->index],
1763                                           e->dest);
1764                         }
1765                     }
1766                 }
1767             }
1768         }
1769     }
1770
1771   free (bb_order);
1772   fibheap_delete (worklist);
1773   fibheap_delete (pending);
1774   sbitmap_free (visited);
1775   sbitmap_free (in_worklist);
1776   sbitmap_free (in_pending);
1777 }
1778
1779 /* Print the content of the LIST to dump file.  */
1780
1781 static void
1782 dump_attrs_list (attrs list)
1783 {
1784   for (; list; list = list->next)
1785     {
1786       print_mem_expr (dump_file, list->decl);
1787       fprintf (dump_file, "+");
1788       fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC, list->offset);
1789     }
1790   fprintf (dump_file, "\n");
1791 }
1792
1793 /* Print the information about variable *SLOT to dump file.  */
1794
1795 static int
1796 dump_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1797 {
1798   variable var = *(variable *) slot;
1799   int i;
1800   location_chain node;
1801
1802   fprintf (dump_file, "  name: %s\n",
1803            IDENTIFIER_POINTER (DECL_NAME (var->decl)));
1804   for (i = 0; i < var->n_var_parts; i++)
1805     {
1806       fprintf (dump_file, "    offset %ld\n",
1807                (long) var->var_part[i].offset);
1808       for (node = var->var_part[i].loc_chain; node; node = node->next)
1809         {
1810           fprintf (dump_file, "      ");
1811           print_rtl_single (dump_file, node->loc);
1812         }
1813     }
1814
1815   /* Continue traversing the hash table.  */
1816   return 1;
1817 }
1818
1819 /* Print the information about variables from hash table VARS to dump file.  */
1820
1821 static void
1822 dump_vars (htab_t vars)
1823 {
1824   if (htab_elements (vars) > 0)
1825     {
1826       fprintf (dump_file, "Variables:\n");
1827       htab_traverse (vars, dump_variable, NULL);
1828     }
1829 }
1830
1831 /* Print the dataflow set SET to dump file.  */
1832
1833 static void
1834 dump_dataflow_set (dataflow_set *set)
1835 {
1836   int i;
1837
1838   fprintf (dump_file, "Stack adjustment: ");
1839   fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC, set->stack_adjust);
1840   fprintf (dump_file, "\n");
1841   for (i = 1; i < FIRST_PSEUDO_REGISTER; i++)
1842     {
1843       if (set->regs[i])
1844         {
1845           fprintf (dump_file, "Reg %d:", i);
1846           dump_attrs_list (set->regs[i]);
1847         }
1848     }
1849   dump_vars (set->vars);
1850   fprintf (dump_file, "\n");
1851 }
1852
1853 /* Print the IN and OUT sets for each basic block to dump file.  */
1854
1855 static void
1856 dump_dataflow_sets (void)
1857 {
1858   basic_block bb;
1859
1860   FOR_EACH_BB (bb)
1861     {
1862       fprintf (dump_file, "\nBasic block %d:\n", bb->index);
1863       fprintf (dump_file, "IN:\n");
1864       dump_dataflow_set (&VTI (bb)->in);
1865       fprintf (dump_file, "OUT:\n");
1866       dump_dataflow_set (&VTI (bb)->out);
1867     }
1868 }
1869
1870 /* Add variable VAR to the hash table of changed variables and
1871    if it has no locations delete it from hash table HTAB.  */
1872
1873 static void
1874 variable_was_changed (variable var, htab_t htab)
1875 {
1876   hashval_t hash = VARIABLE_HASH_VAL (var->decl);
1877
1878   if (emit_notes)
1879     {
1880       variable *slot;
1881
1882       slot = (variable *) htab_find_slot_with_hash (changed_variables,
1883                                                     var->decl, hash, INSERT);
1884
1885       if (htab && var->n_var_parts == 0)
1886         {
1887           variable empty_var;
1888           void **old;
1889
1890           empty_var = pool_alloc (var_pool);
1891           empty_var->decl = var->decl;
1892           empty_var->refcount = 1;
1893           empty_var->n_var_parts = 0;
1894           *slot = empty_var;
1895
1896           old = htab_find_slot_with_hash (htab, var->decl, hash,
1897                                           NO_INSERT);
1898           if (old)
1899             htab_clear_slot (htab, old);
1900         }
1901       else
1902         {
1903           *slot = var;
1904         }
1905     }
1906   else
1907     {
1908 #ifdef ENABLE_CHECKING
1909       if (!htab)
1910         abort ();
1911 #endif
1912       if (var->n_var_parts == 0)
1913         {
1914           void **slot = htab_find_slot_with_hash (htab, var->decl, hash,
1915                                                   NO_INSERT);
1916           if (slot)
1917             htab_clear_slot (htab, slot);
1918         }
1919     }
1920 }
1921
1922 /* Set the location of frame_base_decl to LOC in dataflow set SET.  This
1923    function expects that frame_base_decl has already one location for offset 0
1924    in the variable table.  */
1925
1926 static void
1927 set_frame_base_location (dataflow_set *set, rtx loc)
1928 {
1929   variable var;
1930
1931   var = htab_find_with_hash (set->vars, frame_base_decl,
1932                              VARIABLE_HASH_VAL (frame_base_decl));
1933 #ifdef ENABLE_CHECKING
1934   if (!var)
1935     abort ();
1936   if (var->n_var_parts != 1)
1937     abort ();
1938   if (var->var_part[0].offset != 0)
1939     abort ();
1940   if (!var->var_part[0].loc_chain)
1941     abort ();
1942 #endif
1943
1944   /* If frame_base_decl is shared unshare it first.  */
1945   if (var->refcount > 1)
1946     var = unshare_variable (set, var);
1947
1948   var->var_part[0].loc_chain->loc = loc;
1949   var->var_part[0].cur_loc = loc;
1950   variable_was_changed (var, set->vars);
1951 }
1952
1953 /* Set the part of variable's location in the dataflow set SET.  The variable
1954    part is specified by variable's declaration DECL and offset OFFSET and the
1955    part's location by LOC.  */
1956
1957 static void
1958 set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset)
1959 {
1960   int pos, low, high;
1961   location_chain node, next;
1962   location_chain *nextp;
1963   variable var;
1964   void **slot;
1965
1966   slot = htab_find_slot_with_hash (set->vars, decl,
1967                                    VARIABLE_HASH_VAL (decl), INSERT);
1968   if (!*slot)
1969     {
1970       /* Create new variable information.  */
1971       var = pool_alloc (var_pool);
1972       var->decl = decl;
1973       var->refcount = 1;
1974       var->n_var_parts = 1;
1975       var->var_part[0].offset = offset;
1976       var->var_part[0].loc_chain = NULL;
1977       var->var_part[0].cur_loc = NULL;
1978       *slot = var;
1979       pos = 0;
1980     }
1981   else
1982     {
1983       var = (variable) *slot;
1984
1985       /* Find the location part.  */
1986       low = 0;
1987       high = var->n_var_parts;
1988       while (low != high)
1989         {
1990           pos = (low + high) / 2;
1991           if (var->var_part[pos].offset < offset)
1992             low = pos + 1;
1993           else
1994             high = pos;
1995         }
1996       pos = low;
1997
1998       if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
1999         {
2000           node = var->var_part[pos].loc_chain;
2001
2002           if (node
2003               && ((REG_P (node->loc) && REG_P (loc)
2004                    && REGNO (node->loc) == REGNO (loc))
2005                   || rtx_equal_p (node->loc, loc)))
2006             {
2007               /* LOC is in the beginning of the chain so we have nothing
2008                  to do.  */
2009               return;
2010             }
2011           else
2012             {
2013               /* We have to make a copy of a shared variable.  */
2014               if (var->refcount > 1)
2015                 var = unshare_variable (set, var);
2016             }
2017         }
2018       else
2019         {
2020           /* We have not found the location part, new one will be created.  */
2021
2022           /* We have to make a copy of the shared variable.  */
2023           if (var->refcount > 1)
2024             var = unshare_variable (set, var);
2025
2026 #ifdef ENABLE_CHECKING
2027           /* We track only variables whose size is <= MAX_VAR_PARTS bytes
2028              thus there are at most MAX_VAR_PARTS different offsets.  */
2029           if (var->n_var_parts >= MAX_VAR_PARTS)
2030             abort ();
2031 #endif
2032
2033           /* We have to move the elements of array starting at index low to the
2034              next position.  */
2035           for (high = var->n_var_parts; high > low; high--)
2036             var->var_part[high] = var->var_part[high - 1];
2037
2038           var->n_var_parts++;
2039           var->var_part[pos].offset = offset;
2040           var->var_part[pos].loc_chain = NULL;
2041           var->var_part[pos].cur_loc = NULL;
2042         }
2043     }
2044
2045   /* Delete the location from the list.  */
2046   nextp = &var->var_part[pos].loc_chain;
2047   for (node = var->var_part[pos].loc_chain; node; node = next)
2048     {
2049       next = node->next;
2050       if ((REG_P (node->loc) && REG_P (loc)
2051            && REGNO (node->loc) == REGNO (loc))
2052           || rtx_equal_p (node->loc, loc))
2053         {
2054           pool_free (loc_chain_pool, node);
2055           *nextp = next;
2056           break;
2057         }
2058       else
2059         nextp = &node->next;
2060     }
2061
2062   /* Add the location to the beginning.  */
2063   node = pool_alloc (loc_chain_pool);
2064   node->loc = loc;
2065   node->next = var->var_part[pos].loc_chain;
2066   var->var_part[pos].loc_chain = node;
2067
2068   /* If no location was emitted do so.  */
2069   if (var->var_part[pos].cur_loc == NULL)
2070     {
2071       var->var_part[pos].cur_loc = loc;
2072       variable_was_changed (var, set->vars);
2073     }
2074 }
2075
2076 /* Delete the part of variable's location from dataflow set SET.  The variable
2077    part is specified by variable's declaration DECL and offset OFFSET and the
2078    part's location by LOC.  */
2079
2080 static void
2081 delete_variable_part (dataflow_set *set, rtx loc, tree decl,
2082                       HOST_WIDE_INT offset)
2083 {
2084   int pos, low, high;
2085   void **slot;
2086
2087   slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl),
2088                                    NO_INSERT);
2089   if (slot)
2090     {
2091       variable var = (variable) *slot;
2092
2093       /* Find the location part.  */
2094       low = 0;
2095       high = var->n_var_parts;
2096       while (low != high)
2097         {
2098           pos = (low + high) / 2;
2099           if (var->var_part[pos].offset < offset)
2100             low = pos + 1;
2101           else
2102             high = pos;
2103         }
2104       pos = low;
2105
2106       if (pos < var->n_var_parts && var->var_part[pos].offset == offset)
2107         {
2108           location_chain node, next;
2109           location_chain *nextp;
2110           bool changed;
2111
2112           if (var->refcount > 1)
2113             {
2114               /* If the variable contains the location part we have to
2115                  make a copy of the variable.  */
2116               for (node = var->var_part[pos].loc_chain; node;
2117                    node = node->next)
2118                 {
2119                   if ((REG_P (node->loc) && REG_P (loc)
2120                        && REGNO (node->loc) == REGNO (loc))
2121                       || rtx_equal_p (node->loc, loc))
2122                     {
2123                       var = unshare_variable (set, var);
2124                       break;
2125                     }
2126                 }
2127             }
2128
2129           /* Delete the location part.  */
2130           nextp = &var->var_part[pos].loc_chain;
2131           for (node = *nextp; node; node = next)
2132             {
2133               next = node->next;
2134               if ((REG_P (node->loc) && REG_P (loc)
2135                    && REGNO (node->loc) == REGNO (loc))
2136                   || rtx_equal_p (node->loc, loc))
2137                 {
2138                   pool_free (loc_chain_pool, node);
2139                   *nextp = next;
2140                   break;
2141                 }
2142               else
2143                 nextp = &node->next;
2144             }
2145
2146           /* If we have deleted the location which was last emitted
2147              we have to emit new location so add the variable to set
2148              of changed variables.  */
2149           if (var->var_part[pos].cur_loc
2150               && ((REG_P (loc)
2151                    && REG_P (var->var_part[pos].cur_loc)
2152                    && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
2153                   || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
2154             {
2155               changed = true;
2156               if (var->var_part[pos].loc_chain)
2157                 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
2158             }
2159           else
2160             changed = false;
2161
2162           if (var->var_part[pos].loc_chain == NULL)
2163             {
2164               var->n_var_parts--;
2165               while (pos < var->n_var_parts)
2166                 {
2167                   var->var_part[pos] = var->var_part[pos + 1];
2168                   pos++;
2169                 }
2170             }
2171           if (changed)
2172               variable_was_changed (var, set->vars);
2173         }
2174     }
2175 }
2176
2177 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
2178    additional parameters: WHERE specifies whether the note shall be emitted
2179    before of after instruction INSN.  */
2180
2181 static int
2182 emit_note_insn_var_location (void **varp, void *data)
2183 {
2184   variable var = *(variable *) varp;
2185   rtx insn = ((emit_note_data *)data)->insn;
2186   enum emit_note_where where = ((emit_note_data *)data)->where;
2187   rtx note;
2188   int i;
2189   bool complete;
2190   HOST_WIDE_INT last_limit;
2191   tree type_size_unit;
2192
2193 #ifdef ENABLE_CHECKING
2194   if (!var->decl)
2195     abort ();
2196 #endif
2197
2198   complete = true;
2199   last_limit = 0;
2200   for (i = 0; i < var->n_var_parts; i++)
2201     {
2202       if (last_limit < var->var_part[i].offset)
2203         {
2204           complete = false;
2205           break;
2206         }
2207       last_limit
2208         = (var->var_part[i].offset
2209            + GET_MODE_SIZE (GET_MODE (var->var_part[i].loc_chain->loc)));
2210     }
2211   type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl));
2212   if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit))
2213     complete = false;
2214
2215   if (where == EMIT_NOTE_AFTER_INSN)
2216     note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn);
2217   else
2218     note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn);
2219
2220   if (!complete)
2221     {
2222       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2223                                                        NULL_RTX);
2224     }
2225   else if (var->n_var_parts == 1)
2226     {
2227       rtx expr_list
2228         = gen_rtx_EXPR_LIST (VOIDmode,
2229                              var->var_part[0].loc_chain->loc,
2230                              GEN_INT (var->var_part[0].offset));
2231
2232       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2233                                                        expr_list);
2234     }
2235   else if (var->n_var_parts)
2236     {
2237       rtx argp[MAX_VAR_PARTS];
2238       rtx parallel;
2239
2240       for (i = 0; i < var->n_var_parts; i++)
2241         argp[i] = gen_rtx_EXPR_LIST (VOIDmode, var->var_part[i].loc_chain->loc,
2242                                      GEN_INT (var->var_part[i].offset));
2243       parallel = gen_rtx_PARALLEL (VOIDmode,
2244                                    gen_rtvec_v (var->n_var_parts, argp));
2245       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl,
2246                                                        parallel);
2247     }
2248
2249   htab_clear_slot (changed_variables, varp);
2250
2251   /* When there are no location parts the variable has been already
2252      removed from hash table and a new empty variable was created.
2253      Free the empty variable.  */
2254   if (var->n_var_parts == 0)
2255     {
2256       pool_free (var_pool, var);
2257     }
2258
2259   /* Continue traversing the hash table.  */
2260   return 1;
2261 }
2262
2263 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
2264    CHANGED_VARIABLES and delete this chain.  WHERE specifies whether the notes
2265    shall be emitted before of after instruction INSN.  */
2266
2267 static void
2268 emit_notes_for_changes (rtx insn, enum emit_note_where where)
2269 {
2270   emit_note_data data;
2271
2272   data.insn = insn;
2273   data.where = where;
2274   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
2275 }
2276
2277 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the
2278    same variable in hash table DATA or is not there at all.  */
2279
2280 static int
2281 emit_notes_for_differences_1 (void **slot, void *data)
2282 {
2283   htab_t new_vars = (htab_t) data;
2284   variable old_var, new_var;
2285
2286   old_var = *(variable *) slot;
2287   new_var = htab_find_with_hash (new_vars, old_var->decl,
2288                                  VARIABLE_HASH_VAL (old_var->decl));
2289
2290   if (!new_var)
2291     {
2292       /* Variable has disappeared.  */
2293       variable empty_var;
2294
2295       empty_var = pool_alloc (var_pool);
2296       empty_var->decl = old_var->decl;
2297       empty_var->refcount = 1;
2298       empty_var->n_var_parts = 0;
2299       variable_was_changed (empty_var, NULL);
2300     }
2301   else if (variable_different_p (old_var, new_var, true))
2302     {
2303       variable_was_changed (new_var, NULL);
2304     }
2305
2306   /* Continue traversing the hash table.  */
2307   return 1;
2308 }
2309
2310 /* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash
2311    table DATA.  */
2312
2313 static int
2314 emit_notes_for_differences_2 (void **slot, void *data)
2315 {
2316   htab_t old_vars = (htab_t) data;
2317   variable old_var, new_var;
2318
2319   new_var = *(variable *) slot;
2320   old_var = htab_find_with_hash (old_vars, new_var->decl,
2321                                  VARIABLE_HASH_VAL (new_var->decl));
2322   if (!old_var)
2323     {
2324       /* Variable has appeared.  */
2325       variable_was_changed (new_var, NULL);
2326     }
2327
2328   /* Continue traversing the hash table.  */
2329   return 1;
2330 }
2331
2332 /* Emit notes before INSN for differences between dataflow sets OLD_SET and
2333    NEW_SET.  */
2334
2335 static void
2336 emit_notes_for_differences (rtx insn, dataflow_set *old_set,
2337                             dataflow_set *new_set)
2338 {
2339   htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars);
2340   htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars);
2341   emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2342 }
2343
2344 /* Emit the notes for changes of location parts in the basic block BB.  */
2345
2346 static void
2347 emit_notes_in_bb (basic_block bb)
2348 {
2349   int i;
2350   dataflow_set set;
2351
2352   dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3);
2353   dataflow_set_copy (&set, &VTI (bb)->in);
2354
2355   for (i = 0; i < VTI (bb)->n_mos; i++)
2356     {
2357       rtx insn = VTI (bb)->mos[i].insn;
2358
2359       switch (VTI (bb)->mos[i].type)
2360         {
2361           case MO_CALL:
2362             {
2363               int r;
2364
2365               for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
2366                 if (TEST_HARD_REG_BIT (call_used_reg_set, r))
2367                   {
2368                     var_regno_delete (&set, r);
2369                   }
2370               emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2371             }
2372             break;
2373
2374           case MO_USE:
2375           case MO_SET:
2376             {
2377               rtx loc = VTI (bb)->mos[i].u.loc;
2378
2379               if (REG_P (loc))
2380                 var_reg_delete_and_set (&set, loc);
2381               else
2382                 var_mem_delete_and_set (&set, loc);
2383
2384               if (VTI (bb)->mos[i].type == MO_USE)
2385                 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN);
2386               else
2387                 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN);
2388             }
2389             break;
2390
2391           case MO_USE_NO_VAR:
2392           case MO_CLOBBER:
2393             {
2394               rtx loc = VTI (bb)->mos[i].u.loc;
2395
2396               if (REG_P (loc))
2397                 var_reg_delete (&set, loc);
2398               else
2399                 var_mem_delete (&set, loc);
2400
2401               if (VTI (bb)->mos[i].type == MO_USE_NO_VAR)
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_ADJUST:
2409             {
2410               rtx base;
2411
2412               set.stack_adjust += VTI (bb)->mos[i].u.adjust;
2413               base = gen_rtx_MEM (Pmode, plus_constant (stack_pointer_rtx,
2414                                                         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 (MEM_P (rtl))
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
2494   for (parm = DECL_ARGUMENTS (current_function_decl);
2495        parm; parm = TREE_CHAIN (parm))
2496     {
2497       rtx decl_rtl = DECL_RTL_IF_SET (parm);
2498       rtx incoming = DECL_INCOMING_RTL (parm);
2499       tree decl;
2500       HOST_WIDE_INT offset;
2501       dataflow_set *out;
2502
2503       if (TREE_CODE (parm) != PARM_DECL)
2504         continue;
2505
2506       if (!DECL_NAME (parm))
2507         continue;
2508
2509       if (!decl_rtl || !incoming)
2510         continue;
2511
2512       if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode)
2513         continue;
2514
2515       if (!vt_get_decl_and_offset (incoming, &decl, &offset))
2516         if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset))
2517           continue;
2518
2519       if (!decl)
2520         continue;
2521
2522 #ifdef ENABLE_CHECKING
2523       if (parm != decl)
2524         abort ();
2525 #endif
2526
2527       incoming = eliminate_regs (incoming, 0, NULL_RTX);
2528       out = &VTI (ENTRY_BLOCK_PTR)->out;
2529
2530       if (REG_P (incoming))
2531         {
2532 #ifdef ENABLE_CHECKING
2533           if (REGNO (incoming) >= FIRST_PSEUDO_REGISTER)
2534             abort ();
2535 #endif
2536           attrs_list_insert (&out->regs[REGNO (incoming)],
2537                              parm, offset, incoming);
2538           set_variable_part (out, incoming, parm, offset);
2539         }
2540       else if (MEM_P (incoming))
2541         {
2542           set_variable_part (out, incoming, parm, offset);
2543         }
2544     }
2545 }
2546
2547 /* Allocate and initialize the data structures for variable tracking
2548    and parse the RTL to get the micro operations.  */
2549
2550 static void
2551 vt_initialize (void)
2552 {
2553   basic_block bb;
2554
2555   alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def));
2556
2557   FOR_EACH_BB (bb)
2558     {
2559       rtx insn;
2560       HOST_WIDE_INT pre, post;
2561
2562       /* Count the number of micro operations.  */
2563       VTI (bb)->n_mos = 0;
2564       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2565            insn = NEXT_INSN (insn))
2566         {
2567           if (INSN_P (insn))
2568             {
2569               if (!frame_pointer_needed)
2570                 {
2571                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2572                   if (pre)
2573                     VTI (bb)->n_mos++;
2574                   if (post)
2575                     VTI (bb)->n_mos++;
2576                 }
2577               note_uses (&PATTERN (insn), count_uses_1, insn);
2578               note_stores (PATTERN (insn), count_stores, insn);
2579               if (CALL_P (insn))
2580                 VTI (bb)->n_mos++;
2581             }
2582         }
2583
2584       /* Add the micro-operations to the array.  */
2585       VTI (bb)->mos = xmalloc (VTI (bb)->n_mos
2586                                * sizeof (struct micro_operation_def));
2587       VTI (bb)->n_mos = 0;
2588       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2589            insn = NEXT_INSN (insn))
2590         {
2591           if (INSN_P (insn))
2592             {
2593               int n1, n2;
2594
2595               if (!frame_pointer_needed)
2596                 {
2597                   insn_stack_adjust_offset_pre_post (insn, &pre, &post);
2598                   if (pre)
2599                     {
2600                       micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2601
2602                       mo->type = MO_ADJUST;
2603                       mo->u.adjust = pre;
2604                       mo->insn = insn;
2605                     }
2606                 }
2607
2608               n1 = VTI (bb)->n_mos;
2609               note_uses (&PATTERN (insn), add_uses_1, insn);
2610               n2 = VTI (bb)->n_mos - 1;
2611
2612               /* Order the MO_USEs to be before MO_USE_NO_VARs.  */
2613               while (n1 < n2)
2614                 {
2615                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE)
2616                     n1++;
2617                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR)
2618                     n2--;
2619                   if (n1 < n2)
2620                     {
2621                       micro_operation sw;
2622
2623                       sw = VTI (bb)->mos[n1];
2624                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2625                       VTI (bb)->mos[n2] = sw;
2626                     }
2627                 }
2628
2629               if (CALL_P (insn))
2630                 {
2631                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2632
2633                   mo->type = MO_CALL;
2634                   mo->insn = insn;
2635                 }
2636
2637               n1 = VTI (bb)->n_mos;
2638               note_stores (PATTERN (insn), add_stores, insn);
2639               n2 = VTI (bb)->n_mos - 1;
2640
2641               /* Order the MO_SETs to be before MO_CLOBBERs.  */
2642               while (n1 < n2)
2643                 {
2644                   while (n1 < n2 && VTI (bb)->mos[n1].type == MO_SET)
2645                     n1++;
2646                   while (n1 < n2 && VTI (bb)->mos[n2].type == MO_CLOBBER)
2647                     n2--;
2648                   if (n1 < n2)
2649                     {
2650                       micro_operation sw;
2651
2652                       sw = VTI (bb)->mos[n1];
2653                       VTI (bb)->mos[n1] = VTI (bb)->mos[n2];
2654                       VTI (bb)->mos[n2] = sw;
2655                     }
2656                 }
2657
2658               if (!frame_pointer_needed && post)
2659                 {
2660                   micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++;
2661
2662                   mo->type = MO_ADJUST;
2663                   mo->u.adjust = post;
2664                   mo->insn = insn;
2665                 }
2666             }
2667         }
2668     }
2669
2670   /* Init the IN and OUT sets.  */
2671   FOR_ALL_BB (bb)
2672     {
2673       VTI (bb)->visited = false;
2674       dataflow_set_init (&VTI (bb)->in, 7);
2675       dataflow_set_init (&VTI (bb)->out, 7);
2676     }
2677
2678   attrs_pool = create_alloc_pool ("attrs_def pool",
2679                                   sizeof (struct attrs_def), 1024);
2680   var_pool = create_alloc_pool ("variable_def pool",
2681                                 sizeof (struct variable_def), 64);
2682   loc_chain_pool = create_alloc_pool ("location_chain_def pool",
2683                                       sizeof (struct location_chain_def),
2684                                       1024);
2685   changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq,
2686                                    NULL);
2687   vt_add_function_parameters ();
2688
2689   if (!frame_pointer_needed)
2690     {
2691       rtx base;
2692
2693       /* Create fake variable for tracking stack pointer changes.  */
2694       frame_base_decl = make_node (VAR_DECL);
2695       DECL_NAME (frame_base_decl) = get_identifier ("___frame_base_decl");
2696       TREE_TYPE (frame_base_decl) = char_type_node;
2697       DECL_ARTIFICIAL (frame_base_decl) = 1;
2698
2699       /* Set its initial "location".  */
2700       frame_stack_adjust = -prologue_stack_adjust ();
2701       base = gen_rtx_MEM (Pmode, plus_constant (stack_pointer_rtx,
2702                                                 frame_stack_adjust));
2703       set_variable_part (&VTI (ENTRY_BLOCK_PTR)->out, base, frame_base_decl, 0);
2704     }
2705   else
2706     {
2707       frame_base_decl = NULL;
2708     }
2709 }
2710
2711 /* Free the data structures needed for variable tracking.  */
2712
2713 static void
2714 vt_finalize (void)
2715 {
2716   basic_block bb;
2717
2718   FOR_EACH_BB (bb)
2719     {
2720       free (VTI (bb)->mos);
2721     }
2722
2723   FOR_ALL_BB (bb)
2724     {
2725       dataflow_set_destroy (&VTI (bb)->in);
2726       dataflow_set_destroy (&VTI (bb)->out);
2727     }
2728   free_aux_for_blocks ();
2729   free_alloc_pool (attrs_pool);
2730   free_alloc_pool (var_pool);
2731   free_alloc_pool (loc_chain_pool);
2732   htab_delete (changed_variables);
2733 }
2734
2735 /* The entry point to variable tracking pass.  */
2736
2737 void
2738 variable_tracking_main (void)
2739 {
2740   if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20)
2741     return;
2742
2743   mark_dfs_back_edges ();
2744   vt_initialize ();
2745   if (!frame_pointer_needed)
2746     {
2747       if (!vt_stack_adjustments ())
2748         {
2749           vt_finalize ();
2750           return;
2751         }
2752     }
2753
2754   vt_find_locations ();
2755   vt_emit_notes ();
2756
2757   if (dump_file)
2758     {
2759       dump_dataflow_sets ();
2760       dump_flow_info (dump_file);
2761     }
2762
2763   vt_finalize ();
2764 }