gcc/var-tracking.c

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