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