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