1169689Skan/* Variable tracking routines for the GNU compiler. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689Skan This file is part of GCC. 5169689Skan 6169689Skan GCC is free software; you can redistribute it and/or modify it 7169689Skan under the terms of the GNU General Public License as published by 8169689Skan the Free Software Foundation; either version 2, or (at your option) 9169689Skan any later version. 10169689Skan 11169689Skan GCC is distributed in the hope that it will be useful, but WITHOUT 12169689Skan ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13169689Skan or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14169689Skan License for more details. 15169689Skan 16169689Skan You should have received a copy of the GNU General Public License 17169689Skan along with GCC; see the file COPYING. If not, write to the Free 18169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan 02110-1301, USA. */ 20169689Skan 21169689Skan/* This file contains the variable tracking pass. It computes where 22169689Skan variables are located (which registers or where in memory) at each position 23169689Skan in instruction stream and emits notes describing the locations. 24169689Skan Debug information (DWARF2 location lists) is finally generated from 25169689Skan these notes. 26169689Skan With this debug information, it is possible to show variables 27169689Skan even when debugging optimized code. 28169689Skan 29169689Skan How does the variable tracking pass work? 30169689Skan 31169689Skan First, it scans RTL code for uses, stores and clobbers (register/memory 32169689Skan references in instructions), for call insns and for stack adjustments 33169689Skan separately for each basic block and saves them to an array of micro 34169689Skan operations. 35169689Skan The micro operations of one instruction are ordered so that 36169689Skan pre-modifying stack adjustment < use < use with no var < call insn < 37169689Skan < set < clobber < post-modifying stack adjustment 38169689Skan 39169689Skan Then, a forward dataflow analysis is performed to find out how locations 40169689Skan of variables change through code and to propagate the variable locations 41169689Skan along control flow graph. 42169689Skan The IN set for basic block BB is computed as a union of OUT sets of BB's 43169689Skan predecessors, the OUT set for BB is copied from the IN set for BB and 44169689Skan is changed according to micro operations in BB. 45169689Skan 46169689Skan The IN and OUT sets for basic blocks consist of a current stack adjustment 47169689Skan (used for adjusting offset of variables addressed using stack pointer), 48169689Skan the table of structures describing the locations of parts of a variable 49169689Skan and for each physical register a linked list for each physical register. 50169689Skan The linked list is a list of variable parts stored in the register, 51169689Skan i.e. it is a list of triplets (reg, decl, offset) where decl is 52169689Skan REG_EXPR (reg) and offset is REG_OFFSET (reg). The linked list is used for 53169689Skan effective deleting appropriate variable parts when we set or clobber the 54169689Skan register. 55169689Skan 56169689Skan There may be more than one variable part in a register. The linked lists 57169689Skan should be pretty short so it is a good data structure here. 58169689Skan For example in the following code, register allocator may assign same 59169689Skan register to variables A and B, and both of them are stored in the same 60169689Skan register in CODE: 61169689Skan 62169689Skan if (cond) 63169689Skan set A; 64169689Skan else 65169689Skan set B; 66169689Skan CODE; 67169689Skan if (cond) 68169689Skan use A; 69169689Skan else 70169689Skan use B; 71169689Skan 72169689Skan Finally, the NOTE_INSN_VAR_LOCATION notes describing the variable locations 73169689Skan are emitted to appropriate positions in RTL code. Each such a note describes 74169689Skan the location of one variable at the point in instruction stream where the 75169689Skan note is. There is no need to emit a note for each variable before each 76169689Skan instruction, we only emit these notes where the location of variable changes 77169689Skan (this means that we also emit notes for changes between the OUT set of the 78169689Skan previous block and the IN set of the current block). 79169689Skan 80169689Skan The notes consist of two parts: 81169689Skan 1. the declaration (from REG_EXPR or MEM_EXPR) 82169689Skan 2. the location of a variable - it is either a simple register/memory 83169689Skan reference (for simple variables, for example int), 84169689Skan or a parallel of register/memory references (for a large variables 85169689Skan which consist of several parts, for example long long). 86169689Skan 87169689Skan*/ 88169689Skan 89169689Skan#include "config.h" 90169689Skan#include "system.h" 91169689Skan#include "coretypes.h" 92169689Skan#include "tm.h" 93169689Skan#include "rtl.h" 94169689Skan#include "tree.h" 95169689Skan#include "hard-reg-set.h" 96169689Skan#include "basic-block.h" 97169689Skan#include "flags.h" 98169689Skan#include "output.h" 99169689Skan#include "insn-config.h" 100169689Skan#include "reload.h" 101169689Skan#include "sbitmap.h" 102169689Skan#include "alloc-pool.h" 103169689Skan#include "fibheap.h" 104169689Skan#include "hashtab.h" 105169689Skan#include "regs.h" 106169689Skan#include "expr.h" 107169689Skan#include "timevar.h" 108169689Skan#include "tree-pass.h" 109169689Skan 110169689Skan/* Type of micro operation. */ 111169689Skanenum micro_operation_type 112169689Skan{ 113169689Skan MO_USE, /* Use location (REG or MEM). */ 114169689Skan MO_USE_NO_VAR,/* Use location which is not associated with a variable 115169689Skan or the variable is not trackable. */ 116169689Skan MO_SET, /* Set location. */ 117169689Skan MO_COPY, /* Copy the same portion of a variable from one 118169689Skan location to another. */ 119169689Skan MO_CLOBBER, /* Clobber location. */ 120169689Skan MO_CALL, /* Call insn. */ 121169689Skan MO_ADJUST /* Adjust stack pointer. */ 122169689Skan}; 123169689Skan 124169689Skan/* Where shall the note be emitted? BEFORE or AFTER the instruction. */ 125169689Skanenum emit_note_where 126169689Skan{ 127169689Skan EMIT_NOTE_BEFORE_INSN, 128169689Skan EMIT_NOTE_AFTER_INSN 129169689Skan}; 130169689Skan 131169689Skan/* Structure holding information about micro operation. */ 132169689Skantypedef struct micro_operation_def 133169689Skan{ 134169689Skan /* Type of micro operation. */ 135169689Skan enum micro_operation_type type; 136169689Skan 137169689Skan union { 138169689Skan /* Location. */ 139169689Skan rtx loc; 140169689Skan 141169689Skan /* Stack adjustment. */ 142169689Skan HOST_WIDE_INT adjust; 143169689Skan } u; 144169689Skan 145169689Skan /* The instruction which the micro operation is in, for MO_USE, 146169689Skan MO_USE_NO_VAR, MO_CALL and MO_ADJUST, or the subsequent 147169689Skan instruction or note in the original flow (before any var-tracking 148169689Skan notes are inserted, to simplify emission of notes), for MO_SET 149169689Skan and MO_CLOBBER. */ 150169689Skan rtx insn; 151169689Skan} micro_operation; 152169689Skan 153169689Skan/* Structure for passing some other parameters to function 154169689Skan emit_note_insn_var_location. */ 155169689Skantypedef struct emit_note_data_def 156169689Skan{ 157169689Skan /* The instruction which the note will be emitted before/after. */ 158169689Skan rtx insn; 159169689Skan 160169689Skan /* Where the note will be emitted (before/after insn)? */ 161169689Skan enum emit_note_where where; 162169689Skan} emit_note_data; 163169689Skan 164169689Skan/* Description of location of a part of a variable. The content of a physical 165169689Skan register is described by a chain of these structures. 166169689Skan The chains are pretty short (usually 1 or 2 elements) and thus 167169689Skan chain is the best data structure. */ 168169689Skantypedef struct attrs_def 169169689Skan{ 170169689Skan /* Pointer to next member of the list. */ 171169689Skan struct attrs_def *next; 172169689Skan 173169689Skan /* The rtx of register. */ 174169689Skan rtx loc; 175169689Skan 176169689Skan /* The declaration corresponding to LOC. */ 177169689Skan tree decl; 178169689Skan 179169689Skan /* Offset from start of DECL. */ 180169689Skan HOST_WIDE_INT offset; 181169689Skan} *attrs; 182169689Skan 183169689Skan/* Structure holding the IN or OUT set for a basic block. */ 184169689Skantypedef struct dataflow_set_def 185169689Skan{ 186169689Skan /* Adjustment of stack offset. */ 187169689Skan HOST_WIDE_INT stack_adjust; 188169689Skan 189169689Skan /* Attributes for registers (lists of attrs). */ 190169689Skan attrs regs[FIRST_PSEUDO_REGISTER]; 191169689Skan 192169689Skan /* Variable locations. */ 193169689Skan htab_t vars; 194169689Skan} dataflow_set; 195169689Skan 196169689Skan/* The structure (one for each basic block) containing the information 197169689Skan needed for variable tracking. */ 198169689Skantypedef struct variable_tracking_info_def 199169689Skan{ 200169689Skan /* Number of micro operations stored in the MOS array. */ 201169689Skan int n_mos; 202169689Skan 203169689Skan /* The array of micro operations. */ 204169689Skan micro_operation *mos; 205169689Skan 206169689Skan /* The IN and OUT set for dataflow analysis. */ 207169689Skan dataflow_set in; 208169689Skan dataflow_set out; 209169689Skan 210169689Skan /* Has the block been visited in DFS? */ 211169689Skan bool visited; 212169689Skan} *variable_tracking_info; 213169689Skan 214169689Skan/* Structure for chaining the locations. */ 215169689Skantypedef struct location_chain_def 216169689Skan{ 217169689Skan /* Next element in the chain. */ 218169689Skan struct location_chain_def *next; 219169689Skan 220169689Skan /* The location (REG or MEM). */ 221169689Skan rtx loc; 222169689Skan} *location_chain; 223169689Skan 224169689Skan/* Structure describing one part of variable. */ 225169689Skantypedef struct variable_part_def 226169689Skan{ 227169689Skan /* Chain of locations of the part. */ 228169689Skan location_chain loc_chain; 229169689Skan 230169689Skan /* Location which was last emitted to location list. */ 231169689Skan rtx cur_loc; 232169689Skan 233169689Skan /* The offset in the variable. */ 234169689Skan HOST_WIDE_INT offset; 235169689Skan} variable_part; 236169689Skan 237169689Skan/* Maximum number of location parts. */ 238169689Skan#define MAX_VAR_PARTS 16 239169689Skan 240169689Skan/* Structure describing where the variable is located. */ 241169689Skantypedef struct variable_def 242169689Skan{ 243169689Skan /* The declaration of the variable. */ 244169689Skan tree decl; 245169689Skan 246169689Skan /* Reference count. */ 247169689Skan int refcount; 248169689Skan 249169689Skan /* Number of variable parts. */ 250169689Skan int n_var_parts; 251169689Skan 252169689Skan /* The variable parts. */ 253169689Skan variable_part var_part[MAX_VAR_PARTS]; 254169689Skan} *variable; 255169689Skan 256169689Skan/* Hash function for DECL for VARIABLE_HTAB. */ 257169689Skan#define VARIABLE_HASH_VAL(decl) (DECL_UID (decl)) 258169689Skan 259169689Skan/* Pointer to the BB's information specific to variable tracking pass. */ 260169689Skan#define VTI(BB) ((variable_tracking_info) (BB)->aux) 261169689Skan 262235623Spfg/* Macro to access MEM_OFFSET as an HOST_WIDE_INT. Evaluates MEM twice. */ 263235623Spfg#define INT_MEM_OFFSET(mem) (MEM_OFFSET (mem) ? INTVAL (MEM_OFFSET (mem)) : 0) 264235623Spfg 265169689Skan/* Alloc pool for struct attrs_def. */ 266169689Skanstatic alloc_pool attrs_pool; 267169689Skan 268169689Skan/* Alloc pool for struct variable_def. */ 269169689Skanstatic alloc_pool var_pool; 270169689Skan 271169689Skan/* Alloc pool for struct location_chain_def. */ 272169689Skanstatic alloc_pool loc_chain_pool; 273169689Skan 274169689Skan/* Changed variables, notes will be emitted for them. */ 275169689Skanstatic htab_t changed_variables; 276169689Skan 277169689Skan/* Shall notes be emitted? */ 278169689Skanstatic bool emit_notes; 279169689Skan 280169689Skan/* Local function prototypes. */ 281169689Skanstatic void stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *, 282169689Skan HOST_WIDE_INT *); 283169689Skanstatic void insn_stack_adjust_offset_pre_post (rtx, HOST_WIDE_INT *, 284169689Skan HOST_WIDE_INT *); 285169689Skanstatic void bb_stack_adjust_offset (basic_block); 286169689Skanstatic bool vt_stack_adjustments (void); 287169689Skanstatic rtx adjust_stack_reference (rtx, HOST_WIDE_INT); 288169689Skanstatic hashval_t variable_htab_hash (const void *); 289169689Skanstatic int variable_htab_eq (const void *, const void *); 290169689Skanstatic void variable_htab_free (void *); 291169689Skan 292169689Skanstatic void init_attrs_list_set (attrs *); 293169689Skanstatic void attrs_list_clear (attrs *); 294169689Skanstatic attrs attrs_list_member (attrs, tree, HOST_WIDE_INT); 295169689Skanstatic void attrs_list_insert (attrs *, tree, HOST_WIDE_INT, rtx); 296169689Skanstatic void attrs_list_copy (attrs *, attrs); 297169689Skanstatic void attrs_list_union (attrs *, attrs); 298169689Skan 299169689Skanstatic void vars_clear (htab_t); 300169689Skanstatic variable unshare_variable (dataflow_set *set, variable var); 301169689Skanstatic int vars_copy_1 (void **, void *); 302169689Skanstatic void vars_copy (htab_t, htab_t); 303169689Skanstatic tree var_debug_decl (tree); 304169689Skanstatic void var_reg_set (dataflow_set *, rtx); 305169689Skanstatic void var_reg_delete_and_set (dataflow_set *, rtx, bool); 306169689Skanstatic void var_reg_delete (dataflow_set *, rtx, bool); 307169689Skanstatic void var_regno_delete (dataflow_set *, int); 308169689Skanstatic void var_mem_set (dataflow_set *, rtx); 309169689Skanstatic void var_mem_delete_and_set (dataflow_set *, rtx, bool); 310169689Skanstatic void var_mem_delete (dataflow_set *, rtx, bool); 311169689Skan 312169689Skanstatic void dataflow_set_init (dataflow_set *, int); 313169689Skanstatic void dataflow_set_clear (dataflow_set *); 314169689Skanstatic void dataflow_set_copy (dataflow_set *, dataflow_set *); 315169689Skanstatic int variable_union_info_cmp_pos (const void *, const void *); 316169689Skanstatic int variable_union (void **, void *); 317169689Skanstatic void dataflow_set_union (dataflow_set *, dataflow_set *); 318169689Skanstatic bool variable_part_different_p (variable_part *, variable_part *); 319169689Skanstatic bool variable_different_p (variable, variable, bool); 320169689Skanstatic int dataflow_set_different_1 (void **, void *); 321169689Skanstatic int dataflow_set_different_2 (void **, void *); 322169689Skanstatic bool dataflow_set_different (dataflow_set *, dataflow_set *); 323169689Skanstatic void dataflow_set_destroy (dataflow_set *); 324169689Skan 325169689Skanstatic bool contains_symbol_ref (rtx); 326169689Skanstatic bool track_expr_p (tree); 327169689Skanstatic bool same_variable_part_p (rtx, tree, HOST_WIDE_INT); 328169689Skanstatic int count_uses (rtx *, void *); 329169689Skanstatic void count_uses_1 (rtx *, void *); 330169689Skanstatic void count_stores (rtx, rtx, void *); 331169689Skanstatic int add_uses (rtx *, void *); 332169689Skanstatic void add_uses_1 (rtx *, void *); 333169689Skanstatic void add_stores (rtx, rtx, void *); 334169689Skanstatic bool compute_bb_dataflow (basic_block); 335169689Skanstatic void vt_find_locations (void); 336169689Skan 337169689Skanstatic void dump_attrs_list (attrs); 338169689Skanstatic int dump_variable (void **, void *); 339169689Skanstatic void dump_vars (htab_t); 340169689Skanstatic void dump_dataflow_set (dataflow_set *); 341169689Skanstatic void dump_dataflow_sets (void); 342169689Skan 343169689Skanstatic void variable_was_changed (variable, htab_t); 344169689Skanstatic void set_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 345169689Skanstatic void clobber_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 346169689Skanstatic void delete_variable_part (dataflow_set *, rtx, tree, HOST_WIDE_INT); 347169689Skanstatic int emit_note_insn_var_location (void **, void *); 348169689Skanstatic void emit_notes_for_changes (rtx, enum emit_note_where); 349169689Skanstatic int emit_notes_for_differences_1 (void **, void *); 350169689Skanstatic int emit_notes_for_differences_2 (void **, void *); 351169689Skanstatic void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *); 352169689Skanstatic void emit_notes_in_bb (basic_block); 353169689Skanstatic void vt_emit_notes (void); 354169689Skan 355169689Skanstatic bool vt_get_decl_and_offset (rtx, tree *, HOST_WIDE_INT *); 356169689Skanstatic void vt_add_function_parameters (void); 357169689Skanstatic void vt_initialize (void); 358169689Skanstatic void vt_finalize (void); 359169689Skan 360169689Skan/* Given a SET, calculate the amount of stack adjustment it contains 361169689Skan PRE- and POST-modifying stack pointer. 362169689Skan This function is similar to stack_adjust_offset. */ 363169689Skan 364169689Skanstatic void 365169689Skanstack_adjust_offset_pre_post (rtx pattern, HOST_WIDE_INT *pre, 366169689Skan HOST_WIDE_INT *post) 367169689Skan{ 368169689Skan rtx src = SET_SRC (pattern); 369169689Skan rtx dest = SET_DEST (pattern); 370169689Skan enum rtx_code code; 371169689Skan 372169689Skan if (dest == stack_pointer_rtx) 373169689Skan { 374169689Skan /* (set (reg sp) (plus (reg sp) (const_int))) */ 375169689Skan code = GET_CODE (src); 376169689Skan if (! (code == PLUS || code == MINUS) 377169689Skan || XEXP (src, 0) != stack_pointer_rtx 378169689Skan || GET_CODE (XEXP (src, 1)) != CONST_INT) 379169689Skan return; 380169689Skan 381169689Skan if (code == MINUS) 382169689Skan *post += INTVAL (XEXP (src, 1)); 383169689Skan else 384169689Skan *post -= INTVAL (XEXP (src, 1)); 385169689Skan } 386169689Skan else if (MEM_P (dest)) 387169689Skan { 388169689Skan /* (set (mem (pre_dec (reg sp))) (foo)) */ 389169689Skan src = XEXP (dest, 0); 390169689Skan code = GET_CODE (src); 391169689Skan 392169689Skan switch (code) 393169689Skan { 394169689Skan case PRE_MODIFY: 395169689Skan case POST_MODIFY: 396169689Skan if (XEXP (src, 0) == stack_pointer_rtx) 397169689Skan { 398169689Skan rtx val = XEXP (XEXP (src, 1), 1); 399169689Skan /* We handle only adjustments by constant amount. */ 400169689Skan gcc_assert (GET_CODE (XEXP (src, 1)) == PLUS && 401169689Skan GET_CODE (val) == CONST_INT); 402169689Skan 403169689Skan if (code == PRE_MODIFY) 404169689Skan *pre -= INTVAL (val); 405169689Skan else 406169689Skan *post -= INTVAL (val); 407169689Skan break; 408169689Skan } 409169689Skan return; 410169689Skan 411169689Skan case PRE_DEC: 412169689Skan if (XEXP (src, 0) == stack_pointer_rtx) 413169689Skan { 414169689Skan *pre += GET_MODE_SIZE (GET_MODE (dest)); 415169689Skan break; 416169689Skan } 417169689Skan return; 418169689Skan 419169689Skan case POST_DEC: 420169689Skan if (XEXP (src, 0) == stack_pointer_rtx) 421169689Skan { 422169689Skan *post += GET_MODE_SIZE (GET_MODE (dest)); 423169689Skan break; 424169689Skan } 425169689Skan return; 426169689Skan 427169689Skan case PRE_INC: 428169689Skan if (XEXP (src, 0) == stack_pointer_rtx) 429169689Skan { 430169689Skan *pre -= GET_MODE_SIZE (GET_MODE (dest)); 431169689Skan break; 432169689Skan } 433169689Skan return; 434169689Skan 435169689Skan case POST_INC: 436169689Skan if (XEXP (src, 0) == stack_pointer_rtx) 437169689Skan { 438169689Skan *post -= GET_MODE_SIZE (GET_MODE (dest)); 439169689Skan break; 440169689Skan } 441169689Skan return; 442169689Skan 443169689Skan default: 444169689Skan return; 445169689Skan } 446169689Skan } 447169689Skan} 448169689Skan 449169689Skan/* Given an INSN, calculate the amount of stack adjustment it contains 450169689Skan PRE- and POST-modifying stack pointer. */ 451169689Skan 452169689Skanstatic void 453169689Skaninsn_stack_adjust_offset_pre_post (rtx insn, HOST_WIDE_INT *pre, 454169689Skan HOST_WIDE_INT *post) 455169689Skan{ 456169689Skan *pre = 0; 457169689Skan *post = 0; 458169689Skan 459169689Skan if (GET_CODE (PATTERN (insn)) == SET) 460169689Skan stack_adjust_offset_pre_post (PATTERN (insn), pre, post); 461169689Skan else if (GET_CODE (PATTERN (insn)) == PARALLEL 462169689Skan || GET_CODE (PATTERN (insn)) == SEQUENCE) 463169689Skan { 464169689Skan int i; 465169689Skan 466169689Skan /* There may be stack adjustments inside compound insns. Search 467169689Skan for them. */ 468169689Skan for ( i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 469169689Skan if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET) 470169689Skan stack_adjust_offset_pre_post (XVECEXP (PATTERN (insn), 0, i), 471169689Skan pre, post); 472169689Skan } 473169689Skan} 474169689Skan 475169689Skan/* Compute stack adjustment in basic block BB. */ 476169689Skan 477169689Skanstatic void 478169689Skanbb_stack_adjust_offset (basic_block bb) 479169689Skan{ 480169689Skan HOST_WIDE_INT offset; 481169689Skan int i; 482169689Skan 483169689Skan offset = VTI (bb)->in.stack_adjust; 484169689Skan for (i = 0; i < VTI (bb)->n_mos; i++) 485169689Skan { 486169689Skan if (VTI (bb)->mos[i].type == MO_ADJUST) 487169689Skan offset += VTI (bb)->mos[i].u.adjust; 488169689Skan else if (VTI (bb)->mos[i].type != MO_CALL) 489169689Skan { 490169689Skan if (MEM_P (VTI (bb)->mos[i].u.loc)) 491169689Skan { 492169689Skan VTI (bb)->mos[i].u.loc 493169689Skan = adjust_stack_reference (VTI (bb)->mos[i].u.loc, -offset); 494169689Skan } 495169689Skan } 496169689Skan } 497169689Skan VTI (bb)->out.stack_adjust = offset; 498169689Skan} 499169689Skan 500169689Skan/* Compute stack adjustments for all blocks by traversing DFS tree. 501169689Skan Return true when the adjustments on all incoming edges are consistent. 502169689Skan Heavily borrowed from pre_and_rev_post_order_compute. */ 503169689Skan 504169689Skanstatic bool 505169689Skanvt_stack_adjustments (void) 506169689Skan{ 507169689Skan edge_iterator *stack; 508169689Skan int sp; 509169689Skan 510169689Skan /* Initialize entry block. */ 511169689Skan VTI (ENTRY_BLOCK_PTR)->visited = true; 512169689Skan VTI (ENTRY_BLOCK_PTR)->out.stack_adjust = INCOMING_FRAME_SP_OFFSET; 513169689Skan 514169689Skan /* Allocate stack for back-tracking up CFG. */ 515169689Skan stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 516169689Skan sp = 0; 517169689Skan 518169689Skan /* Push the first edge on to the stack. */ 519169689Skan stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 520169689Skan 521169689Skan while (sp) 522169689Skan { 523169689Skan edge_iterator ei; 524169689Skan basic_block src; 525169689Skan basic_block dest; 526169689Skan 527169689Skan /* Look at the edge on the top of the stack. */ 528169689Skan ei = stack[sp - 1]; 529169689Skan src = ei_edge (ei)->src; 530169689Skan dest = ei_edge (ei)->dest; 531169689Skan 532169689Skan /* Check if the edge destination has been visited yet. */ 533169689Skan if (!VTI (dest)->visited) 534169689Skan { 535169689Skan VTI (dest)->visited = true; 536169689Skan VTI (dest)->in.stack_adjust = VTI (src)->out.stack_adjust; 537169689Skan bb_stack_adjust_offset (dest); 538169689Skan 539169689Skan if (EDGE_COUNT (dest->succs) > 0) 540169689Skan /* Since the DEST node has been visited for the first 541169689Skan time, check its successors. */ 542169689Skan stack[sp++] = ei_start (dest->succs); 543169689Skan } 544169689Skan else 545169689Skan { 546169689Skan /* Check whether the adjustments on the edges are the same. */ 547169689Skan if (VTI (dest)->in.stack_adjust != VTI (src)->out.stack_adjust) 548169689Skan { 549169689Skan free (stack); 550169689Skan return false; 551169689Skan } 552169689Skan 553169689Skan if (! ei_one_before_end_p (ei)) 554169689Skan /* Go to the next edge. */ 555169689Skan ei_next (&stack[sp - 1]); 556169689Skan else 557169689Skan /* Return to previous level if there are no more edges. */ 558169689Skan sp--; 559169689Skan } 560169689Skan } 561169689Skan 562169689Skan free (stack); 563169689Skan return true; 564169689Skan} 565169689Skan 566169689Skan/* Adjust stack reference MEM by ADJUSTMENT bytes and make it relative 567169689Skan to the argument pointer. Return the new rtx. */ 568169689Skan 569169689Skanstatic rtx 570169689Skanadjust_stack_reference (rtx mem, HOST_WIDE_INT adjustment) 571169689Skan{ 572169689Skan rtx addr, cfa, tmp; 573169689Skan 574169689Skan#ifdef FRAME_POINTER_CFA_OFFSET 575169689Skan adjustment -= FRAME_POINTER_CFA_OFFSET (current_function_decl); 576169689Skan cfa = plus_constant (frame_pointer_rtx, adjustment); 577169689Skan#else 578169689Skan adjustment -= ARG_POINTER_CFA_OFFSET (current_function_decl); 579169689Skan cfa = plus_constant (arg_pointer_rtx, adjustment); 580169689Skan#endif 581169689Skan 582169689Skan addr = replace_rtx (copy_rtx (XEXP (mem, 0)), stack_pointer_rtx, cfa); 583169689Skan tmp = simplify_rtx (addr); 584169689Skan if (tmp) 585169689Skan addr = tmp; 586169689Skan 587169689Skan return replace_equiv_address_nv (mem, addr); 588169689Skan} 589169689Skan 590169689Skan/* The hash function for variable_htab, computes the hash value 591169689Skan from the declaration of variable X. */ 592169689Skan 593169689Skanstatic hashval_t 594169689Skanvariable_htab_hash (const void *x) 595169689Skan{ 596169689Skan const variable v = (const variable) x; 597169689Skan 598169689Skan return (VARIABLE_HASH_VAL (v->decl)); 599169689Skan} 600169689Skan 601169689Skan/* Compare the declaration of variable X with declaration Y. */ 602169689Skan 603169689Skanstatic int 604169689Skanvariable_htab_eq (const void *x, const void *y) 605169689Skan{ 606169689Skan const variable v = (const variable) x; 607169689Skan const tree decl = (const tree) y; 608169689Skan 609169689Skan return (VARIABLE_HASH_VAL (v->decl) == VARIABLE_HASH_VAL (decl)); 610169689Skan} 611169689Skan 612169689Skan/* Free the element of VARIABLE_HTAB (its type is struct variable_def). */ 613169689Skan 614169689Skanstatic void 615169689Skanvariable_htab_free (void *elem) 616169689Skan{ 617169689Skan int i; 618169689Skan variable var = (variable) elem; 619169689Skan location_chain node, next; 620169689Skan 621169689Skan gcc_assert (var->refcount > 0); 622169689Skan 623169689Skan var->refcount--; 624169689Skan if (var->refcount > 0) 625169689Skan return; 626169689Skan 627169689Skan for (i = 0; i < var->n_var_parts; i++) 628169689Skan { 629169689Skan for (node = var->var_part[i].loc_chain; node; node = next) 630169689Skan { 631169689Skan next = node->next; 632169689Skan pool_free (loc_chain_pool, node); 633169689Skan } 634169689Skan var->var_part[i].loc_chain = NULL; 635169689Skan } 636169689Skan pool_free (var_pool, var); 637169689Skan} 638169689Skan 639169689Skan/* Initialize the set (array) SET of attrs to empty lists. */ 640169689Skan 641169689Skanstatic void 642169689Skaninit_attrs_list_set (attrs *set) 643169689Skan{ 644169689Skan int i; 645169689Skan 646169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 647169689Skan set[i] = NULL; 648169689Skan} 649169689Skan 650169689Skan/* Make the list *LISTP empty. */ 651169689Skan 652169689Skanstatic void 653169689Skanattrs_list_clear (attrs *listp) 654169689Skan{ 655169689Skan attrs list, next; 656169689Skan 657169689Skan for (list = *listp; list; list = next) 658169689Skan { 659169689Skan next = list->next; 660169689Skan pool_free (attrs_pool, list); 661169689Skan } 662169689Skan *listp = NULL; 663169689Skan} 664169689Skan 665169689Skan/* Return true if the pair of DECL and OFFSET is the member of the LIST. */ 666169689Skan 667169689Skanstatic attrs 668169689Skanattrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset) 669169689Skan{ 670169689Skan for (; list; list = list->next) 671169689Skan if (list->decl == decl && list->offset == offset) 672169689Skan return list; 673169689Skan return NULL; 674169689Skan} 675169689Skan 676169689Skan/* Insert the triplet DECL, OFFSET, LOC to the list *LISTP. */ 677169689Skan 678169689Skanstatic void 679169689Skanattrs_list_insert (attrs *listp, tree decl, HOST_WIDE_INT offset, rtx loc) 680169689Skan{ 681169689Skan attrs list; 682169689Skan 683169689Skan list = pool_alloc (attrs_pool); 684169689Skan list->loc = loc; 685169689Skan list->decl = decl; 686169689Skan list->offset = offset; 687169689Skan list->next = *listp; 688169689Skan *listp = list; 689169689Skan} 690169689Skan 691169689Skan/* Copy all nodes from SRC and create a list *DSTP of the copies. */ 692169689Skan 693169689Skanstatic void 694169689Skanattrs_list_copy (attrs *dstp, attrs src) 695169689Skan{ 696169689Skan attrs n; 697169689Skan 698169689Skan attrs_list_clear (dstp); 699169689Skan for (; src; src = src->next) 700169689Skan { 701169689Skan n = pool_alloc (attrs_pool); 702169689Skan n->loc = src->loc; 703169689Skan n->decl = src->decl; 704169689Skan n->offset = src->offset; 705169689Skan n->next = *dstp; 706169689Skan *dstp = n; 707169689Skan } 708169689Skan} 709169689Skan 710169689Skan/* Add all nodes from SRC which are not in *DSTP to *DSTP. */ 711169689Skan 712169689Skanstatic void 713169689Skanattrs_list_union (attrs *dstp, attrs src) 714169689Skan{ 715169689Skan for (; src; src = src->next) 716169689Skan { 717169689Skan if (!attrs_list_member (*dstp, src->decl, src->offset)) 718169689Skan attrs_list_insert (dstp, src->decl, src->offset, src->loc); 719169689Skan } 720169689Skan} 721169689Skan 722169689Skan/* Delete all variables from hash table VARS. */ 723169689Skan 724169689Skanstatic void 725169689Skanvars_clear (htab_t vars) 726169689Skan{ 727169689Skan htab_empty (vars); 728169689Skan} 729169689Skan 730169689Skan/* Return a copy of a variable VAR and insert it to dataflow set SET. */ 731169689Skan 732169689Skanstatic variable 733169689Skanunshare_variable (dataflow_set *set, variable var) 734169689Skan{ 735169689Skan void **slot; 736169689Skan variable new_var; 737169689Skan int i; 738169689Skan 739169689Skan new_var = pool_alloc (var_pool); 740169689Skan new_var->decl = var->decl; 741169689Skan new_var->refcount = 1; 742169689Skan var->refcount--; 743169689Skan new_var->n_var_parts = var->n_var_parts; 744169689Skan 745169689Skan for (i = 0; i < var->n_var_parts; i++) 746169689Skan { 747169689Skan location_chain node; 748169689Skan location_chain *nextp; 749169689Skan 750169689Skan new_var->var_part[i].offset = var->var_part[i].offset; 751169689Skan nextp = &new_var->var_part[i].loc_chain; 752169689Skan for (node = var->var_part[i].loc_chain; node; node = node->next) 753169689Skan { 754169689Skan location_chain new_lc; 755169689Skan 756169689Skan new_lc = pool_alloc (loc_chain_pool); 757169689Skan new_lc->next = NULL; 758169689Skan new_lc->loc = node->loc; 759169689Skan 760169689Skan *nextp = new_lc; 761169689Skan nextp = &new_lc->next; 762169689Skan } 763169689Skan 764169689Skan /* We are at the basic block boundary when copying variable description 765169689Skan so set the CUR_LOC to be the first element of the chain. */ 766169689Skan if (new_var->var_part[i].loc_chain) 767169689Skan new_var->var_part[i].cur_loc = new_var->var_part[i].loc_chain->loc; 768169689Skan else 769169689Skan new_var->var_part[i].cur_loc = NULL; 770169689Skan } 771169689Skan 772169689Skan slot = htab_find_slot_with_hash (set->vars, new_var->decl, 773169689Skan VARIABLE_HASH_VAL (new_var->decl), 774169689Skan INSERT); 775169689Skan *slot = new_var; 776169689Skan return new_var; 777169689Skan} 778169689Skan 779169689Skan/* Add a variable from *SLOT to hash table DATA and increase its reference 780169689Skan count. */ 781169689Skan 782169689Skanstatic int 783169689Skanvars_copy_1 (void **slot, void *data) 784169689Skan{ 785169689Skan htab_t dst = (htab_t) data; 786169689Skan variable src, *dstp; 787169689Skan 788169689Skan src = *(variable *) slot; 789169689Skan src->refcount++; 790169689Skan 791169689Skan dstp = (variable *) htab_find_slot_with_hash (dst, src->decl, 792169689Skan VARIABLE_HASH_VAL (src->decl), 793169689Skan INSERT); 794169689Skan *dstp = src; 795169689Skan 796169689Skan /* Continue traversing the hash table. */ 797169689Skan return 1; 798169689Skan} 799169689Skan 800169689Skan/* Copy all variables from hash table SRC to hash table DST. */ 801169689Skan 802169689Skanstatic void 803169689Skanvars_copy (htab_t dst, htab_t src) 804169689Skan{ 805169689Skan vars_clear (dst); 806169689Skan htab_traverse (src, vars_copy_1, dst); 807169689Skan} 808169689Skan 809169689Skan/* Map a decl to its main debug decl. */ 810169689Skan 811169689Skanstatic inline tree 812169689Skanvar_debug_decl (tree decl) 813169689Skan{ 814169689Skan if (decl && DECL_P (decl) 815169689Skan && DECL_DEBUG_EXPR_IS_FROM (decl) && DECL_DEBUG_EXPR (decl) 816169689Skan && DECL_P (DECL_DEBUG_EXPR (decl))) 817169689Skan decl = DECL_DEBUG_EXPR (decl); 818169689Skan 819169689Skan return decl; 820169689Skan} 821169689Skan 822169689Skan/* Set the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). */ 823169689Skan 824169689Skanstatic void 825169689Skanvar_reg_set (dataflow_set *set, rtx loc) 826169689Skan{ 827169689Skan tree decl = REG_EXPR (loc); 828169689Skan HOST_WIDE_INT offset = REG_OFFSET (loc); 829169689Skan attrs node; 830169689Skan 831169689Skan decl = var_debug_decl (decl); 832169689Skan 833169689Skan for (node = set->regs[REGNO (loc)]; node; node = node->next) 834169689Skan if (node->decl == decl && node->offset == offset) 835169689Skan break; 836169689Skan if (!node) 837169689Skan attrs_list_insert (&set->regs[REGNO (loc)], decl, offset, loc); 838169689Skan set_variable_part (set, loc, decl, offset); 839169689Skan} 840169689Skan 841169689Skan/* Delete current content of register LOC in dataflow set SET and set 842169689Skan the register to contain REG_EXPR (LOC), REG_OFFSET (LOC). If 843169689Skan MODIFY is true, any other live copies of the same variable part are 844169689Skan also deleted from the dataflow set, otherwise the variable part is 845169689Skan assumed to be copied from another location holding the same 846169689Skan part. */ 847169689Skan 848169689Skanstatic void 849169689Skanvar_reg_delete_and_set (dataflow_set *set, rtx loc, bool modify) 850169689Skan{ 851169689Skan tree decl = REG_EXPR (loc); 852169689Skan HOST_WIDE_INT offset = REG_OFFSET (loc); 853169689Skan attrs node, next; 854169689Skan attrs *nextp; 855169689Skan 856169689Skan decl = var_debug_decl (decl); 857169689Skan 858169689Skan nextp = &set->regs[REGNO (loc)]; 859169689Skan for (node = *nextp; node; node = next) 860169689Skan { 861169689Skan next = node->next; 862169689Skan if (node->decl != decl || node->offset != offset) 863169689Skan { 864169689Skan delete_variable_part (set, node->loc, node->decl, node->offset); 865169689Skan pool_free (attrs_pool, node); 866169689Skan *nextp = next; 867169689Skan } 868169689Skan else 869169689Skan { 870169689Skan node->loc = loc; 871169689Skan nextp = &node->next; 872169689Skan } 873169689Skan } 874169689Skan if (modify) 875169689Skan clobber_variable_part (set, loc, decl, offset); 876169689Skan var_reg_set (set, loc); 877169689Skan} 878169689Skan 879169689Skan/* Delete current content of register LOC in dataflow set SET. If 880169689Skan CLOBBER is true, also delete any other live copies of the same 881169689Skan variable part. */ 882169689Skan 883169689Skanstatic void 884169689Skanvar_reg_delete (dataflow_set *set, rtx loc, bool clobber) 885169689Skan{ 886169689Skan attrs *reg = &set->regs[REGNO (loc)]; 887169689Skan attrs node, next; 888169689Skan 889169689Skan if (clobber) 890169689Skan { 891169689Skan tree decl = REG_EXPR (loc); 892169689Skan HOST_WIDE_INT offset = REG_OFFSET (loc); 893169689Skan 894169689Skan decl = var_debug_decl (decl); 895169689Skan 896169689Skan clobber_variable_part (set, NULL, decl, offset); 897169689Skan } 898169689Skan 899169689Skan for (node = *reg; node; node = next) 900169689Skan { 901169689Skan next = node->next; 902169689Skan delete_variable_part (set, node->loc, node->decl, node->offset); 903169689Skan pool_free (attrs_pool, node); 904169689Skan } 905169689Skan *reg = NULL; 906169689Skan} 907169689Skan 908169689Skan/* Delete content of register with number REGNO in dataflow set SET. */ 909169689Skan 910169689Skanstatic void 911169689Skanvar_regno_delete (dataflow_set *set, int regno) 912169689Skan{ 913169689Skan attrs *reg = &set->regs[regno]; 914169689Skan attrs node, next; 915169689Skan 916169689Skan for (node = *reg; node; node = next) 917169689Skan { 918169689Skan next = node->next; 919169689Skan delete_variable_part (set, node->loc, node->decl, node->offset); 920169689Skan pool_free (attrs_pool, node); 921169689Skan } 922169689Skan *reg = NULL; 923169689Skan} 924169689Skan 925169689Skan/* Set the location part of variable MEM_EXPR (LOC) in dataflow set 926169689Skan SET to LOC. 927169689Skan Adjust the address first if it is stack pointer based. */ 928169689Skan 929169689Skanstatic void 930169689Skanvar_mem_set (dataflow_set *set, rtx loc) 931169689Skan{ 932169689Skan tree decl = MEM_EXPR (loc); 933235623Spfg HOST_WIDE_INT offset = INT_MEM_OFFSET (loc); 934169689Skan 935169689Skan decl = var_debug_decl (decl); 936169689Skan 937169689Skan set_variable_part (set, loc, decl, offset); 938169689Skan} 939169689Skan 940169689Skan/* Delete and set the location part of variable MEM_EXPR (LOC) in 941169689Skan dataflow set SET to LOC. If MODIFY is true, any other live copies 942169689Skan of the same variable part are also deleted from the dataflow set, 943169689Skan otherwise the variable part is assumed to be copied from another 944169689Skan location holding the same part. 945169689Skan Adjust the address first if it is stack pointer based. */ 946169689Skan 947169689Skanstatic void 948169689Skanvar_mem_delete_and_set (dataflow_set *set, rtx loc, bool modify) 949169689Skan{ 950169689Skan tree decl = MEM_EXPR (loc); 951235623Spfg HOST_WIDE_INT offset = INT_MEM_OFFSET (loc); 952169689Skan 953169689Skan decl = var_debug_decl (decl); 954169689Skan 955169689Skan if (modify) 956169689Skan clobber_variable_part (set, NULL, decl, offset); 957169689Skan var_mem_set (set, loc); 958169689Skan} 959169689Skan 960169689Skan/* Delete the location part LOC from dataflow set SET. If CLOBBER is 961169689Skan true, also delete any other live copies of the same variable part. 962169689Skan Adjust the address first if it is stack pointer based. */ 963169689Skan 964169689Skanstatic void 965169689Skanvar_mem_delete (dataflow_set *set, rtx loc, bool clobber) 966169689Skan{ 967169689Skan tree decl = MEM_EXPR (loc); 968235623Spfg HOST_WIDE_INT offset = INT_MEM_OFFSET (loc); 969169689Skan 970169689Skan decl = var_debug_decl (decl); 971169689Skan if (clobber) 972169689Skan clobber_variable_part (set, NULL, decl, offset); 973169689Skan delete_variable_part (set, loc, decl, offset); 974169689Skan} 975169689Skan 976169689Skan/* Initialize dataflow set SET to be empty. 977169689Skan VARS_SIZE is the initial size of hash table VARS. */ 978169689Skan 979169689Skanstatic void 980169689Skandataflow_set_init (dataflow_set *set, int vars_size) 981169689Skan{ 982169689Skan init_attrs_list_set (set->regs); 983169689Skan set->vars = htab_create (vars_size, variable_htab_hash, variable_htab_eq, 984169689Skan variable_htab_free); 985169689Skan set->stack_adjust = 0; 986169689Skan} 987169689Skan 988169689Skan/* Delete the contents of dataflow set SET. */ 989169689Skan 990169689Skanstatic void 991169689Skandataflow_set_clear (dataflow_set *set) 992169689Skan{ 993169689Skan int i; 994169689Skan 995169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 996169689Skan attrs_list_clear (&set->regs[i]); 997169689Skan 998169689Skan vars_clear (set->vars); 999169689Skan} 1000169689Skan 1001169689Skan/* Copy the contents of dataflow set SRC to DST. */ 1002169689Skan 1003169689Skanstatic void 1004169689Skandataflow_set_copy (dataflow_set *dst, dataflow_set *src) 1005169689Skan{ 1006169689Skan int i; 1007169689Skan 1008169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1009169689Skan attrs_list_copy (&dst->regs[i], src->regs[i]); 1010169689Skan 1011169689Skan vars_copy (dst->vars, src->vars); 1012169689Skan dst->stack_adjust = src->stack_adjust; 1013169689Skan} 1014169689Skan 1015169689Skan/* Information for merging lists of locations for a given offset of variable. 1016169689Skan */ 1017169689Skanstruct variable_union_info 1018169689Skan{ 1019169689Skan /* Node of the location chain. */ 1020169689Skan location_chain lc; 1021169689Skan 1022169689Skan /* The sum of positions in the input chains. */ 1023169689Skan int pos; 1024169689Skan 1025169689Skan /* The position in the chains of SRC and DST dataflow sets. */ 1026169689Skan int pos_src; 1027169689Skan int pos_dst; 1028169689Skan}; 1029169689Skan 1030169689Skan/* Compare function for qsort, order the structures by POS element. */ 1031169689Skan 1032169689Skanstatic int 1033169689Skanvariable_union_info_cmp_pos (const void *n1, const void *n2) 1034169689Skan{ 1035169689Skan const struct variable_union_info *i1 = n1; 1036169689Skan const struct variable_union_info *i2 = n2; 1037169689Skan 1038169689Skan if (i1->pos != i2->pos) 1039169689Skan return i1->pos - i2->pos; 1040169689Skan 1041169689Skan return (i1->pos_dst - i2->pos_dst); 1042169689Skan} 1043169689Skan 1044169689Skan/* Compute union of location parts of variable *SLOT and the same variable 1045169689Skan from hash table DATA. Compute "sorted" union of the location chains 1046169689Skan for common offsets, i.e. the locations of a variable part are sorted by 1047169689Skan a priority where the priority is the sum of the positions in the 2 chains 1048169689Skan (if a location is only in one list the position in the second list is 1049169689Skan defined to be larger than the length of the chains). 1050169689Skan When we are updating the location parts the newest location is in the 1051169689Skan beginning of the chain, so when we do the described "sorted" union 1052169689Skan we keep the newest locations in the beginning. */ 1053169689Skan 1054169689Skanstatic int 1055169689Skanvariable_union (void **slot, void *data) 1056169689Skan{ 1057169689Skan variable src, dst, *dstp; 1058169689Skan dataflow_set *set = (dataflow_set *) data; 1059169689Skan int i, j, k; 1060169689Skan 1061169689Skan src = *(variable *) slot; 1062169689Skan dstp = (variable *) htab_find_slot_with_hash (set->vars, src->decl, 1063169689Skan VARIABLE_HASH_VAL (src->decl), 1064169689Skan INSERT); 1065169689Skan if (!*dstp) 1066169689Skan { 1067169689Skan src->refcount++; 1068169689Skan 1069169689Skan /* If CUR_LOC of some variable part is not the first element of 1070169689Skan the location chain we are going to change it so we have to make 1071169689Skan a copy of the variable. */ 1072169689Skan for (k = 0; k < src->n_var_parts; k++) 1073169689Skan { 1074169689Skan gcc_assert (!src->var_part[k].loc_chain 1075169689Skan == !src->var_part[k].cur_loc); 1076169689Skan if (src->var_part[k].loc_chain) 1077169689Skan { 1078169689Skan gcc_assert (src->var_part[k].cur_loc); 1079169689Skan if (src->var_part[k].cur_loc != src->var_part[k].loc_chain->loc) 1080169689Skan break; 1081169689Skan } 1082169689Skan } 1083169689Skan if (k < src->n_var_parts) 1084169689Skan unshare_variable (set, src); 1085169689Skan else 1086169689Skan *dstp = src; 1087169689Skan 1088169689Skan /* Continue traversing the hash table. */ 1089169689Skan return 1; 1090169689Skan } 1091169689Skan else 1092169689Skan dst = *dstp; 1093169689Skan 1094169689Skan gcc_assert (src->n_var_parts); 1095169689Skan 1096169689Skan /* Count the number of location parts, result is K. */ 1097169689Skan for (i = 0, j = 0, k = 0; 1098169689Skan i < src->n_var_parts && j < dst->n_var_parts; k++) 1099169689Skan { 1100169689Skan if (src->var_part[i].offset == dst->var_part[j].offset) 1101169689Skan { 1102169689Skan i++; 1103169689Skan j++; 1104169689Skan } 1105169689Skan else if (src->var_part[i].offset < dst->var_part[j].offset) 1106169689Skan i++; 1107169689Skan else 1108169689Skan j++; 1109169689Skan } 1110169689Skan k += src->n_var_parts - i; 1111169689Skan k += dst->n_var_parts - j; 1112169689Skan 1113169689Skan /* We track only variables whose size is <= MAX_VAR_PARTS bytes 1114169689Skan thus there are at most MAX_VAR_PARTS different offsets. */ 1115169689Skan gcc_assert (k <= MAX_VAR_PARTS); 1116169689Skan 1117169689Skan if (dst->refcount > 1 && dst->n_var_parts != k) 1118169689Skan dst = unshare_variable (set, dst); 1119169689Skan 1120169689Skan i = src->n_var_parts - 1; 1121169689Skan j = dst->n_var_parts - 1; 1122169689Skan dst->n_var_parts = k; 1123169689Skan 1124169689Skan for (k--; k >= 0; k--) 1125169689Skan { 1126169689Skan location_chain node, node2; 1127169689Skan 1128169689Skan if (i >= 0 && j >= 0 1129169689Skan && src->var_part[i].offset == dst->var_part[j].offset) 1130169689Skan { 1131169689Skan /* Compute the "sorted" union of the chains, i.e. the locations which 1132169689Skan are in both chains go first, they are sorted by the sum of 1133169689Skan positions in the chains. */ 1134169689Skan int dst_l, src_l; 1135169689Skan int ii, jj, n; 1136169689Skan struct variable_union_info *vui; 1137169689Skan 1138169689Skan /* If DST is shared compare the location chains. 1139169689Skan If they are different we will modify the chain in DST with 1140169689Skan high probability so make a copy of DST. */ 1141169689Skan if (dst->refcount > 1) 1142169689Skan { 1143169689Skan for (node = src->var_part[i].loc_chain, 1144169689Skan node2 = dst->var_part[j].loc_chain; node && node2; 1145169689Skan node = node->next, node2 = node2->next) 1146169689Skan { 1147169689Skan if (!((REG_P (node2->loc) 1148169689Skan && REG_P (node->loc) 1149169689Skan && REGNO (node2->loc) == REGNO (node->loc)) 1150169689Skan || rtx_equal_p (node2->loc, node->loc))) 1151169689Skan break; 1152169689Skan } 1153169689Skan if (node || node2) 1154169689Skan dst = unshare_variable (set, dst); 1155169689Skan } 1156169689Skan 1157169689Skan src_l = 0; 1158169689Skan for (node = src->var_part[i].loc_chain; node; node = node->next) 1159169689Skan src_l++; 1160169689Skan dst_l = 0; 1161169689Skan for (node = dst->var_part[j].loc_chain; node; node = node->next) 1162169689Skan dst_l++; 1163169689Skan vui = XCNEWVEC (struct variable_union_info, src_l + dst_l); 1164169689Skan 1165169689Skan /* Fill in the locations from DST. */ 1166169689Skan for (node = dst->var_part[j].loc_chain, jj = 0; node; 1167169689Skan node = node->next, jj++) 1168169689Skan { 1169169689Skan vui[jj].lc = node; 1170169689Skan vui[jj].pos_dst = jj; 1171169689Skan 1172169689Skan /* Value larger than a sum of 2 valid positions. */ 1173169689Skan vui[jj].pos_src = src_l + dst_l; 1174169689Skan } 1175169689Skan 1176169689Skan /* Fill in the locations from SRC. */ 1177169689Skan n = dst_l; 1178169689Skan for (node = src->var_part[i].loc_chain, ii = 0; node; 1179169689Skan node = node->next, ii++) 1180169689Skan { 1181169689Skan /* Find location from NODE. */ 1182169689Skan for (jj = 0; jj < dst_l; jj++) 1183169689Skan { 1184169689Skan if ((REG_P (vui[jj].lc->loc) 1185169689Skan && REG_P (node->loc) 1186169689Skan && REGNO (vui[jj].lc->loc) == REGNO (node->loc)) 1187169689Skan || rtx_equal_p (vui[jj].lc->loc, node->loc)) 1188169689Skan { 1189169689Skan vui[jj].pos_src = ii; 1190169689Skan break; 1191169689Skan } 1192169689Skan } 1193169689Skan if (jj >= dst_l) /* The location has not been found. */ 1194169689Skan { 1195169689Skan location_chain new_node; 1196169689Skan 1197169689Skan /* Copy the location from SRC. */ 1198169689Skan new_node = pool_alloc (loc_chain_pool); 1199169689Skan new_node->loc = node->loc; 1200169689Skan vui[n].lc = new_node; 1201169689Skan vui[n].pos_src = ii; 1202169689Skan vui[n].pos_dst = src_l + dst_l; 1203169689Skan n++; 1204169689Skan } 1205169689Skan } 1206169689Skan 1207169689Skan for (ii = 0; ii < src_l + dst_l; ii++) 1208169689Skan vui[ii].pos = vui[ii].pos_src + vui[ii].pos_dst; 1209169689Skan 1210169689Skan qsort (vui, n, sizeof (struct variable_union_info), 1211169689Skan variable_union_info_cmp_pos); 1212169689Skan 1213169689Skan /* Reconnect the nodes in sorted order. */ 1214169689Skan for (ii = 1; ii < n; ii++) 1215169689Skan vui[ii - 1].lc->next = vui[ii].lc; 1216169689Skan vui[n - 1].lc->next = NULL; 1217169689Skan 1218169689Skan dst->var_part[k].loc_chain = vui[0].lc; 1219169689Skan dst->var_part[k].offset = dst->var_part[j].offset; 1220169689Skan 1221169689Skan free (vui); 1222169689Skan i--; 1223169689Skan j--; 1224169689Skan } 1225169689Skan else if ((i >= 0 && j >= 0 1226169689Skan && src->var_part[i].offset < dst->var_part[j].offset) 1227169689Skan || i < 0) 1228169689Skan { 1229169689Skan dst->var_part[k] = dst->var_part[j]; 1230169689Skan j--; 1231169689Skan } 1232169689Skan else if ((i >= 0 && j >= 0 1233169689Skan && src->var_part[i].offset > dst->var_part[j].offset) 1234169689Skan || j < 0) 1235169689Skan { 1236169689Skan location_chain *nextp; 1237169689Skan 1238169689Skan /* Copy the chain from SRC. */ 1239169689Skan nextp = &dst->var_part[k].loc_chain; 1240169689Skan for (node = src->var_part[i].loc_chain; node; node = node->next) 1241169689Skan { 1242169689Skan location_chain new_lc; 1243169689Skan 1244169689Skan new_lc = pool_alloc (loc_chain_pool); 1245169689Skan new_lc->next = NULL; 1246169689Skan new_lc->loc = node->loc; 1247169689Skan 1248169689Skan *nextp = new_lc; 1249169689Skan nextp = &new_lc->next; 1250169689Skan } 1251169689Skan 1252169689Skan dst->var_part[k].offset = src->var_part[i].offset; 1253169689Skan i--; 1254169689Skan } 1255169689Skan 1256169689Skan /* We are at the basic block boundary when computing union 1257169689Skan so set the CUR_LOC to be the first element of the chain. */ 1258169689Skan if (dst->var_part[k].loc_chain) 1259169689Skan dst->var_part[k].cur_loc = dst->var_part[k].loc_chain->loc; 1260169689Skan else 1261169689Skan dst->var_part[k].cur_loc = NULL; 1262169689Skan } 1263169689Skan 1264169689Skan /* Continue traversing the hash table. */ 1265169689Skan return 1; 1266169689Skan} 1267169689Skan 1268169689Skan/* Compute union of dataflow sets SRC and DST and store it to DST. */ 1269169689Skan 1270169689Skanstatic void 1271169689Skandataflow_set_union (dataflow_set *dst, dataflow_set *src) 1272169689Skan{ 1273169689Skan int i; 1274169689Skan 1275169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1276169689Skan attrs_list_union (&dst->regs[i], src->regs[i]); 1277169689Skan 1278169689Skan htab_traverse (src->vars, variable_union, dst); 1279169689Skan} 1280169689Skan 1281169689Skan/* Flag whether two dataflow sets being compared contain different data. */ 1282169689Skanstatic bool 1283169689Skandataflow_set_different_value; 1284169689Skan 1285169689Skanstatic bool 1286169689Skanvariable_part_different_p (variable_part *vp1, variable_part *vp2) 1287169689Skan{ 1288169689Skan location_chain lc1, lc2; 1289169689Skan 1290169689Skan for (lc1 = vp1->loc_chain; lc1; lc1 = lc1->next) 1291169689Skan { 1292169689Skan for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next) 1293169689Skan { 1294169689Skan if (REG_P (lc1->loc) && REG_P (lc2->loc)) 1295169689Skan { 1296169689Skan if (REGNO (lc1->loc) == REGNO (lc2->loc)) 1297169689Skan break; 1298169689Skan } 1299169689Skan if (rtx_equal_p (lc1->loc, lc2->loc)) 1300169689Skan break; 1301169689Skan } 1302169689Skan if (!lc2) 1303169689Skan return true; 1304169689Skan } 1305169689Skan return false; 1306169689Skan} 1307169689Skan 1308169689Skan/* Return true if variables VAR1 and VAR2 are different. 1309169689Skan If COMPARE_CURRENT_LOCATION is true compare also the cur_loc of each 1310169689Skan variable part. */ 1311169689Skan 1312169689Skanstatic bool 1313169689Skanvariable_different_p (variable var1, variable var2, 1314169689Skan bool compare_current_location) 1315169689Skan{ 1316169689Skan int i; 1317169689Skan 1318169689Skan if (var1 == var2) 1319169689Skan return false; 1320169689Skan 1321169689Skan if (var1->n_var_parts != var2->n_var_parts) 1322169689Skan return true; 1323169689Skan 1324169689Skan for (i = 0; i < var1->n_var_parts; i++) 1325169689Skan { 1326169689Skan if (var1->var_part[i].offset != var2->var_part[i].offset) 1327169689Skan return true; 1328169689Skan if (compare_current_location) 1329169689Skan { 1330169689Skan if (!((REG_P (var1->var_part[i].cur_loc) 1331169689Skan && REG_P (var2->var_part[i].cur_loc) 1332169689Skan && (REGNO (var1->var_part[i].cur_loc) 1333169689Skan == REGNO (var2->var_part[i].cur_loc))) 1334169689Skan || rtx_equal_p (var1->var_part[i].cur_loc, 1335169689Skan var2->var_part[i].cur_loc))) 1336169689Skan return true; 1337169689Skan } 1338169689Skan if (variable_part_different_p (&var1->var_part[i], &var2->var_part[i])) 1339169689Skan return true; 1340169689Skan if (variable_part_different_p (&var2->var_part[i], &var1->var_part[i])) 1341169689Skan return true; 1342169689Skan } 1343169689Skan return false; 1344169689Skan} 1345169689Skan 1346169689Skan/* Compare variable *SLOT with the same variable in hash table DATA 1347169689Skan and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */ 1348169689Skan 1349169689Skanstatic int 1350169689Skandataflow_set_different_1 (void **slot, void *data) 1351169689Skan{ 1352169689Skan htab_t htab = (htab_t) data; 1353169689Skan variable var1, var2; 1354169689Skan 1355169689Skan var1 = *(variable *) slot; 1356169689Skan var2 = htab_find_with_hash (htab, var1->decl, 1357169689Skan VARIABLE_HASH_VAL (var1->decl)); 1358169689Skan if (!var2) 1359169689Skan { 1360169689Skan dataflow_set_different_value = true; 1361169689Skan 1362169689Skan /* Stop traversing the hash table. */ 1363169689Skan return 0; 1364169689Skan } 1365169689Skan 1366169689Skan if (variable_different_p (var1, var2, false)) 1367169689Skan { 1368169689Skan dataflow_set_different_value = true; 1369169689Skan 1370169689Skan /* Stop traversing the hash table. */ 1371169689Skan return 0; 1372169689Skan } 1373169689Skan 1374169689Skan /* Continue traversing the hash table. */ 1375169689Skan return 1; 1376169689Skan} 1377169689Skan 1378169689Skan/* Compare variable *SLOT with the same variable in hash table DATA 1379169689Skan and set DATAFLOW_SET_DIFFERENT_VALUE if they are different. */ 1380169689Skan 1381169689Skanstatic int 1382169689Skandataflow_set_different_2 (void **slot, void *data) 1383169689Skan{ 1384169689Skan htab_t htab = (htab_t) data; 1385169689Skan variable var1, var2; 1386169689Skan 1387169689Skan var1 = *(variable *) slot; 1388169689Skan var2 = htab_find_with_hash (htab, var1->decl, 1389169689Skan VARIABLE_HASH_VAL (var1->decl)); 1390169689Skan if (!var2) 1391169689Skan { 1392169689Skan dataflow_set_different_value = true; 1393169689Skan 1394169689Skan /* Stop traversing the hash table. */ 1395169689Skan return 0; 1396169689Skan } 1397169689Skan 1398169689Skan /* If both variables are defined they have been already checked for 1399169689Skan equivalence. */ 1400169689Skan gcc_assert (!variable_different_p (var1, var2, false)); 1401169689Skan 1402169689Skan /* Continue traversing the hash table. */ 1403169689Skan return 1; 1404169689Skan} 1405169689Skan 1406169689Skan/* Return true if dataflow sets OLD_SET and NEW_SET differ. */ 1407169689Skan 1408169689Skanstatic bool 1409169689Skandataflow_set_different (dataflow_set *old_set, dataflow_set *new_set) 1410169689Skan{ 1411169689Skan dataflow_set_different_value = false; 1412169689Skan 1413169689Skan htab_traverse (old_set->vars, dataflow_set_different_1, new_set->vars); 1414169689Skan if (!dataflow_set_different_value) 1415169689Skan { 1416169689Skan /* We have compared the variables which are in both hash tables 1417169689Skan so now only check whether there are some variables in NEW_SET->VARS 1418169689Skan which are not in OLD_SET->VARS. */ 1419169689Skan htab_traverse (new_set->vars, dataflow_set_different_2, old_set->vars); 1420169689Skan } 1421169689Skan return dataflow_set_different_value; 1422169689Skan} 1423169689Skan 1424169689Skan/* Free the contents of dataflow set SET. */ 1425169689Skan 1426169689Skanstatic void 1427169689Skandataflow_set_destroy (dataflow_set *set) 1428169689Skan{ 1429169689Skan int i; 1430169689Skan 1431169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1432169689Skan attrs_list_clear (&set->regs[i]); 1433169689Skan 1434169689Skan htab_delete (set->vars); 1435169689Skan set->vars = NULL; 1436169689Skan} 1437169689Skan 1438169689Skan/* Return true if RTL X contains a SYMBOL_REF. */ 1439169689Skan 1440169689Skanstatic bool 1441169689Skancontains_symbol_ref (rtx x) 1442169689Skan{ 1443169689Skan const char *fmt; 1444169689Skan RTX_CODE code; 1445169689Skan int i; 1446169689Skan 1447169689Skan if (!x) 1448169689Skan return false; 1449169689Skan 1450169689Skan code = GET_CODE (x); 1451169689Skan if (code == SYMBOL_REF) 1452169689Skan return true; 1453169689Skan 1454169689Skan fmt = GET_RTX_FORMAT (code); 1455169689Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1456169689Skan { 1457169689Skan if (fmt[i] == 'e') 1458169689Skan { 1459169689Skan if (contains_symbol_ref (XEXP (x, i))) 1460169689Skan return true; 1461169689Skan } 1462169689Skan else if (fmt[i] == 'E') 1463169689Skan { 1464169689Skan int j; 1465169689Skan for (j = 0; j < XVECLEN (x, i); j++) 1466169689Skan if (contains_symbol_ref (XVECEXP (x, i, j))) 1467169689Skan return true; 1468169689Skan } 1469169689Skan } 1470169689Skan 1471169689Skan return false; 1472169689Skan} 1473169689Skan 1474169689Skan/* Shall EXPR be tracked? */ 1475169689Skan 1476169689Skanstatic bool 1477169689Skantrack_expr_p (tree expr) 1478169689Skan{ 1479169689Skan rtx decl_rtl; 1480169689Skan tree realdecl; 1481169689Skan 1482169689Skan /* If EXPR is not a parameter or a variable do not track it. */ 1483169689Skan if (TREE_CODE (expr) != VAR_DECL && TREE_CODE (expr) != PARM_DECL) 1484169689Skan return 0; 1485169689Skan 1486169689Skan /* It also must have a name... */ 1487169689Skan if (!DECL_NAME (expr)) 1488169689Skan return 0; 1489169689Skan 1490169689Skan /* ... and a RTL assigned to it. */ 1491169689Skan decl_rtl = DECL_RTL_IF_SET (expr); 1492169689Skan if (!decl_rtl) 1493169689Skan return 0; 1494169689Skan 1495169689Skan /* If this expression is really a debug alias of some other declaration, we 1496169689Skan don't need to track this expression if the ultimate declaration is 1497169689Skan ignored. */ 1498169689Skan realdecl = expr; 1499169689Skan if (DECL_DEBUG_EXPR_IS_FROM (realdecl) && DECL_DEBUG_EXPR (realdecl)) 1500169689Skan { 1501169689Skan realdecl = DECL_DEBUG_EXPR (realdecl); 1502169689Skan /* ??? We don't yet know how to emit DW_OP_piece for variable 1503169689Skan that has been SRA'ed. */ 1504169689Skan if (!DECL_P (realdecl)) 1505169689Skan return 0; 1506169689Skan } 1507169689Skan 1508169689Skan /* Do not track EXPR if REALDECL it should be ignored for debugging 1509169689Skan purposes. */ 1510169689Skan if (DECL_IGNORED_P (realdecl)) 1511169689Skan return 0; 1512169689Skan 1513169689Skan /* Do not track global variables until we are able to emit correct location 1514169689Skan list for them. */ 1515169689Skan if (TREE_STATIC (realdecl)) 1516169689Skan return 0; 1517169689Skan 1518169689Skan /* When the EXPR is a DECL for alias of some variable (see example) 1519169689Skan the TREE_STATIC flag is not used. Disable tracking all DECLs whose 1520169689Skan DECL_RTL contains SYMBOL_REF. 1521169689Skan 1522169689Skan Example: 1523169689Skan extern char **_dl_argv_internal __attribute__ ((alias ("_dl_argv"))); 1524169689Skan char **_dl_argv; 1525169689Skan */ 1526169689Skan if (MEM_P (decl_rtl) 1527169689Skan && contains_symbol_ref (XEXP (decl_rtl, 0))) 1528169689Skan return 0; 1529169689Skan 1530169689Skan /* If RTX is a memory it should not be very large (because it would be 1531169689Skan an array or struct). */ 1532169689Skan if (MEM_P (decl_rtl)) 1533169689Skan { 1534169689Skan /* Do not track structures and arrays. */ 1535169689Skan if (GET_MODE (decl_rtl) == BLKmode 1536169689Skan || AGGREGATE_TYPE_P (TREE_TYPE (realdecl))) 1537169689Skan return 0; 1538169689Skan if (MEM_SIZE (decl_rtl) 1539169689Skan && INTVAL (MEM_SIZE (decl_rtl)) > MAX_VAR_PARTS) 1540169689Skan return 0; 1541169689Skan } 1542169689Skan 1543169689Skan return 1; 1544169689Skan} 1545169689Skan 1546235623Spfg/* Return true if OFFSET is a valid offset for a register or memory 1547235623Spfg access we want to track. This is used to reject out-of-bounds 1548235623Spfg accesses that can cause assertions to fail later. Note that we 1549235623Spfg don't reject negative offsets because they can be generated for 1550235623Spfg paradoxical subregs on big-endian architectures. */ 1551235623Spfg 1552235623Spfgstatic inline bool 1553235623Spfgoffset_valid_for_tracked_p (HOST_WIDE_INT offset) 1554235623Spfg{ 1555235623Spfg return (-MAX_VAR_PARTS < offset) && (offset < MAX_VAR_PARTS); 1556235623Spfg} 1557235623Spfg 1558169689Skan/* Determine whether a given LOC refers to the same variable part as 1559169689Skan EXPR+OFFSET. */ 1560169689Skan 1561169689Skanstatic bool 1562169689Skansame_variable_part_p (rtx loc, tree expr, HOST_WIDE_INT offset) 1563169689Skan{ 1564169689Skan tree expr2; 1565169689Skan HOST_WIDE_INT offset2; 1566169689Skan 1567169689Skan if (! DECL_P (expr)) 1568169689Skan return false; 1569169689Skan 1570169689Skan if (REG_P (loc)) 1571169689Skan { 1572169689Skan expr2 = REG_EXPR (loc); 1573169689Skan offset2 = REG_OFFSET (loc); 1574169689Skan } 1575169689Skan else if (MEM_P (loc)) 1576169689Skan { 1577169689Skan expr2 = MEM_EXPR (loc); 1578235623Spfg offset2 = INT_MEM_OFFSET (loc); 1579169689Skan } 1580169689Skan else 1581169689Skan return false; 1582169689Skan 1583169689Skan if (! expr2 || ! DECL_P (expr2)) 1584169689Skan return false; 1585169689Skan 1586169689Skan expr = var_debug_decl (expr); 1587169689Skan expr2 = var_debug_decl (expr2); 1588169689Skan 1589169689Skan return (expr == expr2 && offset == offset2); 1590169689Skan} 1591169689Skan 1592169689Skan 1593169689Skan/* Count uses (register and memory references) LOC which will be tracked. 1594169689Skan INSN is instruction which the LOC is part of. */ 1595169689Skan 1596169689Skanstatic int 1597169689Skancount_uses (rtx *loc, void *insn) 1598169689Skan{ 1599169689Skan basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1600169689Skan 1601169689Skan if (REG_P (*loc)) 1602169689Skan { 1603169689Skan gcc_assert (REGNO (*loc) < FIRST_PSEUDO_REGISTER); 1604169689Skan VTI (bb)->n_mos++; 1605169689Skan } 1606169689Skan else if (MEM_P (*loc) 1607169689Skan && MEM_EXPR (*loc) 1608235623Spfg && track_expr_p (MEM_EXPR (*loc)) 1609235623Spfg && offset_valid_for_tracked_p (INT_MEM_OFFSET (*loc))) 1610169689Skan { 1611169689Skan VTI (bb)->n_mos++; 1612169689Skan } 1613169689Skan 1614169689Skan return 0; 1615169689Skan} 1616169689Skan 1617169689Skan/* Helper function for finding all uses of REG/MEM in X in insn INSN. */ 1618169689Skan 1619169689Skanstatic void 1620169689Skancount_uses_1 (rtx *x, void *insn) 1621169689Skan{ 1622169689Skan for_each_rtx (x, count_uses, insn); 1623169689Skan} 1624169689Skan 1625169689Skan/* Count stores (register and memory references) LOC which will be tracked. 1626169689Skan INSN is instruction which the LOC is part of. */ 1627169689Skan 1628169689Skanstatic void 1629169689Skancount_stores (rtx loc, rtx expr ATTRIBUTE_UNUSED, void *insn) 1630169689Skan{ 1631169689Skan count_uses (&loc, insn); 1632169689Skan} 1633169689Skan 1634169689Skan/* Add uses (register and memory references) LOC which will be tracked 1635169689Skan to VTI (bb)->mos. INSN is instruction which the LOC is part of. */ 1636169689Skan 1637169689Skanstatic int 1638169689Skanadd_uses (rtx *loc, void *insn) 1639169689Skan{ 1640169689Skan if (REG_P (*loc)) 1641169689Skan { 1642169689Skan basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1643169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1644169689Skan 1645235623Spfg if (REG_EXPR (*loc) 1646235623Spfg && track_expr_p (REG_EXPR (*loc)) 1647235623Spfg && offset_valid_for_tracked_p (REG_OFFSET (*loc))) 1648235623Spfg mo->type = MO_USE; 1649235623Spfg else 1650235623Spfg mo->type = MO_USE_NO_VAR; 1651169689Skan mo->u.loc = *loc; 1652169689Skan mo->insn = (rtx) insn; 1653169689Skan } 1654169689Skan else if (MEM_P (*loc) 1655169689Skan && MEM_EXPR (*loc) 1656235623Spfg && track_expr_p (MEM_EXPR (*loc)) 1657235623Spfg && offset_valid_for_tracked_p (INT_MEM_OFFSET (*loc))) 1658169689Skan { 1659169689Skan basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1660169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1661169689Skan 1662169689Skan mo->type = MO_USE; 1663169689Skan mo->u.loc = *loc; 1664169689Skan mo->insn = (rtx) insn; 1665169689Skan } 1666169689Skan 1667169689Skan return 0; 1668169689Skan} 1669169689Skan 1670169689Skan/* Helper function for finding all uses of REG/MEM in X in insn INSN. */ 1671169689Skan 1672169689Skanstatic void 1673169689Skanadd_uses_1 (rtx *x, void *insn) 1674169689Skan{ 1675169689Skan for_each_rtx (x, add_uses, insn); 1676169689Skan} 1677169689Skan 1678169689Skan/* Add stores (register and memory references) LOC which will be tracked 1679169689Skan to VTI (bb)->mos. EXPR is the RTL expression containing the store. 1680169689Skan INSN is instruction which the LOC is part of. */ 1681169689Skan 1682169689Skanstatic void 1683169689Skanadd_stores (rtx loc, rtx expr, void *insn) 1684169689Skan{ 1685169689Skan if (REG_P (loc)) 1686169689Skan { 1687169689Skan basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1688169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1689169689Skan 1690169689Skan if (GET_CODE (expr) == CLOBBER 1691235623Spfg || !(REG_EXPR (loc) 1692235623Spfg && track_expr_p (REG_EXPR (loc)) 1693235623Spfg && offset_valid_for_tracked_p (REG_OFFSET (loc)))) 1694169689Skan mo->type = MO_CLOBBER; 1695169689Skan else if (GET_CODE (expr) == SET 1696169689Skan && SET_DEST (expr) == loc 1697169689Skan && same_variable_part_p (SET_SRC (expr), 1698169689Skan REG_EXPR (loc), 1699169689Skan REG_OFFSET (loc))) 1700169689Skan mo->type = MO_COPY; 1701169689Skan else 1702169689Skan mo->type = MO_SET; 1703169689Skan mo->u.loc = loc; 1704169689Skan mo->insn = NEXT_INSN ((rtx) insn); 1705169689Skan } 1706169689Skan else if (MEM_P (loc) 1707169689Skan && MEM_EXPR (loc) 1708235623Spfg && track_expr_p (MEM_EXPR (loc)) 1709235623Spfg && offset_valid_for_tracked_p (INT_MEM_OFFSET (loc))) 1710169689Skan { 1711169689Skan basic_block bb = BLOCK_FOR_INSN ((rtx) insn); 1712169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 1713169689Skan 1714169689Skan if (GET_CODE (expr) == CLOBBER) 1715169689Skan mo->type = MO_CLOBBER; 1716169689Skan else if (GET_CODE (expr) == SET 1717169689Skan && SET_DEST (expr) == loc 1718169689Skan && same_variable_part_p (SET_SRC (expr), 1719169689Skan MEM_EXPR (loc), 1720235623Spfg INT_MEM_OFFSET (loc))) 1721169689Skan mo->type = MO_COPY; 1722169689Skan else 1723169689Skan mo->type = MO_SET; 1724169689Skan mo->u.loc = loc; 1725169689Skan mo->insn = NEXT_INSN ((rtx) insn); 1726169689Skan } 1727169689Skan} 1728169689Skan 1729169689Skan/* Compute the changes of variable locations in the basic block BB. */ 1730169689Skan 1731169689Skanstatic bool 1732169689Skancompute_bb_dataflow (basic_block bb) 1733169689Skan{ 1734169689Skan int i, n, r; 1735169689Skan bool changed; 1736169689Skan dataflow_set old_out; 1737169689Skan dataflow_set *in = &VTI (bb)->in; 1738169689Skan dataflow_set *out = &VTI (bb)->out; 1739169689Skan 1740169689Skan dataflow_set_init (&old_out, htab_elements (VTI (bb)->out.vars) + 3); 1741169689Skan dataflow_set_copy (&old_out, out); 1742169689Skan dataflow_set_copy (out, in); 1743169689Skan 1744169689Skan n = VTI (bb)->n_mos; 1745169689Skan for (i = 0; i < n; i++) 1746169689Skan { 1747169689Skan switch (VTI (bb)->mos[i].type) 1748169689Skan { 1749169689Skan case MO_CALL: 1750169689Skan for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) 1751169689Skan if (TEST_HARD_REG_BIT (call_used_reg_set, r)) 1752169689Skan var_regno_delete (out, r); 1753169689Skan break; 1754169689Skan 1755169689Skan case MO_USE: 1756169689Skan { 1757169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 1758169689Skan 1759169689Skan if (GET_CODE (loc) == REG) 1760169689Skan var_reg_set (out, loc); 1761169689Skan else if (GET_CODE (loc) == MEM) 1762169689Skan var_mem_set (out, loc); 1763169689Skan } 1764169689Skan break; 1765169689Skan 1766169689Skan case MO_SET: 1767169689Skan { 1768169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 1769169689Skan 1770169689Skan if (REG_P (loc)) 1771169689Skan var_reg_delete_and_set (out, loc, true); 1772169689Skan else if (MEM_P (loc)) 1773169689Skan var_mem_delete_and_set (out, loc, true); 1774169689Skan } 1775169689Skan break; 1776169689Skan 1777169689Skan case MO_COPY: 1778169689Skan { 1779169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 1780169689Skan 1781169689Skan if (REG_P (loc)) 1782169689Skan var_reg_delete_and_set (out, loc, false); 1783169689Skan else if (MEM_P (loc)) 1784169689Skan var_mem_delete_and_set (out, loc, false); 1785169689Skan } 1786169689Skan break; 1787169689Skan 1788169689Skan case MO_USE_NO_VAR: 1789169689Skan { 1790169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 1791169689Skan 1792169689Skan if (REG_P (loc)) 1793169689Skan var_reg_delete (out, loc, false); 1794169689Skan else if (MEM_P (loc)) 1795169689Skan var_mem_delete (out, loc, false); 1796169689Skan } 1797169689Skan break; 1798169689Skan 1799169689Skan case MO_CLOBBER: 1800169689Skan { 1801169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 1802169689Skan 1803169689Skan if (REG_P (loc)) 1804169689Skan var_reg_delete (out, loc, true); 1805169689Skan else if (MEM_P (loc)) 1806169689Skan var_mem_delete (out, loc, true); 1807169689Skan } 1808169689Skan break; 1809169689Skan 1810169689Skan case MO_ADJUST: 1811169689Skan out->stack_adjust += VTI (bb)->mos[i].u.adjust; 1812169689Skan break; 1813169689Skan } 1814169689Skan } 1815169689Skan 1816169689Skan changed = dataflow_set_different (&old_out, out); 1817169689Skan dataflow_set_destroy (&old_out); 1818169689Skan return changed; 1819169689Skan} 1820169689Skan 1821169689Skan/* Find the locations of variables in the whole function. */ 1822169689Skan 1823169689Skanstatic void 1824169689Skanvt_find_locations (void) 1825169689Skan{ 1826169689Skan fibheap_t worklist, pending, fibheap_swap; 1827169689Skan sbitmap visited, in_worklist, in_pending, sbitmap_swap; 1828169689Skan basic_block bb; 1829169689Skan edge e; 1830169689Skan int *bb_order; 1831169689Skan int *rc_order; 1832169689Skan int i; 1833169689Skan 1834169689Skan /* Compute reverse completion order of depth first search of the CFG 1835169689Skan so that the data-flow runs faster. */ 1836169689Skan rc_order = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS); 1837169689Skan bb_order = XNEWVEC (int, last_basic_block); 1838169689Skan pre_and_rev_post_order_compute (NULL, rc_order, false); 1839169689Skan for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++) 1840169689Skan bb_order[rc_order[i]] = i; 1841169689Skan free (rc_order); 1842169689Skan 1843169689Skan worklist = fibheap_new (); 1844169689Skan pending = fibheap_new (); 1845169689Skan visited = sbitmap_alloc (last_basic_block); 1846169689Skan in_worklist = sbitmap_alloc (last_basic_block); 1847169689Skan in_pending = sbitmap_alloc (last_basic_block); 1848169689Skan sbitmap_zero (in_worklist); 1849169689Skan 1850169689Skan FOR_EACH_BB (bb) 1851169689Skan fibheap_insert (pending, bb_order[bb->index], bb); 1852169689Skan sbitmap_ones (in_pending); 1853169689Skan 1854169689Skan while (!fibheap_empty (pending)) 1855169689Skan { 1856169689Skan fibheap_swap = pending; 1857169689Skan pending = worklist; 1858169689Skan worklist = fibheap_swap; 1859169689Skan sbitmap_swap = in_pending; 1860169689Skan in_pending = in_worklist; 1861169689Skan in_worklist = sbitmap_swap; 1862169689Skan 1863169689Skan sbitmap_zero (visited); 1864169689Skan 1865169689Skan while (!fibheap_empty (worklist)) 1866169689Skan { 1867169689Skan bb = fibheap_extract_min (worklist); 1868169689Skan RESET_BIT (in_worklist, bb->index); 1869169689Skan if (!TEST_BIT (visited, bb->index)) 1870169689Skan { 1871169689Skan bool changed; 1872169689Skan edge_iterator ei; 1873169689Skan 1874169689Skan SET_BIT (visited, bb->index); 1875169689Skan 1876169689Skan /* Calculate the IN set as union of predecessor OUT sets. */ 1877169689Skan dataflow_set_clear (&VTI (bb)->in); 1878169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1879169689Skan { 1880169689Skan dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out); 1881169689Skan } 1882169689Skan 1883169689Skan changed = compute_bb_dataflow (bb); 1884169689Skan if (changed) 1885169689Skan { 1886169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1887169689Skan { 1888169689Skan if (e->dest == EXIT_BLOCK_PTR) 1889169689Skan continue; 1890169689Skan 1891169689Skan if (e->dest == bb) 1892169689Skan continue; 1893169689Skan 1894169689Skan if (TEST_BIT (visited, e->dest->index)) 1895169689Skan { 1896169689Skan if (!TEST_BIT (in_pending, e->dest->index)) 1897169689Skan { 1898169689Skan /* Send E->DEST to next round. */ 1899169689Skan SET_BIT (in_pending, e->dest->index); 1900169689Skan fibheap_insert (pending, 1901169689Skan bb_order[e->dest->index], 1902169689Skan e->dest); 1903169689Skan } 1904169689Skan } 1905169689Skan else if (!TEST_BIT (in_worklist, e->dest->index)) 1906169689Skan { 1907169689Skan /* Add E->DEST to current round. */ 1908169689Skan SET_BIT (in_worklist, e->dest->index); 1909169689Skan fibheap_insert (worklist, bb_order[e->dest->index], 1910169689Skan e->dest); 1911169689Skan } 1912169689Skan } 1913169689Skan } 1914169689Skan } 1915169689Skan } 1916169689Skan } 1917169689Skan 1918169689Skan free (bb_order); 1919169689Skan fibheap_delete (worklist); 1920169689Skan fibheap_delete (pending); 1921169689Skan sbitmap_free (visited); 1922169689Skan sbitmap_free (in_worklist); 1923169689Skan sbitmap_free (in_pending); 1924169689Skan} 1925169689Skan 1926169689Skan/* Print the content of the LIST to dump file. */ 1927169689Skan 1928169689Skanstatic void 1929169689Skandump_attrs_list (attrs list) 1930169689Skan{ 1931169689Skan for (; list; list = list->next) 1932169689Skan { 1933169689Skan print_mem_expr (dump_file, list->decl); 1934169689Skan fprintf (dump_file, "+" HOST_WIDE_INT_PRINT_DEC, list->offset); 1935169689Skan } 1936169689Skan fprintf (dump_file, "\n"); 1937169689Skan} 1938169689Skan 1939169689Skan/* Print the information about variable *SLOT to dump file. */ 1940169689Skan 1941169689Skanstatic int 1942169689Skandump_variable (void **slot, void *data ATTRIBUTE_UNUSED) 1943169689Skan{ 1944169689Skan variable var = *(variable *) slot; 1945169689Skan int i; 1946169689Skan location_chain node; 1947169689Skan 1948169689Skan fprintf (dump_file, " name: %s\n", 1949169689Skan IDENTIFIER_POINTER (DECL_NAME (var->decl))); 1950169689Skan for (i = 0; i < var->n_var_parts; i++) 1951169689Skan { 1952169689Skan fprintf (dump_file, " offset %ld\n", 1953169689Skan (long) var->var_part[i].offset); 1954169689Skan for (node = var->var_part[i].loc_chain; node; node = node->next) 1955169689Skan { 1956169689Skan fprintf (dump_file, " "); 1957169689Skan print_rtl_single (dump_file, node->loc); 1958169689Skan } 1959169689Skan } 1960169689Skan 1961169689Skan /* Continue traversing the hash table. */ 1962169689Skan return 1; 1963169689Skan} 1964169689Skan 1965169689Skan/* Print the information about variables from hash table VARS to dump file. */ 1966169689Skan 1967169689Skanstatic void 1968169689Skandump_vars (htab_t vars) 1969169689Skan{ 1970169689Skan if (htab_elements (vars) > 0) 1971169689Skan { 1972169689Skan fprintf (dump_file, "Variables:\n"); 1973169689Skan htab_traverse (vars, dump_variable, NULL); 1974169689Skan } 1975169689Skan} 1976169689Skan 1977169689Skan/* Print the dataflow set SET to dump file. */ 1978169689Skan 1979169689Skanstatic void 1980169689Skandump_dataflow_set (dataflow_set *set) 1981169689Skan{ 1982169689Skan int i; 1983169689Skan 1984169689Skan fprintf (dump_file, "Stack adjustment: " HOST_WIDE_INT_PRINT_DEC "\n", 1985169689Skan set->stack_adjust); 1986169689Skan for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1987169689Skan { 1988169689Skan if (set->regs[i]) 1989169689Skan { 1990169689Skan fprintf (dump_file, "Reg %d:", i); 1991169689Skan dump_attrs_list (set->regs[i]); 1992169689Skan } 1993169689Skan } 1994169689Skan dump_vars (set->vars); 1995169689Skan fprintf (dump_file, "\n"); 1996169689Skan} 1997169689Skan 1998169689Skan/* Print the IN and OUT sets for each basic block to dump file. */ 1999169689Skan 2000169689Skanstatic void 2001169689Skandump_dataflow_sets (void) 2002169689Skan{ 2003169689Skan basic_block bb; 2004169689Skan 2005169689Skan FOR_EACH_BB (bb) 2006169689Skan { 2007169689Skan fprintf (dump_file, "\nBasic block %d:\n", bb->index); 2008169689Skan fprintf (dump_file, "IN:\n"); 2009169689Skan dump_dataflow_set (&VTI (bb)->in); 2010169689Skan fprintf (dump_file, "OUT:\n"); 2011169689Skan dump_dataflow_set (&VTI (bb)->out); 2012169689Skan } 2013169689Skan} 2014169689Skan 2015169689Skan/* Add variable VAR to the hash table of changed variables and 2016169689Skan if it has no locations delete it from hash table HTAB. */ 2017169689Skan 2018169689Skanstatic void 2019169689Skanvariable_was_changed (variable var, htab_t htab) 2020169689Skan{ 2021169689Skan hashval_t hash = VARIABLE_HASH_VAL (var->decl); 2022169689Skan 2023169689Skan if (emit_notes) 2024169689Skan { 2025169689Skan variable *slot; 2026169689Skan 2027169689Skan slot = (variable *) htab_find_slot_with_hash (changed_variables, 2028169689Skan var->decl, hash, INSERT); 2029169689Skan 2030169689Skan if (htab && var->n_var_parts == 0) 2031169689Skan { 2032169689Skan variable empty_var; 2033169689Skan void **old; 2034169689Skan 2035169689Skan empty_var = pool_alloc (var_pool); 2036169689Skan empty_var->decl = var->decl; 2037169689Skan empty_var->refcount = 1; 2038169689Skan empty_var->n_var_parts = 0; 2039169689Skan *slot = empty_var; 2040169689Skan 2041169689Skan old = htab_find_slot_with_hash (htab, var->decl, hash, 2042169689Skan NO_INSERT); 2043169689Skan if (old) 2044169689Skan htab_clear_slot (htab, old); 2045169689Skan } 2046169689Skan else 2047169689Skan { 2048169689Skan *slot = var; 2049169689Skan } 2050169689Skan } 2051169689Skan else 2052169689Skan { 2053169689Skan gcc_assert (htab); 2054169689Skan if (var->n_var_parts == 0) 2055169689Skan { 2056169689Skan void **slot = htab_find_slot_with_hash (htab, var->decl, hash, 2057169689Skan NO_INSERT); 2058169689Skan if (slot) 2059169689Skan htab_clear_slot (htab, slot); 2060169689Skan } 2061169689Skan } 2062169689Skan} 2063169689Skan 2064169689Skan/* Look for the index in VAR->var_part corresponding to OFFSET. 2065169689Skan Return -1 if not found. If INSERTION_POINT is non-NULL, the 2066169689Skan referenced int will be set to the index that the part has or should 2067169689Skan have, if it should be inserted. */ 2068169689Skan 2069169689Skanstatic inline int 2070169689Skanfind_variable_location_part (variable var, HOST_WIDE_INT offset, 2071169689Skan int *insertion_point) 2072169689Skan{ 2073169689Skan int pos, low, high; 2074169689Skan 2075169689Skan /* Find the location part. */ 2076169689Skan low = 0; 2077169689Skan high = var->n_var_parts; 2078169689Skan while (low != high) 2079169689Skan { 2080169689Skan pos = (low + high) / 2; 2081169689Skan if (var->var_part[pos].offset < offset) 2082169689Skan low = pos + 1; 2083169689Skan else 2084169689Skan high = pos; 2085169689Skan } 2086169689Skan pos = low; 2087169689Skan 2088169689Skan if (insertion_point) 2089169689Skan *insertion_point = pos; 2090169689Skan 2091169689Skan if (pos < var->n_var_parts && var->var_part[pos].offset == offset) 2092169689Skan return pos; 2093169689Skan 2094169689Skan return -1; 2095169689Skan} 2096169689Skan 2097169689Skan/* Set the part of variable's location in the dataflow set SET. The variable 2098169689Skan part is specified by variable's declaration DECL and offset OFFSET and the 2099169689Skan part's location by LOC. */ 2100169689Skan 2101169689Skanstatic void 2102169689Skanset_variable_part (dataflow_set *set, rtx loc, tree decl, HOST_WIDE_INT offset) 2103169689Skan{ 2104169689Skan int pos; 2105169689Skan location_chain node, next; 2106169689Skan location_chain *nextp; 2107169689Skan variable var; 2108169689Skan void **slot; 2109169689Skan 2110169689Skan slot = htab_find_slot_with_hash (set->vars, decl, 2111169689Skan VARIABLE_HASH_VAL (decl), INSERT); 2112169689Skan if (!*slot) 2113169689Skan { 2114169689Skan /* Create new variable information. */ 2115169689Skan var = pool_alloc (var_pool); 2116169689Skan var->decl = decl; 2117169689Skan var->refcount = 1; 2118169689Skan var->n_var_parts = 1; 2119169689Skan var->var_part[0].offset = offset; 2120169689Skan var->var_part[0].loc_chain = NULL; 2121169689Skan var->var_part[0].cur_loc = NULL; 2122169689Skan *slot = var; 2123169689Skan pos = 0; 2124169689Skan } 2125169689Skan else 2126169689Skan { 2127169689Skan int inspos = 0; 2128169689Skan 2129169689Skan var = (variable) *slot; 2130169689Skan 2131169689Skan pos = find_variable_location_part (var, offset, &inspos); 2132169689Skan 2133169689Skan if (pos >= 0) 2134169689Skan { 2135169689Skan node = var->var_part[pos].loc_chain; 2136169689Skan 2137169689Skan if (node 2138169689Skan && ((REG_P (node->loc) && REG_P (loc) 2139169689Skan && REGNO (node->loc) == REGNO (loc)) 2140169689Skan || rtx_equal_p (node->loc, loc))) 2141169689Skan { 2142169689Skan /* LOC is in the beginning of the chain so we have nothing 2143169689Skan to do. */ 2144169689Skan return; 2145169689Skan } 2146169689Skan else 2147169689Skan { 2148169689Skan /* We have to make a copy of a shared variable. */ 2149169689Skan if (var->refcount > 1) 2150169689Skan var = unshare_variable (set, var); 2151169689Skan } 2152169689Skan } 2153169689Skan else 2154169689Skan { 2155169689Skan /* We have not found the location part, new one will be created. */ 2156169689Skan 2157169689Skan /* We have to make a copy of the shared variable. */ 2158169689Skan if (var->refcount > 1) 2159169689Skan var = unshare_variable (set, var); 2160169689Skan 2161169689Skan /* We track only variables whose size is <= MAX_VAR_PARTS bytes 2162169689Skan thus there are at most MAX_VAR_PARTS different offsets. */ 2163169689Skan gcc_assert (var->n_var_parts < MAX_VAR_PARTS); 2164169689Skan 2165169689Skan /* We have to move the elements of array starting at index 2166169689Skan inspos to the next position. */ 2167169689Skan for (pos = var->n_var_parts; pos > inspos; pos--) 2168169689Skan var->var_part[pos] = var->var_part[pos - 1]; 2169169689Skan 2170169689Skan var->n_var_parts++; 2171169689Skan var->var_part[pos].offset = offset; 2172169689Skan var->var_part[pos].loc_chain = NULL; 2173169689Skan var->var_part[pos].cur_loc = NULL; 2174169689Skan } 2175169689Skan } 2176169689Skan 2177169689Skan /* Delete the location from the list. */ 2178169689Skan nextp = &var->var_part[pos].loc_chain; 2179169689Skan for (node = var->var_part[pos].loc_chain; node; node = next) 2180169689Skan { 2181169689Skan next = node->next; 2182169689Skan if ((REG_P (node->loc) && REG_P (loc) 2183169689Skan && REGNO (node->loc) == REGNO (loc)) 2184169689Skan || rtx_equal_p (node->loc, loc)) 2185169689Skan { 2186169689Skan pool_free (loc_chain_pool, node); 2187169689Skan *nextp = next; 2188169689Skan break; 2189169689Skan } 2190169689Skan else 2191169689Skan nextp = &node->next; 2192169689Skan } 2193169689Skan 2194169689Skan /* Add the location to the beginning. */ 2195169689Skan node = pool_alloc (loc_chain_pool); 2196169689Skan node->loc = loc; 2197169689Skan node->next = var->var_part[pos].loc_chain; 2198169689Skan var->var_part[pos].loc_chain = node; 2199169689Skan 2200169689Skan /* If no location was emitted do so. */ 2201169689Skan if (var->var_part[pos].cur_loc == NULL) 2202169689Skan { 2203169689Skan var->var_part[pos].cur_loc = loc; 2204169689Skan variable_was_changed (var, set->vars); 2205169689Skan } 2206169689Skan} 2207169689Skan 2208169689Skan/* Remove all recorded register locations for the given variable part 2209169689Skan from dataflow set SET, except for those that are identical to loc. 2210169689Skan The variable part is specified by variable's declaration DECL and 2211169689Skan offset OFFSET. */ 2212169689Skan 2213169689Skanstatic void 2214169689Skanclobber_variable_part (dataflow_set *set, rtx loc, tree decl, 2215169689Skan HOST_WIDE_INT offset) 2216169689Skan{ 2217169689Skan void **slot; 2218169689Skan 2219169689Skan if (! decl || ! DECL_P (decl)) 2220169689Skan return; 2221169689Skan 2222169689Skan slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl), 2223169689Skan NO_INSERT); 2224169689Skan if (slot) 2225169689Skan { 2226169689Skan variable var = (variable) *slot; 2227169689Skan int pos = find_variable_location_part (var, offset, NULL); 2228169689Skan 2229169689Skan if (pos >= 0) 2230169689Skan { 2231169689Skan location_chain node, next; 2232169689Skan 2233169689Skan /* Remove the register locations from the dataflow set. */ 2234169689Skan next = var->var_part[pos].loc_chain; 2235169689Skan for (node = next; node; node = next) 2236169689Skan { 2237169689Skan next = node->next; 2238169689Skan if (node->loc != loc) 2239169689Skan { 2240169689Skan if (REG_P (node->loc)) 2241169689Skan { 2242169689Skan attrs anode, anext; 2243169689Skan attrs *anextp; 2244169689Skan 2245169689Skan /* Remove the variable part from the register's 2246169689Skan list, but preserve any other variable parts 2247169689Skan that might be regarded as live in that same 2248169689Skan register. */ 2249169689Skan anextp = &set->regs[REGNO (node->loc)]; 2250169689Skan for (anode = *anextp; anode; anode = anext) 2251169689Skan { 2252169689Skan anext = anode->next; 2253169689Skan if (anode->decl == decl 2254169689Skan && anode->offset == offset) 2255169689Skan { 2256169689Skan pool_free (attrs_pool, anode); 2257169689Skan *anextp = anext; 2258169689Skan } 2259169689Skan } 2260169689Skan } 2261169689Skan 2262169689Skan delete_variable_part (set, node->loc, decl, offset); 2263169689Skan } 2264169689Skan } 2265169689Skan } 2266169689Skan } 2267169689Skan} 2268169689Skan 2269169689Skan/* Delete the part of variable's location from dataflow set SET. The variable 2270169689Skan part is specified by variable's declaration DECL and offset OFFSET and the 2271169689Skan part's location by LOC. */ 2272169689Skan 2273169689Skanstatic void 2274169689Skandelete_variable_part (dataflow_set *set, rtx loc, tree decl, 2275169689Skan HOST_WIDE_INT offset) 2276169689Skan{ 2277169689Skan void **slot; 2278169689Skan 2279169689Skan slot = htab_find_slot_with_hash (set->vars, decl, VARIABLE_HASH_VAL (decl), 2280169689Skan NO_INSERT); 2281169689Skan if (slot) 2282169689Skan { 2283169689Skan variable var = (variable) *slot; 2284169689Skan int pos = find_variable_location_part (var, offset, NULL); 2285169689Skan 2286169689Skan if (pos >= 0) 2287169689Skan { 2288169689Skan location_chain node, next; 2289169689Skan location_chain *nextp; 2290169689Skan bool changed; 2291169689Skan 2292169689Skan if (var->refcount > 1) 2293169689Skan { 2294169689Skan /* If the variable contains the location part we have to 2295169689Skan make a copy of the variable. */ 2296169689Skan for (node = var->var_part[pos].loc_chain; node; 2297169689Skan node = node->next) 2298169689Skan { 2299169689Skan if ((REG_P (node->loc) && REG_P (loc) 2300169689Skan && REGNO (node->loc) == REGNO (loc)) 2301169689Skan || rtx_equal_p (node->loc, loc)) 2302169689Skan { 2303169689Skan var = unshare_variable (set, var); 2304169689Skan break; 2305169689Skan } 2306169689Skan } 2307169689Skan } 2308169689Skan 2309169689Skan /* Delete the location part. */ 2310169689Skan nextp = &var->var_part[pos].loc_chain; 2311169689Skan for (node = *nextp; node; node = next) 2312169689Skan { 2313169689Skan next = node->next; 2314169689Skan if ((REG_P (node->loc) && REG_P (loc) 2315169689Skan && REGNO (node->loc) == REGNO (loc)) 2316169689Skan || rtx_equal_p (node->loc, loc)) 2317169689Skan { 2318169689Skan pool_free (loc_chain_pool, node); 2319169689Skan *nextp = next; 2320169689Skan break; 2321169689Skan } 2322169689Skan else 2323169689Skan nextp = &node->next; 2324169689Skan } 2325169689Skan 2326169689Skan /* If we have deleted the location which was last emitted 2327169689Skan we have to emit new location so add the variable to set 2328169689Skan of changed variables. */ 2329169689Skan if (var->var_part[pos].cur_loc 2330169689Skan && ((REG_P (loc) 2331169689Skan && REG_P (var->var_part[pos].cur_loc) 2332169689Skan && REGNO (loc) == REGNO (var->var_part[pos].cur_loc)) 2333169689Skan || rtx_equal_p (loc, var->var_part[pos].cur_loc))) 2334169689Skan { 2335169689Skan changed = true; 2336169689Skan if (var->var_part[pos].loc_chain) 2337169689Skan var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc; 2338169689Skan } 2339169689Skan else 2340169689Skan changed = false; 2341169689Skan 2342169689Skan if (var->var_part[pos].loc_chain == NULL) 2343169689Skan { 2344169689Skan var->n_var_parts--; 2345169689Skan while (pos < var->n_var_parts) 2346169689Skan { 2347169689Skan var->var_part[pos] = var->var_part[pos + 1]; 2348169689Skan pos++; 2349169689Skan } 2350169689Skan } 2351169689Skan if (changed) 2352169689Skan variable_was_changed (var, set->vars); 2353169689Skan } 2354169689Skan } 2355169689Skan} 2356169689Skan 2357169689Skan/* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP. DATA contains 2358169689Skan additional parameters: WHERE specifies whether the note shall be emitted 2359169689Skan before of after instruction INSN. */ 2360169689Skan 2361169689Skanstatic int 2362169689Skanemit_note_insn_var_location (void **varp, void *data) 2363169689Skan{ 2364169689Skan variable var = *(variable *) varp; 2365169689Skan rtx insn = ((emit_note_data *)data)->insn; 2366169689Skan enum emit_note_where where = ((emit_note_data *)data)->where; 2367169689Skan rtx note; 2368169689Skan int i, j, n_var_parts; 2369169689Skan bool complete; 2370169689Skan HOST_WIDE_INT last_limit; 2371169689Skan tree type_size_unit; 2372169689Skan HOST_WIDE_INT offsets[MAX_VAR_PARTS]; 2373169689Skan rtx loc[MAX_VAR_PARTS]; 2374169689Skan 2375169689Skan gcc_assert (var->decl); 2376169689Skan 2377169689Skan complete = true; 2378169689Skan last_limit = 0; 2379169689Skan n_var_parts = 0; 2380169689Skan for (i = 0; i < var->n_var_parts; i++) 2381169689Skan { 2382169689Skan enum machine_mode mode, wider_mode; 2383169689Skan 2384169689Skan if (last_limit < var->var_part[i].offset) 2385169689Skan { 2386169689Skan complete = false; 2387169689Skan break; 2388169689Skan } 2389169689Skan else if (last_limit > var->var_part[i].offset) 2390169689Skan continue; 2391169689Skan offsets[n_var_parts] = var->var_part[i].offset; 2392169689Skan loc[n_var_parts] = var->var_part[i].loc_chain->loc; 2393169689Skan mode = GET_MODE (loc[n_var_parts]); 2394169689Skan last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode); 2395169689Skan 2396169689Skan /* Attempt to merge adjacent registers or memory. */ 2397169689Skan wider_mode = GET_MODE_WIDER_MODE (mode); 2398169689Skan for (j = i + 1; j < var->n_var_parts; j++) 2399169689Skan if (last_limit <= var->var_part[j].offset) 2400169689Skan break; 2401169689Skan if (j < var->n_var_parts 2402169689Skan && wider_mode != VOIDmode 2403169689Skan && GET_CODE (loc[n_var_parts]) 2404169689Skan == GET_CODE (var->var_part[j].loc_chain->loc) 2405169689Skan && mode == GET_MODE (var->var_part[j].loc_chain->loc) 2406169689Skan && last_limit == var->var_part[j].offset) 2407169689Skan { 2408169689Skan rtx new_loc = NULL; 2409169689Skan rtx loc2 = var->var_part[j].loc_chain->loc; 2410169689Skan 2411169689Skan if (REG_P (loc[n_var_parts]) 2412169689Skan && hard_regno_nregs[REGNO (loc[n_var_parts])][mode] * 2 2413169689Skan == hard_regno_nregs[REGNO (loc[n_var_parts])][wider_mode] 2414169689Skan && REGNO (loc[n_var_parts]) 2415169689Skan + hard_regno_nregs[REGNO (loc[n_var_parts])][mode] 2416169689Skan == REGNO (loc2)) 2417169689Skan { 2418169689Skan if (! WORDS_BIG_ENDIAN && ! BYTES_BIG_ENDIAN) 2419169689Skan new_loc = simplify_subreg (wider_mode, loc[n_var_parts], 2420169689Skan mode, 0); 2421169689Skan else if (WORDS_BIG_ENDIAN && BYTES_BIG_ENDIAN) 2422169689Skan new_loc = simplify_subreg (wider_mode, loc2, mode, 0); 2423169689Skan if (new_loc) 2424169689Skan { 2425169689Skan if (!REG_P (new_loc) 2426169689Skan || REGNO (new_loc) != REGNO (loc[n_var_parts])) 2427169689Skan new_loc = NULL; 2428169689Skan else 2429169689Skan REG_ATTRS (new_loc) = REG_ATTRS (loc[n_var_parts]); 2430169689Skan } 2431169689Skan } 2432169689Skan else if (MEM_P (loc[n_var_parts]) 2433169689Skan && GET_CODE (XEXP (loc2, 0)) == PLUS 2434169689Skan && GET_CODE (XEXP (XEXP (loc2, 0), 0)) == REG 2435169689Skan && GET_CODE (XEXP (XEXP (loc2, 0), 1)) == CONST_INT) 2436169689Skan { 2437169689Skan if ((GET_CODE (XEXP (loc[n_var_parts], 0)) == REG 2438169689Skan && rtx_equal_p (XEXP (loc[n_var_parts], 0), 2439169689Skan XEXP (XEXP (loc2, 0), 0)) 2440169689Skan && INTVAL (XEXP (XEXP (loc2, 0), 1)) 2441169689Skan == GET_MODE_SIZE (mode)) 2442169689Skan || (GET_CODE (XEXP (loc[n_var_parts], 0)) == PLUS 2443169689Skan && GET_CODE (XEXP (XEXP (loc[n_var_parts], 0), 1)) 2444169689Skan == CONST_INT 2445169689Skan && rtx_equal_p (XEXP (XEXP (loc[n_var_parts], 0), 0), 2446169689Skan XEXP (XEXP (loc2, 0), 0)) 2447169689Skan && INTVAL (XEXP (XEXP (loc[n_var_parts], 0), 1)) 2448169689Skan + GET_MODE_SIZE (mode) 2449169689Skan == INTVAL (XEXP (XEXP (loc2, 0), 1)))) 2450169689Skan new_loc = adjust_address_nv (loc[n_var_parts], 2451169689Skan wider_mode, 0); 2452169689Skan } 2453169689Skan 2454169689Skan if (new_loc) 2455169689Skan { 2456169689Skan loc[n_var_parts] = new_loc; 2457169689Skan mode = wider_mode; 2458169689Skan last_limit = offsets[n_var_parts] + GET_MODE_SIZE (mode); 2459169689Skan i = j; 2460169689Skan } 2461169689Skan } 2462169689Skan ++n_var_parts; 2463169689Skan } 2464169689Skan type_size_unit = TYPE_SIZE_UNIT (TREE_TYPE (var->decl)); 2465169689Skan if ((unsigned HOST_WIDE_INT) last_limit < TREE_INT_CST_LOW (type_size_unit)) 2466169689Skan complete = false; 2467169689Skan 2468169689Skan if (where == EMIT_NOTE_AFTER_INSN) 2469169689Skan note = emit_note_after (NOTE_INSN_VAR_LOCATION, insn); 2470169689Skan else 2471169689Skan note = emit_note_before (NOTE_INSN_VAR_LOCATION, insn); 2472169689Skan 2473169689Skan if (!complete) 2474169689Skan { 2475169689Skan NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2476169689Skan NULL_RTX); 2477169689Skan } 2478169689Skan else if (n_var_parts == 1) 2479169689Skan { 2480169689Skan rtx expr_list 2481169689Skan = gen_rtx_EXPR_LIST (VOIDmode, loc[0], GEN_INT (offsets[0])); 2482169689Skan 2483169689Skan NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2484169689Skan expr_list); 2485169689Skan } 2486169689Skan else if (n_var_parts) 2487169689Skan { 2488169689Skan rtx parallel; 2489169689Skan 2490169689Skan for (i = 0; i < n_var_parts; i++) 2491169689Skan loc[i] 2492169689Skan = gen_rtx_EXPR_LIST (VOIDmode, loc[i], GEN_INT (offsets[i])); 2493169689Skan 2494169689Skan parallel = gen_rtx_PARALLEL (VOIDmode, 2495169689Skan gen_rtvec_v (n_var_parts, loc)); 2496169689Skan NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, var->decl, 2497169689Skan parallel); 2498169689Skan } 2499169689Skan 2500169689Skan htab_clear_slot (changed_variables, varp); 2501169689Skan 2502169689Skan /* When there are no location parts the variable has been already 2503169689Skan removed from hash table and a new empty variable was created. 2504169689Skan Free the empty variable. */ 2505169689Skan if (var->n_var_parts == 0) 2506169689Skan { 2507169689Skan pool_free (var_pool, var); 2508169689Skan } 2509169689Skan 2510169689Skan /* Continue traversing the hash table. */ 2511169689Skan return 1; 2512169689Skan} 2513169689Skan 2514169689Skan/* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain 2515169689Skan CHANGED_VARIABLES and delete this chain. WHERE specifies whether the notes 2516169689Skan shall be emitted before of after instruction INSN. */ 2517169689Skan 2518169689Skanstatic void 2519169689Skanemit_notes_for_changes (rtx insn, enum emit_note_where where) 2520169689Skan{ 2521169689Skan emit_note_data data; 2522169689Skan 2523169689Skan data.insn = insn; 2524169689Skan data.where = where; 2525169689Skan htab_traverse (changed_variables, emit_note_insn_var_location, &data); 2526169689Skan} 2527169689Skan 2528169689Skan/* Add variable *SLOT to the chain CHANGED_VARIABLES if it differs from the 2529169689Skan same variable in hash table DATA or is not there at all. */ 2530169689Skan 2531169689Skanstatic int 2532169689Skanemit_notes_for_differences_1 (void **slot, void *data) 2533169689Skan{ 2534169689Skan htab_t new_vars = (htab_t) data; 2535169689Skan variable old_var, new_var; 2536169689Skan 2537169689Skan old_var = *(variable *) slot; 2538169689Skan new_var = htab_find_with_hash (new_vars, old_var->decl, 2539169689Skan VARIABLE_HASH_VAL (old_var->decl)); 2540169689Skan 2541169689Skan if (!new_var) 2542169689Skan { 2543169689Skan /* Variable has disappeared. */ 2544169689Skan variable empty_var; 2545169689Skan 2546169689Skan empty_var = pool_alloc (var_pool); 2547169689Skan empty_var->decl = old_var->decl; 2548169689Skan empty_var->refcount = 1; 2549169689Skan empty_var->n_var_parts = 0; 2550169689Skan variable_was_changed (empty_var, NULL); 2551169689Skan } 2552169689Skan else if (variable_different_p (old_var, new_var, true)) 2553169689Skan { 2554169689Skan variable_was_changed (new_var, NULL); 2555169689Skan } 2556169689Skan 2557169689Skan /* Continue traversing the hash table. */ 2558169689Skan return 1; 2559169689Skan} 2560169689Skan 2561169689Skan/* Add variable *SLOT to the chain CHANGED_VARIABLES if it is not in hash 2562169689Skan table DATA. */ 2563169689Skan 2564169689Skanstatic int 2565169689Skanemit_notes_for_differences_2 (void **slot, void *data) 2566169689Skan{ 2567169689Skan htab_t old_vars = (htab_t) data; 2568169689Skan variable old_var, new_var; 2569169689Skan 2570169689Skan new_var = *(variable *) slot; 2571169689Skan old_var = htab_find_with_hash (old_vars, new_var->decl, 2572169689Skan VARIABLE_HASH_VAL (new_var->decl)); 2573169689Skan if (!old_var) 2574169689Skan { 2575169689Skan /* Variable has appeared. */ 2576169689Skan variable_was_changed (new_var, NULL); 2577169689Skan } 2578169689Skan 2579169689Skan /* Continue traversing the hash table. */ 2580169689Skan return 1; 2581169689Skan} 2582169689Skan 2583169689Skan/* Emit notes before INSN for differences between dataflow sets OLD_SET and 2584169689Skan NEW_SET. */ 2585169689Skan 2586169689Skanstatic void 2587169689Skanemit_notes_for_differences (rtx insn, dataflow_set *old_set, 2588169689Skan dataflow_set *new_set) 2589169689Skan{ 2590169689Skan htab_traverse (old_set->vars, emit_notes_for_differences_1, new_set->vars); 2591169689Skan htab_traverse (new_set->vars, emit_notes_for_differences_2, old_set->vars); 2592169689Skan emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2593169689Skan} 2594169689Skan 2595169689Skan/* Emit the notes for changes of location parts in the basic block BB. */ 2596169689Skan 2597169689Skanstatic void 2598169689Skanemit_notes_in_bb (basic_block bb) 2599169689Skan{ 2600169689Skan int i; 2601169689Skan dataflow_set set; 2602169689Skan 2603169689Skan dataflow_set_init (&set, htab_elements (VTI (bb)->in.vars) + 3); 2604169689Skan dataflow_set_copy (&set, &VTI (bb)->in); 2605169689Skan 2606169689Skan for (i = 0; i < VTI (bb)->n_mos; i++) 2607169689Skan { 2608169689Skan rtx insn = VTI (bb)->mos[i].insn; 2609169689Skan 2610169689Skan switch (VTI (bb)->mos[i].type) 2611169689Skan { 2612169689Skan case MO_CALL: 2613169689Skan { 2614169689Skan int r; 2615169689Skan 2616169689Skan for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) 2617169689Skan if (TEST_HARD_REG_BIT (call_used_reg_set, r)) 2618169689Skan { 2619169689Skan var_regno_delete (&set, r); 2620169689Skan } 2621169689Skan emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2622169689Skan } 2623169689Skan break; 2624169689Skan 2625169689Skan case MO_USE: 2626169689Skan { 2627169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 2628169689Skan 2629169689Skan if (GET_CODE (loc) == REG) 2630169689Skan var_reg_set (&set, loc); 2631169689Skan else 2632169689Skan var_mem_set (&set, loc); 2633169689Skan 2634169689Skan emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2635169689Skan } 2636169689Skan break; 2637169689Skan 2638169689Skan case MO_SET: 2639169689Skan { 2640169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 2641169689Skan 2642169689Skan if (REG_P (loc)) 2643169689Skan var_reg_delete_and_set (&set, loc, true); 2644169689Skan else 2645169689Skan var_mem_delete_and_set (&set, loc, true); 2646169689Skan 2647169689Skan emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2648169689Skan } 2649169689Skan break; 2650169689Skan 2651169689Skan case MO_COPY: 2652169689Skan { 2653169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 2654169689Skan 2655169689Skan if (REG_P (loc)) 2656169689Skan var_reg_delete_and_set (&set, loc, false); 2657169689Skan else 2658169689Skan var_mem_delete_and_set (&set, loc, false); 2659169689Skan 2660169689Skan emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2661169689Skan } 2662169689Skan break; 2663169689Skan 2664169689Skan case MO_USE_NO_VAR: 2665169689Skan { 2666169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 2667169689Skan 2668169689Skan if (REG_P (loc)) 2669169689Skan var_reg_delete (&set, loc, false); 2670169689Skan else 2671169689Skan var_mem_delete (&set, loc, false); 2672169689Skan 2673169689Skan emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN); 2674169689Skan } 2675169689Skan break; 2676169689Skan 2677169689Skan case MO_CLOBBER: 2678169689Skan { 2679169689Skan rtx loc = VTI (bb)->mos[i].u.loc; 2680169689Skan 2681169689Skan if (REG_P (loc)) 2682169689Skan var_reg_delete (&set, loc, true); 2683169689Skan else 2684169689Skan var_mem_delete (&set, loc, true); 2685169689Skan 2686169689Skan emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN); 2687169689Skan } 2688169689Skan break; 2689169689Skan 2690169689Skan case MO_ADJUST: 2691169689Skan set.stack_adjust += VTI (bb)->mos[i].u.adjust; 2692169689Skan break; 2693169689Skan } 2694169689Skan } 2695169689Skan dataflow_set_destroy (&set); 2696169689Skan} 2697169689Skan 2698169689Skan/* Emit notes for the whole function. */ 2699169689Skan 2700169689Skanstatic void 2701169689Skanvt_emit_notes (void) 2702169689Skan{ 2703169689Skan basic_block bb; 2704169689Skan dataflow_set *last_out; 2705169689Skan dataflow_set empty; 2706169689Skan 2707169689Skan gcc_assert (!htab_elements (changed_variables)); 2708169689Skan 2709169689Skan /* Enable emitting notes by functions (mainly by set_variable_part and 2710169689Skan delete_variable_part). */ 2711169689Skan emit_notes = true; 2712169689Skan 2713169689Skan dataflow_set_init (&empty, 7); 2714169689Skan last_out = ∅ 2715169689Skan 2716169689Skan FOR_EACH_BB (bb) 2717169689Skan { 2718169689Skan /* Emit the notes for changes of variable locations between two 2719169689Skan subsequent basic blocks. */ 2720169689Skan emit_notes_for_differences (BB_HEAD (bb), last_out, &VTI (bb)->in); 2721169689Skan 2722169689Skan /* Emit the notes for the changes in the basic block itself. */ 2723169689Skan emit_notes_in_bb (bb); 2724169689Skan 2725169689Skan last_out = &VTI (bb)->out; 2726169689Skan } 2727169689Skan dataflow_set_destroy (&empty); 2728169689Skan emit_notes = false; 2729169689Skan} 2730169689Skan 2731169689Skan/* If there is a declaration and offset associated with register/memory RTL 2732169689Skan assign declaration to *DECLP and offset to *OFFSETP, and return true. */ 2733169689Skan 2734169689Skanstatic bool 2735169689Skanvt_get_decl_and_offset (rtx rtl, tree *declp, HOST_WIDE_INT *offsetp) 2736169689Skan{ 2737169689Skan if (REG_P (rtl)) 2738169689Skan { 2739169689Skan if (REG_ATTRS (rtl)) 2740169689Skan { 2741169689Skan *declp = REG_EXPR (rtl); 2742169689Skan *offsetp = REG_OFFSET (rtl); 2743169689Skan return true; 2744169689Skan } 2745169689Skan } 2746169689Skan else if (MEM_P (rtl)) 2747169689Skan { 2748169689Skan if (MEM_ATTRS (rtl)) 2749169689Skan { 2750169689Skan *declp = MEM_EXPR (rtl); 2751235623Spfg *offsetp = INT_MEM_OFFSET (rtl); 2752169689Skan return true; 2753169689Skan } 2754169689Skan } 2755169689Skan return false; 2756169689Skan} 2757169689Skan 2758169689Skan/* Insert function parameters to IN and OUT sets of ENTRY_BLOCK. */ 2759169689Skan 2760169689Skanstatic void 2761169689Skanvt_add_function_parameters (void) 2762169689Skan{ 2763169689Skan tree parm; 2764169689Skan 2765169689Skan for (parm = DECL_ARGUMENTS (current_function_decl); 2766169689Skan parm; parm = TREE_CHAIN (parm)) 2767169689Skan { 2768169689Skan rtx decl_rtl = DECL_RTL_IF_SET (parm); 2769169689Skan rtx incoming = DECL_INCOMING_RTL (parm); 2770169689Skan tree decl; 2771169689Skan HOST_WIDE_INT offset; 2772169689Skan dataflow_set *out; 2773169689Skan 2774169689Skan if (TREE_CODE (parm) != PARM_DECL) 2775169689Skan continue; 2776169689Skan 2777169689Skan if (!DECL_NAME (parm)) 2778169689Skan continue; 2779169689Skan 2780169689Skan if (!decl_rtl || !incoming) 2781169689Skan continue; 2782169689Skan 2783169689Skan if (GET_MODE (decl_rtl) == BLKmode || GET_MODE (incoming) == BLKmode) 2784169689Skan continue; 2785169689Skan 2786169689Skan if (!vt_get_decl_and_offset (incoming, &decl, &offset)) 2787169689Skan if (!vt_get_decl_and_offset (decl_rtl, &decl, &offset)) 2788169689Skan continue; 2789169689Skan 2790169689Skan if (!decl) 2791169689Skan continue; 2792169689Skan 2793169689Skan gcc_assert (parm == decl); 2794169689Skan 2795169689Skan out = &VTI (ENTRY_BLOCK_PTR)->out; 2796169689Skan 2797169689Skan if (REG_P (incoming)) 2798169689Skan { 2799169689Skan gcc_assert (REGNO (incoming) < FIRST_PSEUDO_REGISTER); 2800169689Skan attrs_list_insert (&out->regs[REGNO (incoming)], 2801169689Skan parm, offset, incoming); 2802169689Skan set_variable_part (out, incoming, parm, offset); 2803169689Skan } 2804169689Skan else if (MEM_P (incoming)) 2805169689Skan set_variable_part (out, incoming, parm, offset); 2806169689Skan } 2807169689Skan} 2808169689Skan 2809169689Skan/* Allocate and initialize the data structures for variable tracking 2810169689Skan and parse the RTL to get the micro operations. */ 2811169689Skan 2812169689Skanstatic void 2813169689Skanvt_initialize (void) 2814169689Skan{ 2815169689Skan basic_block bb; 2816169689Skan 2817169689Skan alloc_aux_for_blocks (sizeof (struct variable_tracking_info_def)); 2818169689Skan 2819169689Skan FOR_EACH_BB (bb) 2820169689Skan { 2821169689Skan rtx insn; 2822169689Skan HOST_WIDE_INT pre, post = 0; 2823169689Skan 2824169689Skan /* Count the number of micro operations. */ 2825169689Skan VTI (bb)->n_mos = 0; 2826169689Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 2827169689Skan insn = NEXT_INSN (insn)) 2828169689Skan { 2829169689Skan if (INSN_P (insn)) 2830169689Skan { 2831169689Skan if (!frame_pointer_needed) 2832169689Skan { 2833169689Skan insn_stack_adjust_offset_pre_post (insn, &pre, &post); 2834169689Skan if (pre) 2835169689Skan VTI (bb)->n_mos++; 2836169689Skan if (post) 2837169689Skan VTI (bb)->n_mos++; 2838169689Skan } 2839169689Skan note_uses (&PATTERN (insn), count_uses_1, insn); 2840169689Skan note_stores (PATTERN (insn), count_stores, insn); 2841169689Skan if (CALL_P (insn)) 2842169689Skan VTI (bb)->n_mos++; 2843169689Skan } 2844169689Skan } 2845169689Skan 2846169689Skan /* Add the micro-operations to the array. */ 2847169689Skan VTI (bb)->mos = XNEWVEC (micro_operation, VTI (bb)->n_mos); 2848169689Skan VTI (bb)->n_mos = 0; 2849169689Skan for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); 2850169689Skan insn = NEXT_INSN (insn)) 2851169689Skan { 2852169689Skan if (INSN_P (insn)) 2853169689Skan { 2854169689Skan int n1, n2; 2855169689Skan 2856169689Skan if (!frame_pointer_needed) 2857169689Skan { 2858169689Skan insn_stack_adjust_offset_pre_post (insn, &pre, &post); 2859169689Skan if (pre) 2860169689Skan { 2861169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2862169689Skan 2863169689Skan mo->type = MO_ADJUST; 2864169689Skan mo->u.adjust = pre; 2865169689Skan mo->insn = insn; 2866169689Skan } 2867169689Skan } 2868169689Skan 2869169689Skan n1 = VTI (bb)->n_mos; 2870169689Skan note_uses (&PATTERN (insn), add_uses_1, insn); 2871169689Skan n2 = VTI (bb)->n_mos - 1; 2872169689Skan 2873169689Skan /* Order the MO_USEs to be before MO_USE_NO_VARs. */ 2874169689Skan while (n1 < n2) 2875169689Skan { 2876169689Skan while (n1 < n2 && VTI (bb)->mos[n1].type == MO_USE) 2877169689Skan n1++; 2878169689Skan while (n1 < n2 && VTI (bb)->mos[n2].type == MO_USE_NO_VAR) 2879169689Skan n2--; 2880169689Skan if (n1 < n2) 2881169689Skan { 2882169689Skan micro_operation sw; 2883169689Skan 2884169689Skan sw = VTI (bb)->mos[n1]; 2885169689Skan VTI (bb)->mos[n1] = VTI (bb)->mos[n2]; 2886169689Skan VTI (bb)->mos[n2] = sw; 2887169689Skan } 2888169689Skan } 2889169689Skan 2890169689Skan if (CALL_P (insn)) 2891169689Skan { 2892169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2893169689Skan 2894169689Skan mo->type = MO_CALL; 2895169689Skan mo->insn = insn; 2896169689Skan } 2897169689Skan 2898169689Skan n1 = VTI (bb)->n_mos; 2899169689Skan /* This will record NEXT_INSN (insn), such that we can 2900169689Skan insert notes before it without worrying about any 2901169689Skan notes that MO_USEs might emit after the insn. */ 2902169689Skan note_stores (PATTERN (insn), add_stores, insn); 2903169689Skan n2 = VTI (bb)->n_mos - 1; 2904169689Skan 2905169689Skan /* Order the MO_CLOBBERs to be before MO_SETs. */ 2906169689Skan while (n1 < n2) 2907169689Skan { 2908169689Skan while (n1 < n2 && VTI (bb)->mos[n1].type == MO_CLOBBER) 2909169689Skan n1++; 2910169689Skan while (n1 < n2 && (VTI (bb)->mos[n2].type == MO_SET 2911169689Skan || VTI (bb)->mos[n2].type == MO_COPY)) 2912169689Skan n2--; 2913169689Skan if (n1 < n2) 2914169689Skan { 2915169689Skan micro_operation sw; 2916169689Skan 2917169689Skan sw = VTI (bb)->mos[n1]; 2918169689Skan VTI (bb)->mos[n1] = VTI (bb)->mos[n2]; 2919169689Skan VTI (bb)->mos[n2] = sw; 2920169689Skan } 2921169689Skan } 2922169689Skan 2923169689Skan if (!frame_pointer_needed && post) 2924169689Skan { 2925169689Skan micro_operation *mo = VTI (bb)->mos + VTI (bb)->n_mos++; 2926169689Skan 2927169689Skan mo->type = MO_ADJUST; 2928169689Skan mo->u.adjust = post; 2929169689Skan mo->insn = insn; 2930169689Skan } 2931169689Skan } 2932169689Skan } 2933169689Skan } 2934169689Skan 2935169689Skan /* Init the IN and OUT sets. */ 2936169689Skan FOR_ALL_BB (bb) 2937169689Skan { 2938169689Skan VTI (bb)->visited = false; 2939169689Skan dataflow_set_init (&VTI (bb)->in, 7); 2940169689Skan dataflow_set_init (&VTI (bb)->out, 7); 2941169689Skan } 2942169689Skan 2943169689Skan attrs_pool = create_alloc_pool ("attrs_def pool", 2944169689Skan sizeof (struct attrs_def), 1024); 2945169689Skan var_pool = create_alloc_pool ("variable_def pool", 2946169689Skan sizeof (struct variable_def), 64); 2947169689Skan loc_chain_pool = create_alloc_pool ("location_chain_def pool", 2948169689Skan sizeof (struct location_chain_def), 2949169689Skan 1024); 2950169689Skan changed_variables = htab_create (10, variable_htab_hash, variable_htab_eq, 2951169689Skan NULL); 2952169689Skan vt_add_function_parameters (); 2953169689Skan} 2954169689Skan 2955169689Skan/* Free the data structures needed for variable tracking. */ 2956169689Skan 2957169689Skanstatic void 2958169689Skanvt_finalize (void) 2959169689Skan{ 2960169689Skan basic_block bb; 2961169689Skan 2962169689Skan FOR_EACH_BB (bb) 2963169689Skan { 2964169689Skan free (VTI (bb)->mos); 2965169689Skan } 2966169689Skan 2967169689Skan FOR_ALL_BB (bb) 2968169689Skan { 2969169689Skan dataflow_set_destroy (&VTI (bb)->in); 2970169689Skan dataflow_set_destroy (&VTI (bb)->out); 2971169689Skan } 2972169689Skan free_aux_for_blocks (); 2973169689Skan free_alloc_pool (attrs_pool); 2974169689Skan free_alloc_pool (var_pool); 2975169689Skan free_alloc_pool (loc_chain_pool); 2976169689Skan htab_delete (changed_variables); 2977169689Skan} 2978169689Skan 2979169689Skan/* The entry point to variable tracking pass. */ 2980169689Skan 2981169689Skanunsigned int 2982169689Skanvariable_tracking_main (void) 2983169689Skan{ 2984169689Skan if (n_basic_blocks > 500 && n_edges / n_basic_blocks >= 20) 2985169689Skan return 0; 2986169689Skan 2987169689Skan mark_dfs_back_edges (); 2988169689Skan vt_initialize (); 2989169689Skan if (!frame_pointer_needed) 2990169689Skan { 2991169689Skan if (!vt_stack_adjustments ()) 2992169689Skan { 2993169689Skan vt_finalize (); 2994169689Skan return 0; 2995169689Skan } 2996169689Skan } 2997169689Skan 2998169689Skan vt_find_locations (); 2999169689Skan vt_emit_notes (); 3000169689Skan 3001169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3002169689Skan { 3003169689Skan dump_dataflow_sets (); 3004169689Skan dump_flow_info (dump_file, dump_flags); 3005169689Skan } 3006169689Skan 3007169689Skan vt_finalize (); 3008169689Skan return 0; 3009169689Skan} 3010169689Skan 3011169689Skanstatic bool 3012169689Skangate_handle_var_tracking (void) 3013169689Skan{ 3014169689Skan return (flag_var_tracking); 3015169689Skan} 3016169689Skan 3017169689Skan 3018169689Skan 3019169689Skanstruct tree_opt_pass pass_variable_tracking = 3020169689Skan{ 3021169689Skan "vartrack", /* name */ 3022169689Skan gate_handle_var_tracking, /* gate */ 3023169689Skan variable_tracking_main, /* execute */ 3024169689Skan NULL, /* sub */ 3025169689Skan NULL, /* next */ 3026169689Skan 0, /* static_pass_number */ 3027169689Skan TV_VAR_TRACKING, /* tv_id */ 3028169689Skan 0, /* properties_required */ 3029169689Skan 0, /* properties_provided */ 3030169689Skan 0, /* properties_destroyed */ 3031169689Skan 0, /* todo_flags_start */ 3032169689Skan TODO_dump_func, /* todo_flags_finish */ 3033169689Skan 'V' /* letter */ 3034169689Skan}; 3035169689Skan 3036