gcc/var-tracking.c

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