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