1254721Semaste/* Variable tracking routines for the GNU compiler. 2254721Semaste Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3254721Semaste 4254721Semaste This file is part of GCC. 5254721Semaste 6254721Semaste GCC is free software; you can redistribute it and/or modify it 7254721Semaste under the terms of the GNU General Public License as published by 8254721Semaste the Free Software Foundation; either version 2, or (at your option) 9254721Semaste any later version. 10254721Semaste 11254721Semaste GCC is distributed in the hope that it will be useful, but WITHOUT 12254721Semaste ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13254721Semaste or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14254721Semaste License for more details. 15254721Semaste 16254721Semaste You should have received a copy of the GNU General Public License 17254721Semaste along with GCC; see the file COPYING. If not, write to the Free 18254721Semaste Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19254721Semaste 02110-1301, USA. */ 20254721Semaste 21254721Semaste/* This file contains the variable tracking pass. It computes where 22254721Semaste variables are located (which registers or where in memory) at each position 23254721Semaste in instruction stream and emits notes describing the locations. 24254721Semaste Debug information (DWARF2 location lists) is finally generated from 25254721Semaste these notes. 26254721Semaste With this debug information, it is possible to show variables 27254721Semaste even when debugging optimized code. 28254721Semaste 29254721Semaste How does the variable tracking pass work? 30254721Semaste 31254721Semaste First, it scans RTL code for uses, stores and clobbers (register/memory 32254721Semaste references in instructions), for call insns and for stack adjustments 33254721Semaste separately for each basic block and saves them to an array of micro 34254721Semaste operations. 35254721Semaste The micro operations of one instruction are ordered so that 36254721Semaste pre-modifying stack adjustment < use < use with no var < call insn < 37254721Semaste < set < clobber < post-modifying stack adjustment 38254721Semaste 39254721Semaste Then, a forward dataflow analysis is performed to find out how locations 40254721Semaste of variables change through code and to propagate the variable locations 41263367Semaste along control flow graph. 42254721Semaste The IN set for basic block BB is computed as a union of OUT sets of BB's 43254721Semaste predecessors, the OUT set for BB is copied from the IN set for BB and 44254721Semaste is changed according to micro operations in BB. 45254721Semaste 46254721Semaste The IN and OUT sets for basic blocks consist of a current stack adjustment 47254721Semaste (used for adjusting offset of variables addressed using stack pointer), 48254721Semaste the table of structures describing the locations of parts of a variable 49254721Semaste and for each physical register a linked list for each physical register. 50254721Semaste The linked list is a list of variable parts stored in the register, 51263367Semaste i.e. it is a list of triplets (reg, decl, offset) where decl is 52263367Semaste REG_EXPR (reg) and offset is REG_OFFSET (reg). The linked list is used for 53263367Semaste effective deleting appropriate variable parts when we set or clobber the 54263367Semaste register. 55263367Semaste 56263367Semaste There may be more than one variable part in a register. The linked lists 57263367Semaste should be pretty short so it is a good data structure here. 58263367Semaste For example in the following code, register allocator may assign same 59263367Semaste register to variables A and B, and both of them are stored in the same 60263367Semaste register in CODE: 61263367Semaste 62263367Semaste if (cond) 63263367Semaste set A; 64263367Semaste else 65263367Semaste set B; 66263367Semaste CODE; 67263367Semaste if (cond) 68263367Semaste use A; 69263367Semaste else 70263367Semaste use B; 71263367Semaste 72263367Semaste Finally, the NOTE_INSN_VAR_LOCATION notes describing the variable locations 73263367Semaste are emitted to appropriate positions in RTL code. Each such a note describes 74263367Semaste the location of one variable at the point in instruction stream where the 75263367Semaste note is. There is no need to emit a note for each variable before each 76263367Semaste instruction, we only emit these notes where the location of variable changes 77263367Semaste (this means that we also emit notes for changes between the OUT set of the 78263367Semaste previous block and the IN set of the current block). 79263367Semaste 80263367Semaste The notes consist of two parts: 81263367Semaste 1. the declaration (from REG_EXPR or MEM_EXPR) 82263367Semaste 2. the location of a variable - it is either a simple register/memory 83263367Semaste reference (for simple variables, for example int), 84263367Semaste or a parallel of register/memory references (for a large variables 85263367Semaste which consist of several parts, for example long long). 86254721Semaste 87254721Semaste*/ 88254721Semaste 89254721Semaste#include "config.h" 90254721Semaste#include "system.h" 91254721Semaste#include "coretypes.h" 92254721Semaste#include "tm.h" 93254721Semaste#include "rtl.h" 94254721Semaste#include "tree.h" 95254721Semaste#include "hard-reg-set.h" 96263367Semaste#include "basic-block.h" 97254721Semaste#include "flags.h" 98254721Semaste#include "output.h" 99254721Semaste#include "insn-config.h" 100254721Semaste#include "reload.h" 101254721Semaste#include "sbitmap.h" 102254721Semaste#include "alloc-pool.h" 103254721Semaste#include "fibheap.h" 104254721Semaste#include "hashtab.h" 105254721Semaste#include "regs.h" 106254721Semaste#include "expr.h" 107254721Semaste#include "timevar.h" 108254721Semaste#include "tree-pass.h" 109254721Semaste 110254721Semaste/* Type of micro operation. */ 111254721Semasteenum micro_operation_type 112254721Semaste{ 113254721Semaste MO_USE, /* Use location (REG or MEM). */ 114254721Semaste MO_USE_NO_VAR,/* Use location which is not associated with a variable 115254721Semaste or the variable is not trackable. */ 116254721Semaste MO_SET, /* Set location. */ 117254721Semaste MO_COPY, /* Copy the same portion of a variable from one 118254721Semaste location to another. */ 119254721Semaste MO_CLOBBER, /* Clobber location. */ 120254721Semaste MO_CALL, /* Call insn. */ 121254721Semaste MO_ADJUST /* Adjust stack pointer. */ 122254721Semaste}; 123254721Semaste 124254721Semaste/* Where shall the note be emitted? BEFORE or AFTER the instruction. */ 125254721Semasteenum emit_note_where 126254721Semaste{ 127254721Semaste EMIT_NOTE_BEFORE_INSN, 128254721Semaste EMIT_NOTE_AFTER_INSN 129254721Semaste}; 130254721Semaste 131254721Semaste/* Structure holding information about micro operation. */ 132254721Semastetypedef struct micro_operation_def 133254721Semaste{ 134254721Semaste /* Type of micro operation. */ 135254721Semaste enum micro_operation_type type; 136254721Semaste 137254721Semaste union { 138254721Semaste /* Location. */ 139254721Semaste rtx loc; 140254721Semaste 141254721Semaste /* Stack adjustment. */ 142254721Semaste HOST_WIDE_INT adjust; 143254721Semaste } u; 144254721Semaste 145254721Semaste /* The instruction which the micro operation is in, for MO_USE, 146254721Semaste MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent 147254721Semaste instruction or note in the original flow (before any var-tracking 148254721Semaste notes are inserted, to simplify emission of notes), for MO_SET 149254721Semaste and MO_CLOBBER. */ 150254721Semaste rtx insn; 151254721Semaste} micro_operation; 152254721Semaste 153254721Semaste/* Structure for passing some other parameters to function 154254721Semaste emit_note_insn_var_location. */ 155254721Semastetypedef struct emit_note_data_def 156254721Semaste{ 157254721Semaste /* The instruction which the note will be emitted before/after. */ 158254721Semaste rtx insn; 159254721Semaste 160254721Semaste /* Where the note will be emitted (before/after insn)? */ 161254721Semaste enum emit_note_where where; 162254721Semaste} emit_note_data; 163254721Semaste 164254721Semaste/* Description of location of a part of a variable. The content of a physical 165254721Semaste register is described by a chain of these structures. 166254721Semaste The chains are pretty short (usually 1 or 2 elements) and thus 167254721Semaste chain is the best data structure. */ 168254721Semastetypedef struct attrs_def 169254721Semaste{ 170254721Semaste /* Pointer to next member of the list. */ 171254721Semaste struct attrs_def *next; 172254721Semaste 173254721Semaste /* The rtx of register. */ 174254721Semaste rtx loc; 175254721Semaste 176254721Semaste /* The declaration corresponding to LOC. */ 177254721Semaste tree decl; 178254721Semaste 179254721Semaste /* Offset from start of DECL. */ 180254721Semaste HOST_WIDE_INT offset; 181254721Semaste} *attrs; 182254721Semaste 183254721Semaste/* Structure holding the IN or OUT set for a basic block. */ 184254721Semastetypedef struct dataflow_set_def 185254721Semaste{ 186254721Semaste /* Adjustment of stack offset. */ 187254721Semaste HOST_WIDE_INT stack_adjust; 188254721Semaste 189254721Semaste /* Attributes for registers (lists of attrs). */ 190254721Semaste attrs regs[FIRST_PSEUDO_REGISTER]; 191254721Semaste 192254721Semaste /* Variable locations. */ 193254721Semaste htab_t vars; 194254721Semaste} dataflow_set; 195254721Semaste 196254721Semaste/* The structure (one for each basic block) containing the information 197254721Semaste needed for variable tracking. */ 198254721Semastetypedef struct variable_tracking_info_def 199254721Semaste{ 200254721Semaste /* Number of micro operations stored in the MOS array. */ 201254721Semaste int n_mos; 202254721Semaste 203254721Semaste /* The array of micro operations. */ 204254721Semaste micro_operation *mos; 205254721Semaste 206254721Semaste /* The IN and OUT set for dataflow analysis. */ 207254721Semaste dataflow_set in; 208254721Semaste dataflow_set out; 209254721Semaste 210254721Semaste /* Has the block been visited in DFS? */ 211254721Semaste bool visited; 212254721Semaste} *variable_tracking_info; 213254721Semaste 214254721Semaste/* Structure for chaining the locations. */ 215254721Semastetypedef struct location_chain_def 216254721Semaste{ 217254721Semaste /* Next element in the chain. */ 218254721Semaste struct location_chain_def *next; 219254721Semaste 220254721Semaste /* The location (REG or MEM). */ 221254721Semaste rtx loc; 222254721Semaste} *location_chain; 223254721Semaste 224254721Semaste/* Structure describing one part of variable. */ 225254721Semastetypedef struct variable_part_def 226254721Semaste{ 227254721Semaste /* Chain of locations of the part. */ 228254721Semaste location_chain loc_chain; 229254721Semaste 230254721Semaste /* Location which was last emitted to location list. */ 231254721Semaste rtx cur_loc; 232254721Semaste 233254721Semaste /* The offset in the variable. */ 234254721Semaste HOST_WIDE_INT offset; 235254721Semaste} variable_part; 236254721Semaste 237254721Semaste/* Maximum number of location parts. */ 238254721Semaste#define MAX_VAR_PARTS 16 239254721Semaste 240254721Semaste/* Structure describing where the variable is located. */ 241254721Semastetypedef struct variable_def 242254721Semaste{ 243254721Semaste /* The declaration of the variable. */ 244254721Semaste tree decl; 245254721Semaste 246254721Semaste /* Reference count. */ 247254721Semaste int refcount; 248254721Semaste 249254721Semaste /* Number of variable parts. */ 250254721Semaste int n_var_parts; 251254721Semaste 252254721Semaste /* The variable parts. */ 253254721Semaste variable_part var_part[MAX_VAR_PARTS]; 254254721Semaste} *variable; 255254721Semaste 256254721Semaste/* Hash function for DECL for VARIABLE_HTAB. */ 257254721Semaste#define VARIABLE_HASH_VAL(decl) (DECL_UID (decl)) 258254721Semaste 259254721Semaste/* Pointer to the BB's information specific to variable tracking pass. */ 260254721Semaste#define VTI(BB) ((variable_tracking_info) (BB)->aux) 261254721Semaste 262254721Semaste/* Alloc pool for struct attrs_def. */ 263254721Semastestatic alloc_pool attrs_pool; 264254721Semaste 265254721Semaste/* Alloc pool for struct variable_def. */ 266254721Semastestatic alloc_pool var_pool; 267254721Semaste 268254721Semaste/* Alloc pool for struct location_chain_def. */ 269254721Semastestatic alloc_pool loc_chain_pool; 270254721Semaste 271254721Semaste/* Changed variables, notes will be emitted for them. */ 272254721Semastestatic htab_t changed_variables; 273254721Semaste 274254721Semaste/* Shall notes be emitted? */ 275254721Semastestatic bool emit_notes; 276254721Semaste 277254721Semaste/* Local function prototypes. */ 278254721Semastestatic void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *, 279254721Semaste HOST_WIDE_INT *); 280254721Semastestatic void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *, 281254721Semaste HOST_WIDE_INT *); 282254721Semastestatic void bb_stack_adjust_offset (basic_block); 283254721Semastestatic bool vt_stack_adjustments (void); 284254721Semastestatic rtx adjust_stack_reference (rtx, HOST_WIDE_INT); 285254721Semastestatic hashval_t variable_htab_hash (const void *); 286254721Semastestatic int variable_htab_eq (const void *, const void *); 287254721Semastestatic void variable_htab_free (void *); 288254721Semaste 289254721Semastestatic void init_attrs_list_set (attrs *); 290254721Semastestatic void attrs_list_clear (attrs *); 291254721Semastestatic attrs attrs_list_member (attrs, tree, HOST_WIDE_INT); 292254721Semastestatic void attrs_list_insert (attrs *, tree, HOST_WIDE_INT, rtx); 293254721Semastestatic void attrs_list_copy (attrs *, attrs); 294254721Semastestatic void attrs_list_union (attrs *, attrs); 295254721Semaste 296254721Semastestatic void vars_clear (htab_t); 297254721Semastestatic variable unshare_variable (dataflow_set *set, variable var); 298254721Semastestatic int vars_copy_1 (void **, void *); 299254721Semastestatic void vars_copy (htab_t, htab_t); 300254721Semastestatic tree var_debug_decl (tree); 301254721Semastestatic void var_reg_set (dataflow_set *, rtx); 302254721Semastestatic void var_reg_delete_and_set (dataflow_set *, rtx, bool); 303254721Semastestatic void var_reg_delete (dataflow_set *, rtx, bool); 304254721Semastestatic void var_regno_delete (dataflow_set *, int); 305254721Semastestatic void var_mem_set (dataflow_set *, rtx); 306254721Semastestatic void var_mem_delete_and_set (dataflow_set *, rtx, bool); 307254721Semastestatic void var_mem_delete (dataflow_set *, rtx, bool); 308254721Semaste 309254721Semastestatic void dataflow_set_init (dataflow_set *, int); 310254721Semastestatic void dataflow_set_clear (dataflow_set *); 311254721Semastestatic void dataflow_set_copy (dataflow_set *, dataflow_set *); 312254721Semastestatic int variable_union_info_cmp_pos (const void *, const void *); 313254721Semastestatic int variable_union (void **, void *); 314254721Semastestatic void dataflow_set_union (dataflow_set *, dataflow_set *); 315254721Semastestatic bool variable_part_different_p (variable_part *, variable_part *); 316254721Semastestatic bool variable_different_p (variable, variable, bool); 317254721Semastestatic int dataflow_set_different_1 (void **, void *); 318254721Semastestatic int dataflow_set_different_2 (void **, void *); 319254721Semastestatic bool dataflow_set_different (dataflow_set *, dataflow_set *); 320254721Semastestatic void dataflow_set_destroy (dataflow_set *); 321254721Semaste 322254721Semastestatic bool contains_symbol_ref (rtx); 323254721Semastestatic bool track_expr_p (tree); 324254721Semastestatic bool same_variable_part_p (rtx, tree, HOST_WIDE_INT); 325254721Semastestatic int count_uses (rtx *, void *); 326254721Semastestatic void count_uses_1 (rtx *, void *); 327254721Semastestatic void count_stores (rtx, rtx, void *); 328254721Semastestatic int add_uses (rtx *, void *); 329254721Semastestatic void add_uses_1 (rtx *, void *); 330254721Semastestatic void add_stores (rtx, rtx, void *); 331254721Semastestatic bool compute_bb_dataflow (basic_block); 332254721Semastestatic void vt_find_locations (void); 333254721Semaste 334254721Semastestatic void dump_attrs_list (attrs); 335254721Semastestatic int dump_variable (void **, void *); 336254721Semastestatic void dump_vars (htab_t); 337254721Semastestatic void dump_dataflow_set (dataflow_set *); 338254721Semastestatic void dump_dataflow_sets (void); 339254721Semaste 340254721Semastestatic void variable_was_changed (variable, htab_t); 341254721Semastestatic void set_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 342254721Semastestatic void clobber_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 343254721Semastestatic void delete_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 344254721Semastestatic int emit_note_insn_var_location (void **, void *); 345254721Semastestatic void emit_notes_for_changes (rtx, enum emit_note_where); 346254721Semastestatic int emit_notes_for_differences_1 (void **, void *); 347254721Semastestatic int emit_notes_for_differences_2 (void **, void *); 348254721Semastestatic void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *); 349254721Semastestatic void emit_notes_in_bb (basic_block); 350254721Semastestatic void vt_emit_notes (void); 351254721Semaste 352254721Semastestatic bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *); 353254721Semastestatic void vt_add_function_parameters (void); 354254721Semastestatic void vt_initialize (void); 355254721Semastestatic void vt_finalize (void); 356254721Semaste 357254721Semaste/* Given a SET, calculate the amount of stack adjustment it contains 358254721Semaste PRE- and POST-modifying stack pointer. 359254721Semaste This function is similar to stack_adjust_offset. */ 360254721Semaste 361254721Semastestatic void 362254721Semastestack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre, 363254721Semaste HOST_WIDE_INT *post) 364254721Semaste{ 365254721Semaste rtx src = SET_SRC (pattern); 366254721Semaste rtx dest = SET_DEST (pattern); 367254721Semaste enum rtx_code code; 368254721Semaste 369254721Semaste if (dest == stack_pointer_rtx) 370254721Semaste { 371254721Semaste /* (set (reg sp) (plus (reg sp) (const_int))) */ 372254721Semaste code = GET_CODE (src); 373254721Semaste if (! (code == PLUS || code == MINUS) 374254721Semaste || XEXP (src, 0) != stack_pointer_rtx 375254721Semaste || GET_CODE (XEXP (src, 1)) != CONST_INT) 376254721Semaste return; 377254721Semaste 378254721Semaste if (code == MINUS) 379254721Semaste *post += INTVAL (XEXP (src, 1)); 380254721Semaste else 381254721Semaste *post -= INTVAL (XEXP (src, 1)); 382254721Semaste } 383254721Semaste else if (MEM_P (dest)) 384254721Semaste { 385254721Semaste /* (set (mem (pre_dec (reg sp))) (foo)) */ 386254721Semaste src = XEXP (dest, 0); 387254721Semaste code = GET_CODE (src); 388254721Semaste 389254721Semaste switch (code) 390254721Semaste { 391254721Semaste case PRE_MODIFY: 392254721Semaste case POST_MODIFY: 393254721Semaste if (XEXP (src, 0) == stack_pointer_rtx) 394254721Semaste { 395254721Semaste rtx val = XEXP (XEXP (src, 1), 1); 396254721Semaste /* We handle only adjustments by constant amount. */ 397254721Semaste gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS && 398254721Semaste GET_CODE (val) == CONST_INT); 399254721Semaste 400254721Semaste if (code == PRE_MODIFY) 401254721Semaste *pre -= INTVAL (val); 402254721Semaste else 403254721Semaste *post -= INTVAL (val); 404254721Semaste break; 405254721Semaste } 406254721Semaste return; 407254721Semaste 408254721Semaste case PRE_DEC: 409254721Semaste if (XEXP (src, 0) == stack_pointer_rtx) 410254721Semaste { 411254721Semaste *pre += GET_MODE_SIZE (GET_MODE (dest)); 412254721Semaste break; 413254721Semaste } 414254721Semaste return; 415254721Semaste 416254721Semaste case POST_DEC: 417254721Semaste if (XEXP (src, 0) == stack_pointer_rtx) 418254721Semaste { 419254721Semaste *post += GET_MODE_SIZE (GET_MODE (dest)); 420254721Semaste break; 421254721Semaste } 422254721Semaste return; 423254721Semaste 424254721Semaste case PRE_INC: 425254721Semaste if (XEXP (src, 0) == stack_pointer_rtx) 426254721Semaste { 427254721Semaste *pre -= GET_MODE_SIZE (GET_MODE (dest)); 428254721Semaste break; 429254721Semaste } 430254721Semaste return; 431254721Semaste 432254721Semaste case POST_INC: 433254721Semaste if (XEXP (src, 0) == stack_pointer_rtx) 434254721Semaste { 435254721Semaste *post -= GET_MODE_SIZE (GET_MODE (dest)); 436254721Semaste break; 437254721Semaste } 438254721Semaste return; 439254721Semaste 440254721Semaste default: 441254721Semaste return; 442254721Semaste } 443254721Semaste } 444254721Semaste} 445254721Semaste 446254721Semaste/* Given an INSN, calculate the amount of stack adjustment it contains 447254721Semaste PRE- and POST-modifying stack pointer. */ 448254721Semaste 449254721Semastestatic void 450254721Semasteinsn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre, 451254721Semaste HOST_WIDE_INT *post) 452254721Semaste{ 453254721Semaste *pre = 0; 454254721Semaste *post = 0; 455254721Semaste 456254721Semaste if (GET_CODE (PATTERN (insn)) == SET) 457254721Semaste stack_adjust_offset_pre_post (PATTERN (insn), pre, post); 458254721Semaste else if (GET_CODE (PATTERN (insn)) == PARALLEL 459254721Semaste || GET_CODE (PATTERN (insn)) == SEQUENCE) 460254721Semaste { 461254721Semaste int i; 462254721Semaste 463254721Semaste /* There may be stack adjustments inside compound insns. Search 464254721Semaste for them. */ 465254721Semaste for ( i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 466254721Semaste if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET) 467254721Semaste stack_adjust_offset_pre_post (XVECEXP (PATTERN (insn), 0, i), 468254721Semaste pre, post); 469254721Semaste } 470254721Semaste} 471254721Semaste 472254721Semaste/* Compute stack adjustment in basic block BB. */ 473254721Semaste 474254721Semastestatic void 475254721Semastebb_stack_adjust_offset (basic_block bb) 476254721Semaste{ 477254721Semaste HOST_WIDE_INT offset; 478254721Semaste int i; 479254721Semaste 480254721Semaste offset = VTI (bb)->in.stack_adjust; 481254721Semaste for (i = 0; i < VTI (bb)->n_mos; i++) 482254721Semaste { 483254721Semaste if (VTI (bb)->mos[i].type == MO_ADJUST) 484254721Semaste offset += VTI (bb)->mos[i].u.adjust; 485254721Semaste else if (VTI (bb)->mos[i].type != MO_CALL) 486254721Semaste { 487254721Semaste if (MEM_P (VTI (bb)->mos[i].u.loc)) 488254721Semaste { 489254721Semaste VTI (bb)->mos[i].u.loc 490254721Semaste = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset); 491254721Semaste } 492254721Semaste } 493254721Semaste } 494254721Semaste VTI (bb)->out.stack_adjust = offset; 495254721Semaste} 496254721Semaste 497254721Semaste/* Compute stack adjustments for all blocks by traversing DFS tree. 498254721Semaste Return true when the adjustments on all incoming edges are consistent. 499254721Semaste Heavily borrowed from pre_and_rev_post_order_compute. */ 500254721Semaste 501254721Semastestatic bool 502254721Semastevt_stack_adjustments (void) 503254721Semaste{ 504254721Semaste edge_iterator *stack; 505254721Semaste int sp; 506254721Semaste 507254721Semaste /* Initialize entry block. */ 508254721Semaste VTI (ENTRY_BLOCK_PTR)->visited = true; 509254721Semaste VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET; 510254721Semaste 511254721Semaste /* Allocate stack for back-tracking up CFG. */ 512254721Semaste stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 513254721Semaste sp = 0; 514254721Semaste 515254721Semaste /* Push the first edge on to the stack. */ 516254721Semaste stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 517254721Semaste 518254721Semaste while (sp) 519263363Semaste { 520254721Semaste edge_iterator ei; 521254721Semaste basic_block src; 522254721Semaste basic_block dest; 523254721Semaste 524254721Semaste /* Look at the edge on the top of the stack. */ 525254721Semaste ei = stack[sp - 1]; 526254721Semaste src = ei_edge (ei)->src; 527254721Semaste dest = ei_edge (ei)->dest; 528254721Semaste 529254721Semaste /* Check if the edge destination has been visited yet. */ 530254721Semaste if (!VTI (dest)->visited) 531254721Semaste { 532254721Semaste VTI (dest)->visited = true; 533254721Semaste VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust; 534254721Semaste bb_stack_adjust_offset (dest); 535254721Semaste 536254721Semaste if (EDGE_COUNT (dest->succs) > 0) 537254721Semaste /* Since the DEST node has been visited for the first 538254721Semaste time, check its successors. */ 539254721Semaste stack[sp++] = ei_start (dest->succs); 540254721Semaste } 541254721Semaste else 542254721Semaste { 543254721Semaste /* Check whether the adjustments on the edges are the same. */ 544254721Semaste if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust) 545254721Semaste { 546254721Semaste free (stack); 547254721Semaste return false; 548254721Semaste } 549254721Semaste 550254721Semaste if (! ei_one_before_end_p (ei)) 551254721Semaste /* Go to the next edge. */ 552254721Semaste ei_next (&stack[sp - 1]); 553254721Semaste else 554254721Semaste /* Return to previous level if there are no more edges. */ 555254721Semaste sp--; 556254721Semaste } 557254721Semaste } 558254721Semaste 559254721Semaste free (stack); 560254721Semaste return true; 561254721Semaste} 562254721Semaste 563254721Semaste/* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative 564254721Semaste to the argument pointer. Return the new rtx. */ 565254721Semaste 566254721Semastestatic rtx 567254721Semasteadjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment) 568254721Semaste{ 569254721Semaste rtx addr, cfa, tmp; 570254721Semaste 571254721Semaste#ifdef FRAME_POINTER_CFA_OFFSET 572254721Semaste adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl); 573254721Semaste cfa = plus_constant (frame_pointer_rtx, adjustment); 574254721Semaste#else 575254721Semaste adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl); 576254721Semaste cfa = plus_constant (arg_pointer_rtx, adjustment); 577254721Semaste#endif 578254721Semaste 579254721Semaste addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa); 580254721Semaste tmp = simplify_rtx (addr); 581254721Semaste if (tmp) 582254721Semaste addr = tmp; 583254721Semaste 584254721Semaste return replace_equiv_address_nv (mem, addr); 585254721Semaste} 586254721Semaste 587254721Semaste/* The hash function for variable_htab, computes the hash value 588254721Semaste from the declaration of variable X. */ 589254721Semaste 590254721Semastestatic hashval_t 591254721Semastevariable_htab_hash (const void *x) 592254721Semaste{ 593254721Semaste const variable v = (const variable) x; 594254721Semaste 595254721Semaste return (VARIABLE_HASH_VAL (v->decl)); 596254721Semaste} 597254721Semaste 598254721Semaste/* Compare the declaration of variable X with declaration Y. */ 599254721Semaste 600254721Semastestatic int 601254721Semastevariable_htab_eq (const void *x, const void *y) 602254721Semaste{ 603254721Semaste const variable v = (const variable) x; 604254721Semaste const tree decl = (const tree) y; 605254721Semaste 606254721Semaste return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl)); 607254721Semaste} 608254721Semaste 609254721Semaste/* Free the element of VARIABLE_HTAB (its type is struct variable_def). */ 610254721Semaste 611254721Semastestatic void 612254721Semastevariable_htab_free (void *elem) 613254721Semaste{ 614254721Semaste int i; 615254721Semaste variable var = (variable) elem; 616254721Semaste location_chain node, next; 617254721Semaste 618254721Semaste gcc_assert (var->refcount > 0); 619254721Semaste 620254721Semaste var->refcount--; 621254721Semaste if (var->refcount > 0) 622254721Semaste return; 623254721Semaste 624254721Semaste for (i = 0; i < var->n_var_parts; i++) 625254721Semaste { 626254721Semaste for (node = var->var_part[i].loc_chain; node; node = next) 627254721Semaste { 628254721Semaste next = node->next; 629254721Semaste pool_free (loc_chain_pool, node); 630254721Semaste } 631254721Semaste var->var_part[i].loc_chain = NULL; 632254721Semaste } 633254721Semaste pool_free (var_pool, var); 634254721Semaste} 635254721Semaste 636254721Semaste/* Initialize the set (array) SET of attrs to empty lists. */ 637254721Semaste 638254721Semastestatic void 639254721Semasteinit_attrs_list_set (attrs *set) 640254721Semaste{ 641254721Semaste int i; 642254721Semaste 643254721Semaste for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 644254721Semaste set[i] = NULL; 645254721Semaste} 646254721Semaste 647254721Semaste/* Make the list *LISTP empty. */ 648254721Semaste 649254721Semastestatic void 650254721Semasteattrs_list_clear (attrs *listp) 651254721Semaste{ 652254721Semaste attrs list, next; 653254721Semaste 654254721Semaste for (list = *listp; list; list = next) 655254721Semaste { 656254721Semaste next = list->next; 657254721Semaste pool_free (attrs_pool, list); 658254721Semaste } 659254721Semaste *listp = NULL; 660254721Semaste} 661254721Semaste 662254721Semaste/* Return true if the pair of DECL and OFFSET is the member of the LIST. */ 663254721Semaste 664254721Semastestatic attrs 665254721Semasteattrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset) 666254721Semaste{ 667254721Semaste for (; list; list = list->next) 668254721Semaste if (list->decl == decl && list->offset == offset) 669254721Semaste return list; 670254721Semaste return NULL; 671254721Semaste} 672254721Semaste 673254721Semaste/* Insert the triplet DECL, OFFSET, LOC to the list *LISTP. */ 674254721Semaste 675254721Semastestatic void 676254721Semasteattrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc) 677254721Semaste{ 678254721Semaste attrs list; 679254721Semaste 680254721Semaste list = pool_alloc (attrs_pool); 681254721Semaste list->loc = loc; 682254721Semaste list->decl = decl; 683254721Semaste list->offset = offset; 684254721Semaste list->next = *listp; 685254721Semaste *listp = list; 686254721Semaste} 687254721Semaste 688254721Semaste/* Copy all nodes from SRC and create a list *DSTP of the copies. */ 689254721Semaste 690254721Semastestatic void 691254721Semasteattrs_list_copy (attrs *dstp, attrs src) 692254721Semaste{ 693254721Semaste attrs n; 694254721Semaste 695254721Semaste attrs_list_clear (dstp); 696254721Semaste for (; src; src = src->next) 697254721Semaste { 698254721Semaste n = pool_alloc (attrs_pool); 699254721Semaste n->loc = src->loc; 700254721Semaste n->decl = src->decl; 701254721Semaste n->offset = src->offset; 702254721Semaste n->next = *dstp; 703254721Semaste *dstp = n; 704254721Semaste } 705254721Semaste} 706254721Semaste 707254721Semaste/* Add all nodes from SRC which are not in *DSTP to *DSTP. */ 708254721Semaste 709254721Semastestatic void 710254721Semasteattrs_list_union (attrs *dstp, attrs src) 711254721Semaste{ 712254721Semaste for (; src; src = src->next) 713254721Semaste { 714254721Semaste if (!attrs_list_member (*dstp, src->decl, src->offset)) 715254721Semaste attrs_list_insert (dstp, src->decl, src->offset, src->loc); 716254721Semaste } 717254721Semaste} 718254721Semaste 719254721Semaste/* Delete all variables from hash table VARS. */ 720254721Semaste 721254721Semastestatic void 722254721Semastevars_clear (htab_t vars) 723254721Semaste{ 724254721Semaste htab_empty (vars); 725254721Semaste} 726254721Semaste 727254721Semaste/* Return a copy of a variable VAR and insert it to dataflow set SET. */ 728254721Semaste 729254721Semastestatic variable 730254721Semasteunshare_variable (dataflow_set *set, variable var) 731254721Semaste{ 732254721Semaste void **slot; 733254721Semaste variable new_var; 734254721Semaste int i; 735254721Semaste 736254721Semaste new_var = pool_alloc (var_pool); 737254721Semaste new_var->decl = var->decl; 738254721Semaste new_var->refcount = 1; 739254721Semaste var->refcount--; 740254721Semaste new_var->n_var_parts = var->n_var_parts; 741254721Semaste 742254721Semaste for (i = 0; i < var->n_var_parts; i++) 743254721Semaste { 744254721Semaste location_chain node; 745254721Semaste location_chain *nextp; 746254721Semaste 747254721Semaste new_var->var_part[i].offset = var->var_part[i].offset; 748254721Semaste nextp = &new_var->var_part[i].loc_chain; 749254721Semaste for (node = var->var_part[i].loc_chain; node; node = node->next) 750263363Semaste { 751254721Semaste location_chain new_lc; 752254721Semaste 753254721Semaste new_lc = pool_alloc (loc_chain_pool); 754254721Semaste new_lc->next = NULL; 755254721Semaste new_lc->loc = node->loc; 756254721Semaste 757254721Semaste *nextp = new_lc; 758254721Semaste nextp = &new_lc->next; 759254721Semaste } 760254721Semaste 761254721Semaste /* We are at the basic block boundary when copying variable description 762254721Semaste so set the CUR_LOC to be the first element of the chain. */ 763254721Semaste if (new_var->var_part[i].loc_chain) 764254721Semaste new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc; 765254721Semaste else 766254721Semaste new_var->var_part[i].cur_loc = NULL; 767254721Semaste } 768254721Semaste 769254721Semaste slot = htab_find_slot_with_hash (set->vars, new_var->decl, 770254721Semaste VARIABLE_HASH_VAL (new_var->decl), 771254721Semaste INSERT); 772254721Semaste *slot = new_var; 773254721Semaste return new_var; 774254721Semaste} 775254721Semaste 776254721Semaste/* Add a variable from *SLOT to hash table DATA and increase its reference 777254721Semaste count. */ 778254721Semaste 779254721Semastestatic int 780254721Semastevars_copy_1 (void **slot, void *data) 781254721Semaste{ 782254721Semaste htab_t dst = (htab_t) data; 783254721Semaste variable src, *dstp; 784254721Semaste 785254721Semaste src = *(variable *) slot; 786254721Semaste src->refcount++; 787254721Semaste 788254721Semaste dstp = (variable *) htab_find_slot_with_hash (dst, src->decl, 789254721Semaste VARIABLE_HASH_VAL (src->decl), 790254721Semaste INSERT); 791254721Semaste *dstp = src; 792254721Semaste 793254721Semaste /* Continue traversing the hash table. */ 794254721Semaste return 1; 795254721Semaste} 796254721Semaste 797254721Semaste/* Copy all variables from hash table SRC to hash table DST. */ 798254721Semaste 799254721Semastestatic void 800254721Semastevars_copy (htab_t dst, htab_t src) 801254721Semaste{ 802254721Semaste vars_clear (dst); 803254721Semaste htab_traverse (src, vars_copy_1, dst); 804254721Semaste} 805254721Semaste 806254721Semaste/* Map a decl to its main debug decl. */ 807254721Semaste 808254721Semastestatic inline tree 809254721Semastevar_debug_decl (tree decl) 810254721Semaste{ 811254721Semaste if (decl && DECL_P (decl) 812254721Semaste && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl) 813254721Semaste && DECL_P (DECL_DEBUG_EXPR (decl))) 814254721Semaste decl = DECL_DEBUG_EXPR (decl); 815254721Semaste 816254721Semaste return decl; 817254721Semaste} 818254721Semaste 819254721Semaste/* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). */ 820254721Semaste 821254721Semastestatic void 822254721Semastevar_reg_set (dataflow_set *set, rtx loc) 823254721Semaste{ 824254721Semaste tree decl = REG_EXPR (loc); 825254721Semaste HOST_WIDE_INT offset = REG_OFFSET (loc); 826254721Semaste attrs node; 827254721Semaste 828254721Semaste decl = var_debug_decl (decl); 829254721Semaste 830254721Semaste for (node = set->regs[REGNO (loc)]; node; node = node->next) 831254721Semaste if (node->decl == decl && node->offset == offset) 832254721Semaste break; 833254721Semaste if (!node) 834254721Semaste attrs_list_insert (&set->regs[REGNO (loc)], decl, offset, loc); 835254721Semaste set_variable_part (set, loc, decl, offset); 836254721Semaste} 837254721Semaste 838254721Semaste/* Delete current content of register LOC in dataflow set SET and set 839254721Semaste the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). If 840254721Semaste MODIFY is true, any other live copies of the same variable part are 841254721Semaste also deleted from the dataflow set, otherwise the variable part is 842254721Semaste assumed to be copied from another location holding the same 843263367Semaste part. */ 844263367Semaste 845263367Semastestatic void 846263367Semastevar_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify) 847263367Semaste{ 848263367Semaste tree decl = REG_EXPR (loc); 849263367Semaste HOST_WIDE_INT offset = REG_OFFSET (loc); 850263367Semaste attrs node, next; 851263367Semaste attrs *nextp; 852263367Semaste 853263367Semaste decl = var_debug_decl (decl); 854263367Semaste 855263367Semaste nextp = &set->regs[REGNO (loc)]; 856263367Semaste for (node = *nextp; node; node = next) 857263367Semaste { 858263367Semaste next = node->next; 859263367Semaste if (node->decl != decl || node->offset != offset) 860263367Semaste { 861263367Semaste delete_variable_part (set, node->loc, node->decl, node->offset); 862254721Semaste pool_free (attrs_pool, node); 863263367Semaste *nextp = next; 864263367Semaste } 865263367Semaste else 866263367Semaste { 867263367Semaste node->loc = loc; 868263367Semaste nextp = &node->next; 869263367Semaste } 870263367Semaste } 871263367Semaste if (modify) 872263367Semaste clobber_variable_part (set, loc, decl, offset); 873263367Semaste var_reg_set (set, loc); 874263367Semaste} 875263367Semaste 876263367Semaste/* Delete current content of register LOC in dataflow set SET. If 877263367Semaste CLOBBER is true, also delete any other live copies of the same 878263367Semaste variable part. */ 879263367Semaste 880254721Semastestatic void 881254721Semastevar_reg_delete (dataflow_set *set, rtx loc, bool clobber) 882254721Semaste{ 883254721Semaste attrs *reg = &set->regs[REGNO (loc)]; 884254721Semaste attrs node, next; 885254721Semaste 886254721Semaste if (clobber) 887254721Semaste { 888254721Semaste tree decl = REG_EXPR (loc); 889254721Semaste HOST_WIDE_INT offset = REG_OFFSET (loc); 890254721Semaste 891254721Semaste decl = var_debug_decl (decl); 892254721Semaste 893254721Semaste clobber_variable_part (set, NULL, decl, offset); 894254721Semaste } 895254721Semaste 896254721Semaste for (node = *reg; node; node = next) 897254721Semaste { 898254721Semaste next = node->next; 899254721Semaste delete_variable_part (set, node->loc, node->decl, node->offset); 900254721Semaste pool_free (attrs_pool, node); 901254721Semaste } 902254721Semaste *reg = NULL; 903254721Semaste} 904254721Semaste 905254721Semaste/* Delete content of register with number REGNO in dataflow set SET. */ 906254721Semaste 907254721Semastestatic void 908254721Semastevar_regno_delete (dataflow_set *set, int regno) 909254721Semaste{ 910254721Semaste attrs *reg = &set->regs[regno]; 911254721Semaste attrs node, next; 912254721Semaste 913254721Semaste for (node = *reg; node; node = next) 914254721Semaste { 915254721Semaste next = node->next; 916254721Semaste delete_variable_part (set, node->loc, node->decl, node->offset); 917254721Semaste pool_free (attrs_pool, node); 918254721Semaste } 919254721Semaste *reg = NULL; 920254721Semaste} 921254721Semaste 922254721Semaste/* Set the location part of variable MEM_EXPR (LOC) in dataflow set 923254721Semaste SET to LOC. 924254721Semaste Adjust the address first if it is stack pointer based. */ 925254721Semaste 926254721Semastestatic void 927254721Semastevar_mem_set (dataflow_set *set, rtx loc) 928254721Semaste{ 929254721Semaste tree decl = MEM_EXPR (loc); 930254721Semaste HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0; 931254721Semaste 932254721Semaste decl = var_debug_decl (decl); 933254721Semaste 934254721Semaste set_variable_part (set, loc, decl, offset); 935254721Semaste} 936254721Semaste 937254721Semaste/* Delete and set the location part of variable MEM_EXPR (LOC) in 938254721Semaste dataflow set SET to LOC. If MODIFY is true, any other live copies 939254721Semaste of the same variable part are also deleted from the dataflow set, 940254721Semaste otherwise the variable part is assumed to be copied from another 941254721Semaste location holding the same part. 942254721Semaste Adjust the address first if it is stack pointer based. */ 943254721Semaste 944254721Semastestatic void 945254721Semastevar_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify) 946254721Semaste{ 947254721Semaste tree decl = MEM_EXPR (loc); 948254721Semaste HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0; 949254721Semaste 950254721Semaste decl = var_debug_decl (decl); 951254721Semaste 952254721Semaste if (modify) 953254721Semaste clobber_variable_part (set, NULL, decl, offset); 954254721Semaste var_mem_set (set, loc); 955254721Semaste} 956254721Semaste 957254721Semaste/* Delete the location part LOC from dataflow set SET. If CLOBBER is 958254721Semaste true, also delete any other live copies of the same variable part. 959254721Semaste Adjust the address first if it is stack pointer based. */ 960254721Semaste 961254721Semastestatic void 962254721Semastevar_mem_delete (dataflow_set *set, rtx loc, bool clobber) 963254721Semaste{ 964254721Semaste tree decl = MEM_EXPR (loc); 965254721Semaste HOST_WIDE_INT offset = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0; 966254721Semaste 967254721Semaste decl = var_debug_decl (decl); 968254721Semaste if (clobber) 969254721Semaste clobber_variable_part (set, NULL, decl, offset); 970254721Semaste delete_variable_part (set, loc, decl, offset); 971254721Semaste} 972254721Semaste 973254721Semaste/* Initialize dataflow set SET to be empty. 974254721Semaste VARS_SIZE is the initial size of hash table VARS. */ 975254721Semaste 976254721Semastestatic void 977254721Semastedataflow_set_init (dataflow_set *set, int vars_size) 978254721Semaste{ 979254721Semaste init_attrs_list_set (set->regs); 980254721Semaste set->vars = htab_create (vars_size, variable_htab_hash, variable_htab_eq, 981254721Semaste variable_htab_free); 982254721Semaste set->stack_adjust = 0; 983254721Semaste} 984254721Semaste 985254721Semaste/* Delete the contents of dataflow set SET. */ 986254721Semaste 987254721Semastestatic void 988254721Semastedataflow_set_clear (dataflow_set *set) 989254721Semaste{ 990254721Semaste int i; 991254721Semaste 992254721Semaste for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 993254721Semaste attrs_list_clear (&set->regs[i]); 994254721Semaste 995254721Semaste vars_clear (set->vars); 996254721Semaste} 997254721Semaste 998254721Semaste/* Copy the contents of dataflow set SRC to DST. */ 999254721Semaste 1000254721Semastestatic void 1001254721Semastedataflow_set_copy (dataflow_set *dst, dataflow_set *src) 1002254721Semaste{ 1003254721Semaste int i; 1004254721Semaste 1005254721Semaste for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1006254721Semaste attrs_list_copy (&dst->regs[i], src->regs[i]); 1007254721Semaste 1008254721Semaste vars_copy (dst->vars, src->vars); 1009254721Semaste dst->stack_adjust = src->stack_adjust; 1010254721Semaste} 1011254721Semaste 1012254721Semaste/* Information for merging lists of locations for a given offset of variable. 1013254721Semaste */ 1014254721Semastestruct variable_union_info 1015254721Semaste{ 1016254721Semaste /* Node of the location chain. */ 1017254721Semaste location_chain lc; 1018254721Semaste 1019254721Semaste /* The sum of positions in the input chains. */ 1020254721Semaste int pos; 1021254721Semaste 1022254721Semaste /* The position in the chains of SRC and DST dataflow sets. */ 1023254721Semaste int pos_src; 1024254721Semaste int pos_dst; 1025254721Semaste}; 1026254721Semaste 1027254721Semaste/* Compare function for qsort, order the structures by POS element. */ 1028254721Semaste 1029254721Semastestatic int 1030254721Semastevariable_union_info_cmp_pos (const void *n1, const void *n2) 1031254721Semaste{ 1032254721Semaste const struct variable_union_info *i1 = n1; 1033254721Semaste const struct variable_union_info *i2 = n2; 1034254721Semaste 1035254721Semaste if (i1->pos != i2->pos) 1036254721Semaste return i1->pos - i2->pos; 1037254721Semaste 1038254721Semaste return (i1->pos_dst - i2->pos_dst); 1039254721Semaste} 1040254721Semaste 1041254721Semaste/* Compute union of location parts of variable *SLOT and the same variable 1042254721Semaste from hash table DATA. Compute "sorted" union of the location chains 1043254721Semaste for common offsets, i.e. the locations of a variable part are sorted by 1044254721Semaste a priority where the priority is the sum of the positions in the 2 chains 1045254721Semaste (if a location is only in one list the position in the second list is 1046254721Semaste defined to be larger than the length of the chains). 1047254721Semaste When we are updating the location parts the newest location is in the 1048254721Semaste beginning of the chain, so when we do the described "sorted" union 1049254721Semaste we keep the newest locations in the beginning. */ 1050254721Semaste 1051254721Semastestatic int 1052254721Semastevariable_union (void **slot, void *data) 1053254721Semaste{ 1054254721Semaste variable src, dst, *dstp; 1055254721Semaste dataflow_set *set = (dataflow_set *) data; 1056254721Semaste int i, j, k; 1057254721Semaste 1058254721Semaste src = *(variable *) slot; 1059254721Semaste dstp = (variable *) htab_find_slot_with_hash (set->vars, src->decl, 1060254721Semaste VARIABLE_HASH_VAL (src->decl), 1061254721Semaste INSERT); 1062254721Semaste if (!*dstp) 1063254721Semaste { 1064254721Semaste src->refcount++; 1065254721Semaste 1066254721Semaste /* If CUR_LOC of some variable part is not the first element of 1067254721Semaste the location chain we are going to change it so we have to make 1068254721Semaste a copy of the variable. */ 1069254721Semaste for (k = 0; k < src->n_var_parts; k++) 1070254721Semaste { 1071254721Semaste gcc_assert (!src->var_part[k].loc_chain 1072254721Semaste == !src->var_part[k].cur_loc); 1073254721Semaste if (src->var_part[k].loc_chain) 1074254721Semaste { 1075254721Semaste gcc_assert (src->var_part[k].cur_loc); 1076254721Semaste if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc) 1077254721Semaste break; 1078254721Semaste } 1079254721Semaste } 1080254721Semaste if (k < src->n_var_parts) 1081254721Semaste unshare_variable (set, src); 1082254721Semaste else 1083254721Semaste *dstp = src; 1084254721Semaste 1085254721Semaste /* Continue traversing the hash table. */ 1086254721Semaste return 1; 1087254721Semaste } 1088254721Semaste else 1089254721Semaste dst = *dstp; 1090254721Semaste 1091254721Semaste gcc_assert (src->n_var_parts); 1092254721Semaste 1093254721Semaste /* Count the number of location parts, result is K. */ 1094254721Semaste for (i = 0, j = 0, k = 0; 1095254721Semaste i < src->n_var_parts && j < dst->n_var_parts; k++) 1096254721Semaste { 1097254721Semaste if (src->var_part[i].offset == dst->var_part[j].offset) 1098254721Semaste { 1099254721Semaste i++; 1100254721Semaste j++; 1101254721Semaste } 1102254721Semaste else if (src->var_part[i].offset < dst->var_part[j].offset) 1103254721Semaste i++; 1104254721Semaste else 1105254721Semaste j++; 1106254721Semaste } 1107254721Semaste k += src->n_var_parts - i; 1108254721Semaste k += dst->n_var_parts - j; 1109254721Semaste 1110254721Semaste /* We track only variables whose size is <= MAX_VAR_PARTS bytes 1111254721Semaste thus there are at most MAX_VAR_PARTS different offsets. */ 1112254721Semaste gcc_assert (k <= MAX_VAR_PARTS); 1113254721Semaste 1114254721Semaste if (dst->refcount > 1 && dst->n_var_parts != k) 1115254721Semaste dst = unshare_variable (set, dst); 1116254721Semaste 1117254721Semaste i = src->n_var_parts - 1; 1118254721Semaste j = dst->n_var_parts - 1; 1119254721Semaste dst->n_var_parts = k; 1120254721Semaste 1121254721Semaste for (k--; k >= 0; k--) 1122254721Semaste { 1123254721Semaste location_chain node, node2; 1124254721Semaste 1125254721Semaste if (i >= 0 && j >= 0 1126254721Semaste && src->var_part[i].offset == dst->var_part[j].offset) 1127254721Semaste { 1128254721Semaste /* Compute the "sorted" union of the chains, i.e. the locations which 1129254721Semaste are in both chains go first, they are sorted by the sum of 1130254721Semaste positions in the chains. */ 1131254721Semaste int dst_l, src_l; 1132254721Semaste int ii, jj, n; 1133254721Semaste struct variable_union_info *vui; 1134254721Semaste 1135254721Semaste /* If DST is shared compare the location chains. 1136254721Semaste If they are different we will modify the chain in DST with 1137254721Semaste high probability so make a copy of DST. */ 1138254721Semaste if (dst->refcount > 1) 1139254721Semaste { 1140254721Semaste for (node = src->var_part[i].loc_chain, 1141254721Semaste node2 = dst->var_part[j].loc_chain; node && node2; 1142254721Semaste node = node->next, node2 = node2->next) 1143254721Semaste { 1144254721Semaste if (!((REG_P (node2->loc) 1145254721Semaste && REG_P (node->loc) 1146254721Semaste && REGNO (node2->loc) == REGNO (node->loc)) 1147254721Semaste || rtx_equal_p (node2->loc, node->loc))) 1148254721Semaste break; 1149254721Semaste } 1150254721Semaste if (node || node2) 1151254721Semaste dst = unshare_variable (set, dst); 1152254721Semaste } 1153254721Semaste 1154254721Semaste src_l = 0; 1155254721Semaste for (node = src->var_part[i].loc_chain; node; node = node->next) 1156254721Semaste src_l++; 1157254721Semaste dst_l = 0; 1158254721Semaste for (node = dst->var_part[j].loc_chain; node; node = node->next) 1159254721Semaste dst_l++; 1160254721Semaste vui = XCNEWVEC (struct variable_union_info, src_l + dst_l); 1161254721Semaste 1162254721Semaste /* Fill in the locations from DST. */ 1163254721Semaste for (node = dst->var_part[j].loc_chain, jj = 0; node; 1164254721Semaste node = node->next, jj++) 1165254721Semaste { 1166254721Semaste vui[jj].lc = node; 1167254721Semaste vui[jj].pos_dst = jj; 1168254721Semaste 1169254721Semaste /* Value larger than a sum of 2 valid positions. */ 1170254721Semaste vui[jj].pos_src = src_l + dst_l; 1171254721Semaste } 1172254721Semaste 1173254721Semaste /* Fill in the locations from SRC. */ 1174254721Semaste n = dst_l; 1175254721Semaste for (node = src->var_part[i].loc_chain, ii = 0; node; 1176254721Semaste node = node->next, ii++) 1177254721Semaste { 1178254721Semaste /* Find location from NODE. */ 1179254721Semaste for (jj = 0; jj < dst_l; jj++) 1180254721Semaste { 1181254721Semaste if ((REG_P (vui[jj].lc->loc) 1182254721Semaste && REG_P (node->loc) 1183254721Semaste && REGNO (vui[jj].lc->loc) == REGNO (node->loc)) 1184254721Semaste || rtx_equal_p (vui[jj].lc->loc, node->loc)) 1185254721Semaste { 1186254721Semaste vui[jj].pos_src = ii; 1187254721Semaste break; 1188254721Semaste } 1189254721Semaste } 1190254721Semaste if (jj >= dst_l) /* The location has not been found. */ 1191254721Semaste { 1192254721Semaste location_chain new_node; 1193254721Semaste 1194254721Semaste /* Copy the location from SRC. */ 1195254721Semaste new_node = pool_alloc (loc_chain_pool); 1196254721Semaste new_node->loc = node->loc; 1197254721Semaste vui[n].lc = new_node; 1198254721Semaste vui[n].pos_src = ii; 1199254721Semaste vui[n].pos_dst = src_l + dst_l; 1200254721Semaste n++; 1201254721Semaste } 1202254721Semaste } 1203254721Semaste 1204254721Semaste for (ii = 0; ii < src_l + dst_l; ii++) 1205254721Semaste vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst; 1206254721Semaste 1207254721Semaste qsort (vui, n, sizeof (struct variable_union_info), 1208254721Semaste variable_union_info_cmp_pos); 1209254721Semaste 1210254721Semaste /* Reconnect the nodes in sorted order. */ 1211254721Semaste for (ii = 1; ii < n; ii++) 1212254721Semaste vui[ii - 1].lc->next = vui[ii].lc; 1213254721Semaste vui[n - 1].lc->next = NULL; 1214254721Semaste 1215254721Semaste dst->var_part[k].loc_chain = vui[0].lc; 1216254721Semaste dst->var_part[k].offset = dst->var_part[j].offset; 1217254721Semaste 1218254721Semaste free (vui); 1219254721Semaste i--; 1220254721Semaste j--; 1221254721Semaste } 1222254721Semaste else if ((i >= 0 && j >= 0 1223254721Semaste && src->var_part[i].offset < dst->var_part[j].offset) 1224254721Semaste || i < 0) 1225254721Semaste { 1226254721Semaste dst->var_part[k] = dst->var_part[j]; 1227254721Semaste j--; 1228254721Semaste } 1229254721Semaste else if ((i >= 0 && j >= 0 1230254721Semaste && src->var_part[i].offset > dst->var_part[j].offset) 1231254721Semaste || j < 0) 1232254721Semaste { 1233254721Semaste location_chain *nextp; 1234254721Semaste 1235254721Semaste /* Copy the chain from SRC. */ 1236254721Semaste nextp = &dst->var_part[k].loc_chain; 1237254721Semaste for (node = src->var_part[i].loc_chain; node; node = node->next) 1238254721Semaste { 1239254721Semaste location_chain new_lc; 1240254721Semaste 1241254721Semaste new_lc = pool_alloc (loc_chain_pool); 1242254721Semaste new_lc->next = NULL; 1243254721Semaste new_lc->loc = node->loc; 1244254721Semaste 1245254721Semaste *nextp = new_lc; 1246254721Semaste nextp = &new_lc->next; 1247254721Semaste } 1248254721Semaste 1249254721Semaste dst->var_part[k].offset = src->var_part[i].offset; 1250254721Semaste i--; 1251254721Semaste } 1252254721Semaste 1253254721Semaste /* We are at the basic block boundary when computing union 1254254721Semaste so set the CUR_LOC to be the first element of the chain. */ 1255254721Semaste if (dst->var_part[k].loc_chain) 1256254721Semaste dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc; 1257254721Semaste else 1258254721Semaste dst->var_part[k].cur_loc = NULL; 1259254721Semaste } 1260254721Semaste 1261254721Semaste /* Continue traversing the hash table. */ 1262254721Semaste return 1; 1263254721Semaste} 1264254721Semaste 1265254721Semaste/* Compute union of dataflow sets SRC and DST and store it to DST. */ 1266254721Semaste 1267254721Semastestatic void 1268254721Semastedataflow_set_union (dataflow_set *dst, dataflow_set *src) 1269254721Semaste{ 1270254721Semaste int i; 1271254721Semaste 1272254721Semaste for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1273254721Semaste attrs_list_union (&dst->regs[i], src->regs[i]); 1274254721Semaste 1275254721Semaste htab_traverse (src->vars, variable_union, dst); 1276254721Semaste} 1277254721Semaste 1278254721Semaste/* Flag whether two dataflow sets being compared contain different data. */ 1279254721Semastestatic bool 1280254721Semastedataflow_set_different_value; 1281254721Semaste 1282254721Semastestatic bool 1283254721Semastevariable_part_different_p (variable_part *vp1, variable_part *vp2) 1284254721Semaste{ 1285254721Semaste location_chain lc1, lc2; 1286254721Semaste 1287254721Semaste for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next) 1288254721Semaste { 1289254721Semaste for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next) 1290254721Semaste { 1291254721Semaste if (REG_P (lc1->loc) && REG_P (lc2->loc)) 1292254721Semaste { 1293254721Semaste if (REGNO (lc1->loc) == REGNO (lc2->loc)) 1294254721Semaste break; 1295254721Semaste } 1296254721Semaste if (rtx_equal_p (lc1->loc, lc2->loc)) 1297254721Semaste break; 1298254721Semaste } 1299254721Semaste if (!lc2) 1300254721Semaste return true; 1301254721Semaste } 1302254721Semaste return false; 1303254721Semaste} 1304254721Semaste 1305254721Semaste/* Return true if variables VAR1 and VAR2 are different. 1306254721Semaste If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each 1307254721Semaste variable part. */ 1308254721Semaste 1309254721Semastestatic bool 1310254721Semastevariable_different_p (variable var1, variable var2, 1311254721Semaste bool compare_current_location) 1312254721Semaste{ 1313254721Semaste int i; 1314254721Semaste 1315254721Semaste if (var1 == var2) 1316254721Semaste return false; 1317254721Semaste 1318254721Semaste if (var1->n_var_parts != var2->n_var_parts) 1319254721Semaste return true; 1320254721Semaste 1321254721Semaste for (i = 0; i < var1->n_var_parts; i++) 1322254721Semaste { 1323254721Semaste if (var1->var_part[i].offset != var2->var_part[i].offset) 1324254721Semaste return true; 1325254721Semaste if (compare_current_location) 1326254721Semaste { 1327254721Semaste if (!((REG_P (var1->var_part[i].cur_loc) 1328254721Semaste && REG_P (var2->var_part[i].cur_loc) 1329254721Semaste && (REGNO (var1->var_part[i].cur_loc) 1330254721Semaste == REGNO (var2->var_part[i].cur_loc))) 1331254721Semaste || rtx_equal_p (var1->var_part[i].cur_loc, 1332254721Semaste var2->var_part[i].cur_loc))) 1333254721Semaste return true; 1334254721Semaste } 1335254721Semaste if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i])) 1336254721Semaste return true; 1337 if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i])) 1338 return true; 1339 } 1340 return false; 1341} 1342 1343/* Compare variable *SLOT with the same variable in hash table DATA 1344 and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */ 1345 1346static int 1347dataflow_set_different_1 (void **slot, void *data) 1348{ 1349 htab_t htab = (htab_t) data; 1350 variable var1, var2; 1351 1352 var1 = *(variable *) slot; 1353 var2 = htab_find_with_hash (htab, var1->decl, 1354 VARIABLE_HASH_VAL (var1->decl)); 1355 if (!var2) 1356 { 1357 dataflow_set_different_value = true; 1358 1359 /* Stop traversing the hash table. */ 1360 return 0; 1361 } 1362 1363 if (variable_different_p (var1, var2, false)) 1364 { 1365 dataflow_set_different_value = true; 1366 1367 /* Stop traversing the hash table. */ 1368 return 0; 1369 } 1370 1371 /* Continue traversing the hash table. */ 1372 return 1; 1373} 1374 1375/* Compare variable *SLOT with the same variable in hash table DATA 1376 and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */ 1377 1378static int 1379dataflow_set_different_2 (void **slot, void *data) 1380{ 1381 htab_t htab = (htab_t) data; 1382 variable var1, var2; 1383 1384 var1 = *(variable *) slot; 1385 var2 = htab_find_with_hash (htab, var1->decl, 1386 VARIABLE_HASH_VAL (var1->decl)); 1387 if (!var2) 1388 { 1389 dataflow_set_different_value = true; 1390 1391 /* Stop traversing the hash table. */ 1392 return 0; 1393 } 1394 1395 /* If both variables are defined they have been already checked for 1396 equivalence. */ 1397 gcc_assert (!variable_different_p (var1, var2, false)); 1398 1399 /* Continue traversing the hash table. */ 1400 return 1; 1401} 1402 1403/* Return true if dataflow sets OLD_SET and NEW_SET differ. */ 1404 1405static bool 1406dataflow_set_different (dataflow_set *old_set, dataflow_set *new_set) 1407{ 1408 dataflow_set_different_value = false; 1409 1410 htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars); 1411 if (!dataflow_set_different_value) 1412 { 1413 /* We have compared the variables which are in both hash tables 1414 so now only check whether there are some variables in NEW_SET->VARS 1415 which are not in OLD_SET->VARS. */ 1416 htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars); 1417 } 1418 return dataflow_set_different_value; 1419} 1420 1421/* Free the contents of dataflow set SET. */ 1422 1423static void 1424dataflow_set_destroy (dataflow_set *set) 1425{ 1426 int i; 1427 1428 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1429 attrs_list_clear (&set->regs[i]); 1430 1431 htab_delete (set->vars); 1432 set->vars = NULL; 1433} 1434 1435/* Return true if RTL X contains a SYMBOL_REF. */ 1436 1437static bool 1438contains_symbol_ref (rtx x) 1439{ 1440 const char *fmt; 1441 RTX_CODE code; 1442 int i; 1443 1444 if (!x) 1445 return false; 1446 1447 code = GET_CODE (x); 1448 if (code == SYMBOL_REF) 1449 return true; 1450 1451 fmt = GET_RTX_FORMAT (code); 1452 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1453 { 1454 if (fmt[i] == 'e') 1455 { 1456 if (contains_symbol_ref (XEXP (x, i))) 1457 return true; 1458 } 1459 else if (fmt[i] == 'E') 1460 { 1461 int j; 1462 for (j = 0; j < XVECLEN (x, i); j++) 1463 if (contains_symbol_ref (XVECEXP (x, i, j))) 1464 return true; 1465 } 1466 } 1467 1468 return false; 1469} 1470 1471/* Shall EXPR be tracked? */ 1472 1473static bool 1474track_expr_p (tree expr) 1475{ 1476 rtx decl_rtl; 1477 tree realdecl; 1478 1479 /* If EXPR is not a parameter or a variable do not track it. */ 1480 if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL) 1481 return 0; 1482 1483 /* It also must have a name... */ 1484 if (!DECL_NAME (expr)) 1485 return 0; 1486 1487 /* ... and a RTL assigned to it. */ 1488 decl_rtl = DECL_RTL_IF_SET (expr); 1489 if (!decl_rtl) 1490 return 0; 1491 1492 /* If this expression is really a debug alias of some other declaration, we 1493 don't need to track this expression if the ultimate declaration is 1494 ignored. */ 1495 realdecl = expr; 1496 if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl)) 1497 { 1498 realdecl = DECL_DEBUG_EXPR (realdecl); 1499 /* ??? We don't yet know how to emit DW_OP_piece for variable 1500 that has been SRA'ed. */ 1501 if (!DECL_P (realdecl)) 1502 return 0; 1503 } 1504 1505 /* Do not track EXPR if REALDECL it should be ignored for debugging 1506 purposes. */ 1507 if (DECL_IGNORED_P (realdecl)) 1508 return 0; 1509 1510 /* Do not track global variables until we are able to emit correct location 1511 list for them. */ 1512 if (TREE_STATIC (realdecl)) 1513 return 0; 1514 1515 /* When the EXPR is a DECL for alias of some variable (see example) 1516 the TREE_STATIC flag is not used. Disable tracking all DECLs whose 1517 DECL_RTL contains SYMBOL_REF. 1518 1519 Example: 1520 extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv"))); 1521 char **_dl_argv; 1522 */ 1523 if (MEM_P (decl_rtl) 1524 && contains_symbol_ref (XEXP (decl_rtl, 0))) 1525 return 0; 1526 1527 /* If RTX is a memory it should not be very large (because it would be 1528 an array or struct). */ 1529 if (MEM_P (decl_rtl)) 1530 { 1531 /* Do not track structures and arrays. */ 1532 if (GET_MODE (decl_rtl) == BLKmode 1533 || AGGREGATE_TYPE_P (TREE_TYPE (realdecl))) 1534 return 0; 1535 if (MEM_SIZE (decl_rtl) 1536 && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS) 1537 return 0; 1538 } 1539 1540 return 1; 1541} 1542 1543/* Determine whether a given LOC refers to the same variable part as 1544 EXPR+OFFSET. */ 1545 1546static bool 1547same_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset) 1548{ 1549 tree expr2; 1550 HOST_WIDE_INT offset2; 1551 1552 if (! DECL_P (expr)) 1553 return false; 1554 1555 if (REG_P (loc)) 1556 { 1557 expr2 = REG_EXPR (loc); 1558 offset2 = REG_OFFSET (loc); 1559 } 1560 else if (MEM_P (loc)) 1561 { 1562 expr2 = MEM_EXPR (loc); 1563 offset2 = MEM_OFFSET (loc) ? INTVAL (MEM_OFFSET (loc)) : 0; 1564 } 1565 else 1566 return false; 1567 1568 if (! expr2 || ! DECL_P (expr2)) 1569 return false; 1570 1571 expr = var_debug_decl (expr); 1572 expr2 = var_debug_decl (expr2); 1573 1574 return (expr == expr2 && offset == offset2); 1575} 1576 1577 1578/* Count uses (register and memory references) LOC which will be tracked. 1579 INSN is instruction which the LOC is part of. */ 1580 1581static int 1582count_uses (rtx *loc, void *insn) 1583{ 1584 basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1585 1586 if (REG_P (*loc)) 1587 { 1588 gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER); 1589 VTI (bb)->n_mos++; 1590 } 1591 else if (MEM_P (*loc) 1592 && MEM_EXPR (*loc) 1593 && track_expr_p (MEM_EXPR (*loc))) 1594 { 1595 VTI (bb)->n_mos++; 1596 } 1597 1598 return 0; 1599} 1600 1601/* Helper function for finding all uses of REG/MEM in X in insn INSN. */ 1602 1603static void 1604count_uses_1 (rtx *x, void *insn) 1605{ 1606 for_each_rtx (x, count_uses, insn); 1607} 1608 1609/* Count stores (register and memory references) LOC which will be tracked. 1610 INSN is instruction which the LOC is part of. */ 1611 1612static void 1613count_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn) 1614{ 1615 count_uses (&loc, insn); 1616} 1617 1618/* Add uses (register and memory references) LOC which will be tracked 1619 to VTI (bb)->mos. INSN is instruction which the LOC is part of. */ 1620 1621static int 1622add_uses (rtx *loc, void *insn) 1623{ 1624 if (REG_P (*loc)) 1625 { 1626 basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1627 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1628 1629 mo->type = ((REG_EXPR (*loc) && track_expr_p (REG_EXPR (*loc))) 1630 ? MO_USE : MO_USE_NO_VAR); 1631 mo->u.loc = *loc; 1632 mo->insn = (rtx) insn; 1633 } 1634 else if (MEM_P (*loc) 1635 && MEM_EXPR (*loc) 1636 && track_expr_p (MEM_EXPR (*loc))) 1637 { 1638 basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1639 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1640 1641 mo->type = MO_USE; 1642 mo->u.loc = *loc; 1643 mo->insn = (rtx) insn; 1644 } 1645 1646 return 0; 1647} 1648 1649/* Helper function for finding all uses of REG/MEM in X in insn INSN. */ 1650 1651static void 1652add_uses_1 (rtx *x, void *insn) 1653{ 1654 for_each_rtx (x, add_uses, insn); 1655} 1656 1657/* Add stores (register and memory references) LOC which will be tracked 1658 to VTI (bb)->mos. EXPR is the RTL expression containing the store. 1659 INSN is instruction which the LOC is part of. */ 1660 1661static void 1662add_stores (rtx loc, rtx expr, void *insn) 1663{ 1664 if (REG_P (loc)) 1665 { 1666 basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1667 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1668 1669 if (GET_CODE (expr) == CLOBBER 1670 || ! REG_EXPR (loc) 1671 || ! track_expr_p (REG_EXPR (loc))) 1672 mo->type = MO_CLOBBER; 1673 else if (GET_CODE (expr) == SET 1674 && SET_DEST (expr) == loc 1675 && same_variable_part_p (SET_SRC (expr), 1676 REG_EXPR (loc), 1677 REG_OFFSET (loc))) 1678 mo->type = MO_COPY; 1679 else 1680 mo->type = MO_SET; 1681 mo->u.loc = loc; 1682 mo->insn = NEXT_INSN ((rtx) insn); 1683 } 1684 else if (MEM_P (loc) 1685 && MEM_EXPR (loc) 1686 && track_expr_p (MEM_EXPR (loc))) 1687 { 1688 basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1689 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1690 1691 if (GET_CODE (expr) == CLOBBER) 1692 mo->type = MO_CLOBBER; 1693 else if (GET_CODE (expr) == SET 1694 && SET_DEST (expr) == loc 1695 && same_variable_part_p (SET_SRC (expr), 1696 MEM_EXPR (loc), 1697 MEM_OFFSET (loc) 1698 ? INTVAL (MEM_OFFSET (loc)) : 0)) 1699 mo->type = MO_COPY; 1700 else 1701 mo->type = MO_SET; 1702 mo->u.loc = loc; 1703 mo->insn = NEXT_INSN ((rtx) insn); 1704 } 1705} 1706 1707/* Compute the changes of variable locations in the basic block BB. */ 1708 1709static bool 1710compute_bb_dataflow (basic_block bb) 1711{ 1712 int i, n, r; 1713 bool changed; 1714 dataflow_set old_out; 1715 dataflow_set *in = &VTI (bb)->in; 1716 dataflow_set *out = &VTI (bb)->out; 1717 1718 dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3); 1719 dataflow_set_copy (&old_out, out); 1720 dataflow_set_copy (out, in); 1721 1722 n = VTI (bb)->n_mos; 1723 for (i = 0; i < n; i++) 1724 { 1725 switch (VTI (bb)->mos[i].type) 1726 { 1727 case MO_CALL: 1728 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) 1729 if (TEST_HARD_REG_BIT (call_used_reg_set, r)) 1730 var_regno_delete (out, r); 1731 break; 1732 1733 case MO_USE: 1734 { 1735 rtx loc = VTI (bb)->mos[i].u.loc; 1736 1737 if (GET_CODE (loc) == REG) 1738 var_reg_set (out, loc); 1739 else if (GET_CODE (loc) == MEM) 1740 var_mem_set (out, loc); 1741 } 1742 break; 1743 1744 case MO_SET: 1745 { 1746 rtx loc = VTI (bb)->mos[i].u.loc; 1747 1748 if (REG_P (loc)) 1749 var_reg_delete_and_set (out, loc, true); 1750 else if (MEM_P (loc)) 1751 var_mem_delete_and_set (out, loc, true); 1752 } 1753 break; 1754 1755 case MO_COPY: 1756 { 1757 rtx loc = VTI (bb)->mos[i].u.loc; 1758 1759 if (REG_P (loc)) 1760 var_reg_delete_and_set (out, loc, false); 1761 else if (MEM_P (loc)) 1762 var_mem_delete_and_set (out, loc, false); 1763 } 1764 break; 1765 1766 case MO_USE_NO_VAR: 1767 { 1768 rtx loc = VTI (bb)->mos[i].u.loc; 1769 1770 if (REG_P (loc)) 1771 var_reg_delete (out, loc, false); 1772 else if (MEM_P (loc)) 1773 var_mem_delete (out, loc, false); 1774 } 1775 break; 1776 1777 case MO_CLOBBER: 1778 { 1779 rtx loc = VTI (bb)->mos[i].u.loc; 1780 1781 if (REG_P (loc)) 1782 var_reg_delete (out, loc, true); 1783 else if (MEM_P (loc)) 1784 var_mem_delete (out, loc, true); 1785 } 1786 break; 1787 1788 case MO_ADJUST: 1789 out->stack_adjust += VTI (bb)->mos[i].u.adjust; 1790 break; 1791 } 1792 } 1793 1794 changed = dataflow_set_different (&old_out, out); 1795 dataflow_set_destroy (&old_out); 1796 return changed; 1797} 1798 1799/* Find the locations of variables in the whole function. */ 1800 1801static void 1802vt_find_locations (void) 1803{ 1804 fibheap_t worklist, pending, fibheap_swap; 1805 sbitmap visited, in_worklist, in_pending, sbitmap_swap; 1806 basic_block bb; 1807 edge e; 1808 int *bb_order; 1809 int *rc_order; 1810 int i; 1811 1812 /* Compute reverse completion order of depth first search of the CFG 1813 so that the data-flow runs faster. */ 1814 rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); 1815 bb_order = XNEWVEC (int, last_basic_block); 1816 pre_and_rev_post_order_compute (NULL, rc_order, false); 1817 for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 1818 bb_order[rc_order[i]] = i; 1819 free (rc_order); 1820 1821 worklist = fibheap_new (); 1822 pending = fibheap_new (); 1823 visited = sbitmap_alloc (last_basic_block); 1824 in_worklist = sbitmap_alloc (last_basic_block); 1825 in_pending = sbitmap_alloc (last_basic_block); 1826 sbitmap_zero (in_worklist); 1827 1828 FOR_EACH_BB (bb) 1829 fibheap_insert (pending, bb_order[bb->index], bb); 1830 sbitmap_ones (in_pending); 1831 1832 while (!fibheap_empty (pending)) 1833 { 1834 fibheap_swap = pending; 1835 pending = worklist; 1836 worklist = fibheap_swap; 1837 sbitmap_swap = in_pending; 1838 in_pending = in_worklist; 1839 in_worklist = sbitmap_swap; 1840 1841 sbitmap_zero (visited); 1842 1843 while (!fibheap_empty (worklist)) 1844 { 1845 bb = fibheap_extract_min (worklist); 1846 RESET_BIT (in_worklist, bb->index); 1847 if (!TEST_BIT (visited, bb->index)) 1848 { 1849 bool changed; 1850 edge_iterator ei; 1851 1852 SET_BIT (visited, bb->index); 1853 1854 /* Calculate the IN set as union of predecessor OUT sets. */ 1855 dataflow_set_clear (&VTI (bb)->in); 1856 FOR_EACH_EDGE (e, ei, bb->preds) 1857 { 1858 dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out); 1859 } 1860 1861 changed = compute_bb_dataflow (bb); 1862 if (changed) 1863 { 1864 FOR_EACH_EDGE (e, ei, bb->succs) 1865 { 1866 if (e->dest == EXIT_BLOCK_PTR) 1867 continue; 1868 1869 if (e->dest == bb) 1870 continue; 1871 1872 if (TEST_BIT (visited, e->dest->index)) 1873 { 1874 if (!TEST_BIT (in_pending, e->dest->index)) 1875 { 1876 /* Send E->DEST to next round. */ 1877 SET_BIT (in_pending, e->dest->index); 1878 fibheap_insert (pending, 1879 bb_order[e->dest->index], 1880 e->dest); 1881 } 1882 } 1883 else if (!TEST_BIT (in_worklist, e->dest->index)) 1884 { 1885 /* Add E->DEST to current round. */ 1886 SET_BIT (in_worklist, e->dest->index); 1887 fibheap_insert (worklist, bb_order[e->dest->index], 1888 e->dest); 1889 } 1890 } 1891 } 1892 } 1893 } 1894 } 1895 1896 free (bb_order); 1897 fibheap_delete (worklist); 1898 fibheap_delete (pending); 1899 sbitmap_free (visited); 1900 sbitmap_free (in_worklist); 1901 sbitmap_free (in_pending); 1902} 1903 1904/* Print the content of the LIST to dump file. */ 1905 1906static void 1907dump_attrs_list (attrs list) 1908{ 1909 for (; list; list = list->next) 1910 { 1911 print_mem_expr (dump_file, list->decl); 1912 fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset); 1913 } 1914 fprintf (dump_file, "\n"); 1915} 1916 1917/* Print the information about variable *SLOT to dump file. */ 1918 1919static int 1920dump_variable (void **slot, void *data ATTRIBUTE_UNUSED) 1921{ 1922 variable var = *(variable *) slot; 1923 int i; 1924 location_chain node; 1925 1926 fprintf (dump_file, " name: %s\n", 1927 IDENTIFIER_POINTER (DECL_NAME (var->decl))); 1928 for (i = 0; i < var->n_var_parts; i++) 1929 { 1930 fprintf (dump_file, " offset %ld\n", 1931 (long) var->var_part[i].offset); 1932 for (node = var->var_part[i].loc_chain; node; node = node->next) 1933 { 1934 fprintf (dump_file, " "); 1935 print_rtl_single (dump_file, node->loc); 1936 } 1937 } 1938 1939 /* Continue traversing the hash table. */ 1940 return 1; 1941} 1942 1943/* Print the information about variables from hash table VARS to dump file. */ 1944 1945static void 1946dump_vars (htab_t vars) 1947{ 1948 if (htab_elements (vars) > 0) 1949 { 1950 fprintf (dump_file, "Variables:\n"); 1951 htab_traverse (vars, dump_variable, NULL); 1952 } 1953} 1954 1955/* Print the dataflow set SET to dump file. */ 1956 1957static void 1958dump_dataflow_set (dataflow_set *set) 1959{ 1960 int i; 1961 1962 fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n", 1963 set->stack_adjust); 1964 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1965 { 1966 if (set->regs[i]) 1967 { 1968 fprintf (dump_file, "Reg %d:", i); 1969 dump_attrs_list (set->regs[i]); 1970 } 1971 } 1972 dump_vars (set->vars); 1973 fprintf (dump_file, "\n"); 1974} 1975 1976/* Print the IN and OUT sets for each basic block to dump file. */ 1977 1978static void 1979dump_dataflow_sets (void) 1980{ 1981 basic_block bb; 1982 1983 FOR_EACH_BB (bb) 1984 { 1985 fprintf (dump_file, "\nBasic block %d:\n", bb->index); 1986 fprintf (dump_file, "IN:\n"); 1987 dump_dataflow_set (&VTI (bb)->in); 1988 fprintf (dump_file, "OUT:\n"); 1989 dump_dataflow_set (&VTI (bb)->out); 1990 } 1991} 1992 1993/* Add variable VAR to the hash table of changed variables and 1994 if it has no locations delete it from hash table HTAB. */ 1995 1996static void 1997variable_was_changed (variable var, htab_t htab) 1998{ 1999 hashval_t hash = VARIABLE_HASH_VAL (var->decl); 2000 2001 if (emit_notes) 2002 { 2003 variable *slot; 2004 2005 slot = (variable *) htab_find_slot_with_hash (changed_variables, 2006 var->decl, hash, INSERT); 2007 2008 if (htab && var->n_var_parts == 0) 2009 { 2010 variable empty_var; 2011 void **old; 2012 2013 empty_var = pool_alloc (var_pool); 2014 empty_var->decl = var->decl; 2015 empty_var->refcount = 1; 2016 empty_var->n_var_parts = 0; 2017 *slot = empty_var; 2018 2019 old = htab_find_slot_with_hash (htab, var->decl, hash, 2020 NO_INSERT); 2021 if (old) 2022 htab_clear_slot (htab, old); 2023 } 2024 else 2025 { 2026 *slot = var; 2027 } 2028 } 2029 else 2030 { 2031 gcc_assert (htab); 2032 if (var->n_var_parts == 0) 2033 { 2034 void **slot = htab_find_slot_with_hash (htab, var->decl, hash, 2035 NO_INSERT); 2036 if (slot) 2037 htab_clear_slot (htab, slot); 2038 } 2039 } 2040} 2041 2042/* Look for the index in VAR->var_part corresponding to OFFSET. 2043 Return -1 if not found. If INSERTION_POINT is non-NULL, the 2044 referenced int will be set to the index that the part has or should 2045 have, if it should be inserted. */ 2046 2047static inline int 2048find_variable_location_part (variable var, HOST_WIDE_INT offset, 2049 int *insertion_point) 2050{ 2051 int pos, low, high; 2052 2053 /* Find the location part. */ 2054 low = 0; 2055 high = var->n_var_parts; 2056 while (low != high) 2057 { 2058 pos = (low + high) / 2; 2059 if (var->var_part[pos].offset < offset) 2060 low = pos + 1; 2061 else 2062 high = pos; 2063 } 2064 pos = low; 2065 2066 if (insertion_point) 2067 *insertion_point = pos; 2068 2069 if (pos < var->n_var_parts && var->var_part[pos].offset == offset) 2070 return pos; 2071 2072 return -1; 2073} 2074 2075/* Set the part of variable's location in the dataflow set SET. The variable 2076 part is specified by variable's declaration DECL and offset OFFSET and the 2077 part's location by LOC. */ 2078 2079static void 2080set_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset) 2081{ 2082 int pos; 2083 location_chain node, next; 2084 location_chain *nextp; 2085 variable var; 2086 void **slot; 2087 2088 slot = htab_find_slot_with_hash (set->vars, decl, 2089 VARIABLE_HASH_VAL (decl), INSERT); 2090 if (!*slot) 2091 { 2092 /* Create new variable information. */ 2093 var = pool_alloc (var_pool); 2094 var->decl = decl; 2095 var->refcount = 1; 2096 var->n_var_parts = 1; 2097 var->var_part[0].offset = offset; 2098 var->var_part[0].loc_chain = NULL; 2099 var->var_part[0].cur_loc = NULL; 2100 *slot = var; 2101 pos = 0; 2102 } 2103 else 2104 { 2105 int inspos = 0; 2106 2107 var = (variable) *slot; 2108 2109 pos = find_variable_location_part (var, offset, &inspos); 2110 2111 if (pos >= 0) 2112 { 2113 node = var->var_part[pos].loc_chain; 2114 2115 if (node 2116 && ((REG_P (node->loc) && REG_P (loc) 2117 && REGNO (node->loc) == REGNO (loc)) 2118 || rtx_equal_p (node->loc, loc))) 2119 { 2120 /* LOC is in the beginning of the chain so we have nothing 2121 to do. */ 2122 return; 2123 } 2124 else 2125 { 2126 /* We have to make a copy of a shared variable. */ 2127 if (var->refcount > 1) 2128 var = unshare_variable (set, var); 2129 } 2130 } 2131 else 2132 { 2133 /* We have not found the location part, new one will be created. */ 2134 2135 /* We have to make a copy of the shared variable. */ 2136 if (var->refcount > 1) 2137 var = unshare_variable (set, var); 2138 2139 /* We track only variables whose size is <= MAX_VAR_PARTS bytes 2140 thus there are at most MAX_VAR_PARTS different offsets. */ 2141 gcc_assert (var->n_var_parts < MAX_VAR_PARTS); 2142 2143 /* We have to move the elements of array starting at index 2144 inspos to the next position. */ 2145 for (pos = var->n_var_parts; pos > inspos; pos--) 2146 var->var_part[pos] = var->var_part[pos - 1]; 2147 2148 var->n_var_parts++; 2149 var->var_part[pos].offset = offset; 2150 var->var_part[pos].loc_chain = NULL; 2151 var->var_part[pos].cur_loc = NULL; 2152 } 2153 } 2154 2155 /* Delete the location from the list. */ 2156 nextp = &var->var_part[pos].loc_chain; 2157 for (node = var->var_part[pos].loc_chain; node; node = next) 2158 { 2159 next = node->next; 2160 if ((REG_P (node->loc) && REG_P (loc) 2161 && REGNO (node->loc) == REGNO (loc)) 2162 || rtx_equal_p (node->loc, loc)) 2163 { 2164 pool_free (loc_chain_pool, node); 2165 *nextp = next; 2166 break; 2167 } 2168 else 2169 nextp = &node->next; 2170 } 2171 2172 /* Add the location to the beginning. */ 2173 node = pool_alloc (loc_chain_pool); 2174 node->loc = loc; 2175 node->next = var->var_part[pos].loc_chain; 2176 var->var_part[pos].loc_chain = node; 2177 2178 /* If no location was emitted do so. */ 2179 if (var->var_part[pos].cur_loc == NULL) 2180 { 2181 var->var_part[pos].cur_loc = loc; 2182 variable_was_changed (var, set->vars); 2183 } 2184} 2185 2186/* Remove all recorded register locations for the given variable part 2187 from dataflow set SET, except for those that are identical to loc. 2188 The variable part is specified by variable's declaration DECL and 2189 offset OFFSET. */ 2190 2191static void 2192clobber_variable_part (dataflow_set *set, rtx loc, tree decl, 2193 HOST_WIDE_INT offset) 2194{ 2195 void **slot; 2196 2197 if (! decl || ! DECL_P (decl)) 2198 return; 2199 2200 slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl), 2201 NO_INSERT); 2202 if (slot) 2203 { 2204 variable var = (variable) *slot; 2205 int pos = find_variable_location_part (var, offset, NULL); 2206 2207 if (pos >= 0) 2208 { 2209 location_chain node, next; 2210 2211 /* Remove the register locations from the dataflow set. */ 2212 next = var->var_part[pos].loc_chain; 2213 for (node = next; node; node = next) 2214 { 2215 next = node->next; 2216 if (node->loc != loc) 2217 { 2218 if (REG_P (node->loc)) 2219 { 2220 attrs anode, anext; 2221 attrs *anextp; 2222 2223 /* Remove the variable part from the register's 2224 list, but preserve any other variable parts 2225 that might be regarded as live in that same 2226 register. */ 2227 anextp = &set->regs[REGNO (node->loc)]; 2228 for (anode = *anextp; anode; anode = anext) 2229 { 2230 anext = anode->next; 2231 if (anode->decl == decl 2232 && anode->offset == offset) 2233 { 2234 pool_free (attrs_pool, anode); 2235 *anextp = anext; 2236 } 2237 } 2238 } 2239 2240 delete_variable_part (set, node->loc, decl, offset); 2241 } 2242 } 2243 } 2244 } 2245} 2246 2247/* Delete the part of variable's location from dataflow set SET. The variable 2248 part is specified by variable's declaration DECL and offset OFFSET and the 2249 part's location by LOC. */ 2250 2251static void 2252delete_variable_part (dataflow_set *set, rtx loc, tree decl, 2253 HOST_WIDE_INT offset) 2254{ 2255 void **slot; 2256 2257 slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl), 2258 NO_INSERT); 2259 if (slot) 2260 { 2261 variable var = (variable) *slot; 2262 int pos = find_variable_location_part (var, offset, NULL); 2263 2264 if (pos >= 0) 2265 { 2266 location_chain node, next; 2267 location_chain *nextp; 2268 bool changed; 2269 2270 if (var->refcount > 1) 2271 { 2272 /* If the variable contains the location part we have to 2273 make a copy of the variable. */ 2274 for (node = var->var_part[pos].loc_chain; node; 2275 node = node->next) 2276 { 2277 if ((REG_P (node->loc) && REG_P (loc) 2278 && REGNO (node->loc) == REGNO (loc)) 2279 || rtx_equal_p (node->loc, loc)) 2280 { 2281 var = unshare_variable (set, var); 2282 break; 2283 } 2284 } 2285 } 2286 2287 /* Delete the location part. */ 2288 nextp = &var->var_part[pos].loc_chain; 2289 for (node = *nextp; node; node = next) 2290 { 2291 next = node->next; 2292 if ((REG_P (node->loc) && REG_P (loc) 2293 && REGNO (node->loc) == REGNO (loc)) 2294 || rtx_equal_p (node->loc, loc)) 2295 { 2296 pool_free (loc_chain_pool, node); 2297 *nextp = next; 2298 break; 2299 } 2300 else 2301 nextp = &node->next; 2302 } 2303 2304 /* If we have deleted the location which was last emitted 2305 we have to emit new location so add the variable to set 2306 of changed variables. */ 2307 if (var->var_part[pos].cur_loc 2308 && ((REG_P (loc) 2309 && REG_P (var->var_part[pos].cur_loc) 2310 && REGNO (loc) == REGNO (var->var_part[pos].cur_loc)) 2311 || rtx_equal_p (loc, var->var_part[pos].cur_loc))) 2312 { 2313 changed = true; 2314 if (var->var_part[pos].loc_chain) 2315 var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc; 2316 } 2317 else 2318 changed = false; 2319 2320 if (var->var_part[pos].loc_chain == NULL) 2321 { 2322 var->n_var_parts--; 2323 while (pos < var->n_var_parts) 2324 { 2325 var->var_part[pos] = var->var_part[pos + 1]; 2326 pos++; 2327 } 2328 } 2329 if (changed) 2330 variable_was_changed (var, set->vars); 2331 } 2332 } 2333} 2334 2335/* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP. DATA contains 2336 additional parameters: WHERE specifies whether the note shall be emitted 2337 before of after instruction INSN. */ 2338 2339static int 2340emit_note_insn_var_location (void **varp, void *data) 2341{ 2342 variable var = *(variable *) varp; 2343 rtx insn = ((emit_note_data *)data)->insn; 2344 enum emit_note_where where = ((emit_note_data *)data)->where; 2345 rtx note; 2346 int i, j, n_var_parts; 2347 bool complete; 2348 HOST_WIDE_INT last_limit; 2349 tree type_size_unit; 2350 HOST_WIDE_INT offsets[MAX_VAR_PARTS]; 2351 rtx loc[MAX_VAR_PARTS]; 2352 2353 gcc_assert (var->decl); 2354 2355 complete = true; 2356 last_limit = 0; 2357 n_var_parts = 0; 2358 for (i = 0; i < var->n_var_parts; i++) 2359 { 2360 enum machine_mode mode, wider_mode; 2361 2362 if (last_limit < var->var_part[i].offset) 2363 { 2364 complete = false; 2365 break; 2366 } 2367 else if (last_limit > var->var_part[i].offset) 2368 continue; 2369 offsets[n_var_parts] = var->var_part[i].offset; 2370 loc[n_var_parts] = var->var_part[i].loc_chain->loc; 2371 mode = GET_MODE (loc[n_var_parts]); 2372 last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode); 2373 2374 /* Attempt to merge adjacent registers or memory. */ 2375 wider_mode = GET_MODE_WIDER_MODE (mode); 2376 for (j = i + 1; j < var->n_var_parts; j++) 2377 if (last_limit <= var->var_part[j].offset) 2378 break; 2379 if (j < var->n_var_parts 2380 && wider_mode != VOIDmode 2381 && GET_CODE (loc[n_var_parts]) 2382 == GET_CODE (var->var_part[j].loc_chain->loc) 2383 && mode == GET_MODE (var->var_part[j].loc_chain->loc) 2384 && last_limit == var->var_part[j].offset) 2385 { 2386 rtx new_loc = NULL; 2387 rtx loc2 = var->var_part[j].loc_chain->loc; 2388 2389 if (REG_P (loc[n_var_parts]) 2390 && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2 2391 == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode] 2392 && REGNO (loc[n_var_parts]) 2393 + hard_regno_nregs[REGNO (loc[n_var_parts])][mode] 2394 == REGNO (loc2)) 2395 { 2396 if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN) 2397 new_loc = simplify_subreg (wider_mode, loc[n_var_parts], 2398 mode, 0); 2399 else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN) 2400 new_loc = simplify_subreg (wider_mode, loc2, mode, 0); 2401 if (new_loc) 2402 { 2403 if (!REG_P (new_loc) 2404 || REGNO (new_loc) != REGNO (loc[n_var_parts])) 2405 new_loc = NULL; 2406 else 2407 REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]); 2408 } 2409 } 2410 else if (MEM_P (loc[n_var_parts]) 2411 && GET_CODE (XEXP (loc2, 0)) == PLUS 2412 && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG 2413 && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT) 2414 { 2415 if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG 2416 && rtx_equal_p (XEXP (loc[n_var_parts], 0), 2417 XEXP (XEXP (loc2, 0), 0)) 2418 && INTVAL (XEXP (XEXP (loc2, 0), 1)) 2419 == GET_MODE_SIZE (mode)) 2420 || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS 2421 && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1)) 2422 == CONST_INT 2423 && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0), 2424 XEXP (XEXP (loc2, 0), 0)) 2425 && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1)) 2426 + GET_MODE_SIZE (mode) 2427 == INTVAL (XEXP (XEXP (loc2, 0), 1)))) 2428 new_loc = adjust_address_nv (loc[n_var_parts], 2429 wider_mode, 0); 2430 } 2431 2432 if (new_loc) 2433 { 2434 loc[n_var_parts] = new_loc; 2435 mode = wider_mode; 2436 last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode); 2437 i = j; 2438 } 2439 } 2440 ++n_var_parts; 2441 } 2442 type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl)); 2443 if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit)) 2444 complete = false; 2445 2446 if (where == EMIT_NOTE_AFTER_INSN) 2447 note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn); 2448 else 2449 note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn); 2450 2451 if (!complete) 2452 { 2453 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2454 NULL_RTX); 2455 } 2456 else if (n_var_parts == 1) 2457 { 2458 rtx expr_list 2459 = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0])); 2460 2461 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2462 expr_list); 2463 } 2464 else if (n_var_parts) 2465 { 2466 rtx parallel; 2467 2468 for (i = 0; i < n_var_parts; i++) 2469 loc[i] 2470 = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i])); 2471 2472 parallel = gen_rtx_PARALLEL (VOIDmode, 2473 gen_rtvec_v (n_var_parts, loc)); 2474 NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2475 parallel); 2476 } 2477 2478 htab_clear_slot (changed_variables, varp); 2479 2480 /* When there are no location parts the variable has been already 2481 removed from hash table and a new empty variable was created. 2482 Free the empty variable. */ 2483 if (var->n_var_parts == 0) 2484 { 2485 pool_free (var_pool, var); 2486 } 2487 2488 /* Continue traversing the hash table. */ 2489 return 1; 2490} 2491 2492/* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain 2493 CHANGED_VARIABLES and delete this chain. WHERE specifies whether the notes 2494 shall be emitted before of after instruction INSN. */ 2495 2496static void 2497emit_notes_for_changes (rtx insn, enum emit_note_where where) 2498{ 2499 emit_note_data data; 2500 2501 data.insn = insn; 2502 data.where = where; 2503 htab_traverse (changed_variables, emit_note_insn_var_location, &data); 2504} 2505 2506/* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the 2507 same variable in hash table DATA or is not there at all. */ 2508 2509static int 2510emit_notes_for_differences_1 (void **slot, void *data) 2511{ 2512 htab_t new_vars = (htab_t) data; 2513 variable old_var, new_var; 2514 2515 old_var = *(variable *) slot; 2516 new_var = htab_find_with_hash (new_vars, old_var->decl, 2517 VARIABLE_HASH_VAL (old_var->decl)); 2518 2519 if (!new_var) 2520 { 2521 /* Variable has disappeared. */ 2522 variable empty_var; 2523 2524 empty_var = pool_alloc (var_pool); 2525 empty_var->decl = old_var->decl; 2526 empty_var->refcount = 1; 2527 empty_var->n_var_parts = 0; 2528 variable_was_changed (empty_var, NULL); 2529 } 2530 else if (variable_different_p (old_var, new_var, true)) 2531 { 2532 variable_was_changed (new_var, NULL); 2533 } 2534 2535 /* Continue traversing the hash table. */ 2536 return 1; 2537} 2538 2539/* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash 2540 table DATA. */ 2541 2542static int 2543emit_notes_for_differences_2 (void **slot, void *data) 2544{ 2545 htab_t old_vars = (htab_t) data; 2546 variable old_var, new_var; 2547 2548 new_var = *(variable *) slot; 2549 old_var = htab_find_with_hash (old_vars, new_var->decl, 2550 VARIABLE_HASH_VAL (new_var->decl)); 2551 if (!old_var) 2552 { 2553 /* Variable has appeared. */ 2554 variable_was_changed (new_var, NULL); 2555 } 2556 2557 /* Continue traversing the hash table. */ 2558 return 1; 2559} 2560 2561/* Emit notes before INSN for differences between dataflow sets OLD_SET and 2562 NEW_SET. */ 2563 2564static void 2565emit_notes_for_differences (rtx insn, dataflow_set *old_set, 2566 dataflow_set *new_set) 2567{ 2568 htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars); 2569 htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars); 2570 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2571} 2572 2573/* Emit the notes for changes of location parts in the basic block BB. */ 2574 2575static void 2576emit_notes_in_bb (basic_block bb) 2577{ 2578 int i; 2579 dataflow_set set; 2580 2581 dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3); 2582 dataflow_set_copy (&set, &VTI (bb)->in); 2583 2584 for (i = 0; i < VTI (bb)->n_mos; i++) 2585 { 2586 rtx insn = VTI (bb)->mos[i].insn; 2587 2588 switch (VTI (bb)->mos[i].type) 2589 { 2590 case MO_CALL: 2591 { 2592 int r; 2593 2594 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) 2595 if (TEST_HARD_REG_BIT (call_used_reg_set, r)) 2596 { 2597 var_regno_delete (&set, r); 2598 } 2599 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2600 } 2601 break; 2602 2603 case MO_USE: 2604 { 2605 rtx loc = VTI (bb)->mos[i].u.loc; 2606 2607 if (GET_CODE (loc) == REG) 2608 var_reg_set (&set, loc); 2609 else 2610 var_mem_set (&set, loc); 2611 2612 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2613 } 2614 break; 2615 2616 case MO_SET: 2617 { 2618 rtx loc = VTI (bb)->mos[i].u.loc; 2619 2620 if (REG_P (loc)) 2621 var_reg_delete_and_set (&set, loc, true); 2622 else 2623 var_mem_delete_and_set (&set, loc, true); 2624 2625 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2626 } 2627 break; 2628 2629 case MO_COPY: 2630 { 2631 rtx loc = VTI (bb)->mos[i].u.loc; 2632 2633 if (REG_P (loc)) 2634 var_reg_delete_and_set (&set, loc, false); 2635 else 2636 var_mem_delete_and_set (&set, loc, false); 2637 2638 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2639 } 2640 break; 2641 2642 case MO_USE_NO_VAR: 2643 { 2644 rtx loc = VTI (bb)->mos[i].u.loc; 2645 2646 if (REG_P (loc)) 2647 var_reg_delete (&set, loc, false); 2648 else 2649 var_mem_delete (&set, loc, false); 2650 2651 emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2652 } 2653 break; 2654 2655 case MO_CLOBBER: 2656 { 2657 rtx loc = VTI (bb)->mos[i].u.loc; 2658 2659 if (REG_P (loc)) 2660 var_reg_delete (&set, loc, true); 2661 else 2662 var_mem_delete (&set, loc, true); 2663 2664 emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2665 } 2666 break; 2667 2668 case MO_ADJUST: 2669 set.stack_adjust += VTI (bb)->mos[i].u.adjust; 2670 break; 2671 } 2672 } 2673 dataflow_set_destroy (&set); 2674} 2675 2676/* Emit notes for the whole function. */ 2677 2678static void 2679vt_emit_notes (void) 2680{ 2681 basic_block bb; 2682 dataflow_set *last_out; 2683 dataflow_set empty; 2684 2685 gcc_assert (!htab_elements (changed_variables)); 2686 2687 /* Enable emitting notes by functions (mainly by set_variable_part and 2688 delete_variable_part). */ 2689 emit_notes = true; 2690 2691 dataflow_set_init (&empty, 7); 2692 last_out = ∅ 2693 2694 FOR_EACH_BB (bb) 2695 { 2696 /* Emit the notes for changes of variable locations between two 2697 subsequent basic blocks. */ 2698 emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in); 2699 2700 /* Emit the notes for the changes in the basic block itself. */ 2701 emit_notes_in_bb (bb); 2702 2703 last_out = &VTI (bb)->out; 2704 } 2705 dataflow_set_destroy (&empty); 2706 emit_notes = false; 2707} 2708 2709/* If there is a declaration and offset associated with register/memory RTL 2710 assign declaration to *DECLP and offset to *OFFSETP, and return true. */ 2711 2712static bool 2713vt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp) 2714{ 2715 if (REG_P (rtl)) 2716 { 2717 if (REG_ATTRS (rtl)) 2718 { 2719 *declp = REG_EXPR (rtl); 2720 *offsetp = REG_OFFSET (rtl); 2721 return true; 2722 } 2723 } 2724 else if (MEM_P (rtl)) 2725 { 2726 if (MEM_ATTRS (rtl)) 2727 { 2728 *declp = MEM_EXPR (rtl); 2729 *offsetp = MEM_OFFSET (rtl) ? INTVAL (MEM_OFFSET (rtl)) : 0; 2730 return true; 2731 } 2732 } 2733 return false; 2734} 2735 2736/* Insert function parameters to IN and OUT sets of ENTRY_BLOCK. */ 2737 2738static void 2739vt_add_function_parameters (void) 2740{ 2741 tree parm; 2742 2743 for (parm = DECL_ARGUMENTS (current_function_decl); 2744 parm; parm = TREE_CHAIN (parm)) 2745 { 2746 rtx decl_rtl = DECL_RTL_IF_SET (parm); 2747 rtx incoming = DECL_INCOMING_RTL (parm); 2748 tree decl; 2749 HOST_WIDE_INT offset; 2750 dataflow_set *out; 2751 2752 if (TREE_CODE (parm) != PARM_DECL) 2753 continue; 2754 2755 if (!DECL_NAME (parm)) 2756 continue; 2757 2758 if (!decl_rtl || !incoming) 2759 continue; 2760 2761 if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode) 2762 continue; 2763 2764 if (!vt_get_decl_and_offset (incoming, &decl, &offset)) 2765 if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset)) 2766 continue; 2767 2768 if (!decl) 2769 continue; 2770 2771 gcc_assert (parm == decl); 2772 2773 out = &VTI (ENTRY_BLOCK_PTR)->out; 2774 2775 if (REG_P (incoming)) 2776 { 2777 gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER); 2778 attrs_list_insert (&out->regs[REGNO (incoming)], 2779 parm, offset, incoming); 2780 set_variable_part (out, incoming, parm, offset); 2781 } 2782 else if (MEM_P (incoming)) 2783 set_variable_part (out, incoming, parm, offset); 2784 } 2785} 2786 2787/* Allocate and initialize the data structures for variable tracking 2788 and parse the RTL to get the micro operations. */ 2789 2790static void 2791vt_initialize (void) 2792{ 2793 basic_block bb; 2794 2795 alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def)); 2796 2797 FOR_EACH_BB (bb) 2798 { 2799 rtx insn; 2800 HOST_WIDE_INT pre, post = 0; 2801 2802 /* Count the number of micro operations. */ 2803 VTI (bb)->n_mos = 0; 2804 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 2805 insn = NEXT_INSN (insn)) 2806 { 2807 if (INSN_P (insn)) 2808 { 2809 if (!frame_pointer_needed) 2810 { 2811 insn_stack_adjust_offset_pre_post (insn, &pre, &post); 2812 if (pre) 2813 VTI (bb)->n_mos++; 2814 if (post) 2815 VTI (bb)->n_mos++; 2816 } 2817 note_uses (&PATTERN (insn), count_uses_1, insn); 2818 note_stores (PATTERN (insn), count_stores, insn); 2819 if (CALL_P (insn)) 2820 VTI (bb)->n_mos++; 2821 } 2822 } 2823 2824 /* Add the micro-operations to the array. */ 2825 VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos); 2826 VTI (bb)->n_mos = 0; 2827 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 2828 insn = NEXT_INSN (insn)) 2829 { 2830 if (INSN_P (insn)) 2831 { 2832 int n1, n2; 2833 2834 if (!frame_pointer_needed) 2835 { 2836 insn_stack_adjust_offset_pre_post (insn, &pre, &post); 2837 if (pre) 2838 { 2839 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2840 2841 mo->type = MO_ADJUST; 2842 mo->u.adjust = pre; 2843 mo->insn = insn; 2844 } 2845 } 2846 2847 n1 = VTI (bb)->n_mos; 2848 note_uses (&PATTERN (insn), add_uses_1, insn); 2849 n2 = VTI (bb)->n_mos - 1; 2850 2851 /* Order the MO_USEs to be before MO_USE_NO_VARs. */ 2852 while (n1 < n2) 2853 { 2854 while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE) 2855 n1++; 2856 while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR) 2857 n2--; 2858 if (n1 < n2) 2859 { 2860 micro_operation sw; 2861 2862 sw = VTI (bb)->mos[n1]; 2863 VTI (bb)->mos[n1] = VTI (bb)->mos[n2]; 2864 VTI (bb)->mos[n2] = sw; 2865 } 2866 } 2867 2868 if (CALL_P (insn)) 2869 { 2870 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2871 2872 mo->type = MO_CALL; 2873 mo->insn = insn; 2874 } 2875 2876 n1 = VTI (bb)->n_mos; 2877 /* This will record NEXT_INSN (insn), such that we can 2878 insert notes before it without worrying about any 2879 notes that MO_USEs might emit after the insn. */ 2880 note_stores (PATTERN (insn), add_stores, insn); 2881 n2 = VTI (bb)->n_mos - 1; 2882 2883 /* Order the MO_CLOBBERs to be before MO_SETs. */ 2884 while (n1 < n2) 2885 { 2886 while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER) 2887 n1++; 2888 while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET 2889 || VTI (bb)->mos[n2].type == MO_COPY)) 2890 n2--; 2891 if (n1 < n2) 2892 { 2893 micro_operation sw; 2894 2895 sw = VTI (bb)->mos[n1]; 2896 VTI (bb)->mos[n1] = VTI (bb)->mos[n2]; 2897 VTI (bb)->mos[n2] = sw; 2898 } 2899 } 2900 2901 if (!frame_pointer_needed && post) 2902 { 2903 micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2904 2905 mo->type = MO_ADJUST; 2906 mo->u.adjust = post; 2907 mo->insn = insn; 2908 } 2909 } 2910 } 2911 } 2912 2913 /* Init the IN and OUT sets. */ 2914 FOR_ALL_BB (bb) 2915 { 2916 VTI (bb)->visited = false; 2917 dataflow_set_init (&VTI (bb)->in, 7); 2918 dataflow_set_init (&VTI (bb)->out, 7); 2919 } 2920 2921 attrs_pool = create_alloc_pool ("attrs_def pool", 2922 sizeof (struct attrs_def), 1024); 2923 var_pool = create_alloc_pool ("variable_def pool", 2924 sizeof (struct variable_def), 64); 2925 loc_chain_pool = create_alloc_pool ("location_chain_def pool", 2926 sizeof (struct location_chain_def), 2927 1024); 2928 changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq, 2929 NULL); 2930 vt_add_function_parameters (); 2931} 2932 2933/* Free the data structures needed for variable tracking. */ 2934 2935static void 2936vt_finalize (void) 2937{ 2938 basic_block bb; 2939 2940 FOR_EACH_BB (bb) 2941 { 2942 free (VTI (bb)->mos); 2943 } 2944 2945 FOR_ALL_BB (bb) 2946 { 2947 dataflow_set_destroy (&VTI (bb)->in); 2948 dataflow_set_destroy (&VTI (bb)->out); 2949 } 2950 free_aux_for_blocks (); 2951 free_alloc_pool (attrs_pool); 2952 free_alloc_pool (var_pool); 2953 free_alloc_pool (loc_chain_pool); 2954 htab_delete (changed_variables); 2955} 2956 2957/* The entry point to variable tracking pass. */ 2958 2959unsigned int 2960variable_tracking_main (void) 2961{ 2962 if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20) 2963 return 0; 2964 2965 mark_dfs_back_edges (); 2966 vt_initialize (); 2967 if (!frame_pointer_needed) 2968 { 2969 if (!vt_stack_adjustments ()) 2970 { 2971 vt_finalize (); 2972 return 0; 2973 } 2974 } 2975 2976 vt_find_locations (); 2977 vt_emit_notes (); 2978 2979 if (dump_file && (dump_flags & TDF_DETAILS)) 2980 { 2981 dump_dataflow_sets (); 2982 dump_flow_info (dump_file, dump_flags); 2983 } 2984 2985 vt_finalize (); 2986 return 0; 2987} 2988 2989static bool 2990gate_handle_var_tracking (void) 2991{ 2992 return (flag_var_tracking); 2993} 2994 2995 2996 2997struct tree_opt_pass pass_variable_tracking = 2998{ 2999 "vartrack", /* name */ 3000 gate_handle_var_tracking, /* gate */ 3001 variable_tracking_main, /* execute */ 3002 NULL, /* sub */ 3003 NULL, /* next */ 3004 0, /* static_pass_number */ 3005 TV_VAR_TRACKING, /* tv_id */ 3006 0, /* properties_required */ 3007 0, /* properties_provided */ 3008 0, /* properties_destroyed */ 3009 0, /* todo_flags_start */ 3010 TODO_dump_func, /* todo_flags_finish */ 3011 'V' /* letter */ 3012}; 3013 3014