1/* Callgraph based analysis of static variables. 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. 21*/ 22 23/* This file gathers information about how variables whose scope is 24 confined to the compilation unit are used. 25 26 There are two categories of information produced by this pass: 27 28 1) The addressable (TREE_ADDRESSABLE) bit and readonly 29 (TREE_READONLY) bit associated with these variables is properly set 30 based on scanning all of the code withing the compilation unit. 31 32 2) The transitive call site specific clobber effects are computed 33 for the variables whose scope is contained within this compilation 34 unit. 35 36 First each function and static variable initialization is analyzed 37 to determine which local static variables are either read, written, 38 or have their address taken. Any local static that has its address 39 taken is removed from consideration. Once the local read and 40 writes are determined, a transitive closure of this information is 41 performed over the call graph to determine the worst case set of 42 side effects of each call. In later parts of the compiler, these 43 local and global sets are examined to make the call clobbering less 44 traumatic, promote some statics to registers, and improve aliasing 45 information. 46 47 Currently must be run after inlining decisions have been made since 48 otherwise, the local sets will not contain information that is 49 consistent with post inlined state. The global sets are not prone 50 to this problem since they are by definition transitive. 51*/ 52 53#include "config.h" 54#include "system.h" 55#include "coretypes.h" 56#include "tm.h" 57#include "tree.h" 58#include "tree-flow.h" 59#include "tree-inline.h" 60#include "tree-pass.h" 61#include "langhooks.h" 62#include "pointer-set.h" 63#include "ggc.h" 64#include "ipa-utils.h" 65#include "ipa-reference.h" 66#include "c-common.h" 67#include "tree-gimple.h" 68#include "cgraph.h" 69#include "output.h" 70#include "flags.h" 71#include "timevar.h" 72#include "diagnostic.h" 73#include "langhooks.h" 74 75/* This splay tree contains all of the static variables that are 76 being considered by the compilation level alias analysis. For 77 module_at_a_time compilation, this is the set of static but not 78 public variables. Any variables that either have their address 79 taken or participate in otherwise unsavory operations are deleted 80 from this list. */ 81static GTY((param1_is(int), param2_is(tree))) 82 splay_tree reference_vars_to_consider; 83 84/* This bitmap is used to knock out the module static variables whose 85 addresses have been taken and passed around. */ 86static bitmap module_statics_escape; 87 88/* This bitmap is used to knock out the module static variables that 89 are not readonly. */ 90static bitmap module_statics_written; 91 92/* A bit is set for every module static we are considering. This is 93 ored into the local info when asm code is found that clobbers all 94 memory. */ 95static bitmap all_module_statics; 96 97static struct pointer_set_t *visited_nodes; 98 99static bitmap_obstack ipa_obstack; 100 101enum initialization_status_t 102{ 103 UNINITIALIZED, 104 RUNNING, 105 FINISHED 106}; 107 108tree memory_identifier_string; 109 110/* Return the ipa_reference_vars structure starting from the cgraph NODE. */ 111static inline ipa_reference_vars_info_t 112get_reference_vars_info_from_cgraph (struct cgraph_node * node) 113{ 114 return get_function_ann (node->decl)->reference_vars_info; 115} 116 117/* Get a bitmap that contains all of the locally referenced static 118 variables for function FN. */ 119static ipa_reference_local_vars_info_t 120get_local_reference_vars_info (tree fn) 121{ 122 ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info; 123 124 if (info) 125 return info->local; 126 else 127 /* This phase was not run. */ 128 return NULL; 129} 130 131/* Get a bitmap that contains all of the globally referenced static 132 variables for function FN. */ 133 134static ipa_reference_global_vars_info_t 135get_global_reference_vars_info (tree fn) 136{ 137 ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info; 138 139 if (info) 140 return info->global; 141 else 142 /* This phase was not run. */ 143 return NULL; 144} 145 146/* Return a bitmap indexed by VAR_DECL uid for the static variables 147 that may be read locally by the execution of the function fn. 148 Returns NULL if no data is available. */ 149 150bitmap 151ipa_reference_get_read_local (tree fn) 152{ 153 ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn); 154 if (l) 155 return l->statics_read; 156 else 157 return NULL; 158} 159 160/* Return a bitmap indexed by VAR_DECL uid for the static variables 161 that may be written locally by the execution of the function fn. 162 Returns NULL if no data is available. */ 163 164bitmap 165ipa_reference_get_written_local (tree fn) 166{ 167 ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn); 168 if (l) 169 return l->statics_written; 170 else 171 return NULL; 172} 173 174/* Return a bitmap indexed by VAR_DECL uid for the static variables 175 that are read during the execution of the function FN. Returns 176 NULL if no data is available. */ 177 178bitmap 179ipa_reference_get_read_global (tree fn) 180{ 181 ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); 182 if (g) 183 return g->statics_read; 184 else 185 return NULL; 186} 187 188/* Return a bitmap indexed by VAR_DECL uid for the static variables 189 that are written during the execution of the function FN. Note 190 that variables written may or may not be read during the function 191 call. Returns NULL if no data is available. */ 192 193bitmap 194ipa_reference_get_written_global (tree fn) 195{ 196 ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); 197 if (g) 198 return g->statics_written; 199 else 200 return NULL; 201} 202 203/* Return a bitmap indexed by_DECL_UID uid for the static variables 204 that are not read during the execution of the function FN. Returns 205 NULL if no data is available. */ 206 207bitmap 208ipa_reference_get_not_read_global (tree fn) 209{ 210 ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); 211 if (g) 212 return g->statics_not_read; 213 else 214 return NULL; 215} 216 217/* Return a bitmap indexed by DECL_UID uid for the static variables 218 that are not written during the execution of the function FN. Note 219 that variables written may or may not be read during the function 220 call. Returns NULL if no data is available. */ 221 222bitmap 223ipa_reference_get_not_written_global (tree fn) 224{ 225 ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); 226 if (g) 227 return g->statics_not_written; 228 else 229 return NULL; 230} 231 232 233 234/* Add VAR to all_module_statics and the two 235 reference_vars_to_consider* sets. */ 236 237static inline void 238add_static_var (tree var) 239{ 240 int uid = DECL_UID (var); 241 if (!bitmap_bit_p (all_module_statics, uid)) 242 { 243 splay_tree_insert (reference_vars_to_consider, 244 uid, (splay_tree_value)var); 245 bitmap_set_bit (all_module_statics, uid); 246 } 247} 248 249/* Return true if the variable T is the right kind of static variable to 250 perform compilation unit scope escape analysis. */ 251 252static inline bool 253has_proper_scope_for_analysis (tree t) 254{ 255 /* If the variable has the "used" attribute, treat it as if it had a 256 been touched by the devil. */ 257 if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) 258 return false; 259 260 /* Do not want to do anything with volatile except mark any 261 function that uses one to be not const or pure. */ 262 if (TREE_THIS_VOLATILE (t)) 263 return false; 264 265 /* Do not care about a local automatic that is not static. */ 266 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) 267 return false; 268 269 if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) 270 return false; 271 272 /* This is a variable we care about. Check if we have seen it 273 before, and if not add it the set of variables we care about. */ 274 if (!bitmap_bit_p (all_module_statics, DECL_UID (t))) 275 add_static_var (t); 276 277 return true; 278} 279 280/* If T is a VAR_DECL for a static that we are interested in, add the 281 uid to the bitmap. */ 282 283static void 284check_operand (ipa_reference_local_vars_info_t local, 285 tree t, bool checking_write) 286{ 287 if (!t) return; 288 289 if ((TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == FUNCTION_DECL) 290 && (has_proper_scope_for_analysis (t))) 291 { 292 if (checking_write) 293 { 294 if (local) 295 bitmap_set_bit (local->statics_written, DECL_UID (t)); 296 /* Mark the write so we can tell which statics are 297 readonly. */ 298 bitmap_set_bit (module_statics_written, DECL_UID (t)); 299 } 300 else if (local) 301 bitmap_set_bit (local->statics_read, DECL_UID (t)); 302 } 303} 304 305/* Examine tree T for references to static variables. All internal 306 references like array references or indirect references are added 307 to the READ_BM. Direct references are added to either READ_BM or 308 WRITE_BM depending on the value of CHECKING_WRITE. */ 309 310static void 311check_tree (ipa_reference_local_vars_info_t local, tree t, bool checking_write) 312{ 313 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 314 return; 315 316 while (TREE_CODE (t) == REALPART_EXPR 317 || TREE_CODE (t) == IMAGPART_EXPR 318 || handled_component_p (t)) 319 { 320 if (TREE_CODE (t) == ARRAY_REF) 321 check_operand (local, TREE_OPERAND (t, 1), false); 322 t = TREE_OPERAND (t, 0); 323 } 324 325 /* The bottom of an indirect reference can only be read, not 326 written. So just recurse and whatever we find, check it against 327 the read bitmaps. */ 328 329 /* if (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF) */ 330 /* FIXME when we have array_ref's of pointers. */ 331 if (INDIRECT_REF_P (t)) 332 check_tree (local, TREE_OPERAND (t, 0), false); 333 334 if (SSA_VAR_P (t)) 335 check_operand (local, t, checking_write); 336} 337 338/* Scan tree T to see if there are any addresses taken in within T. */ 339 340static void 341look_for_address_of (tree t) 342{ 343 if (TREE_CODE (t) == ADDR_EXPR) 344 { 345 tree x = get_base_var (t); 346 if (TREE_CODE (x) == VAR_DECL || TREE_CODE (x) == FUNCTION_DECL) 347 if (has_proper_scope_for_analysis (x)) 348 bitmap_set_bit (module_statics_escape, DECL_UID (x)); 349 } 350} 351 352/* Check to see if T is a read or address of operation on a static var 353 we are interested in analyzing. LOCAL is passed in to get access 354 to its bit vectors. Local is NULL if this is called from a static 355 initializer. */ 356 357static void 358check_rhs_var (ipa_reference_local_vars_info_t local, tree t) 359{ 360 look_for_address_of (t); 361 362 if (local == NULL) 363 return; 364 365 check_tree(local, t, false); 366} 367 368/* Check to see if T is an assignment to a static var we are 369 interested in analyzing. LOCAL is passed in to get access to its bit 370 vectors. */ 371 372static void 373check_lhs_var (ipa_reference_local_vars_info_t local, tree t) 374{ 375 if (local == NULL) 376 return; 377 378 check_tree(local, t, true); 379} 380 381/* This is a scaled down version of get_asm_expr_operands from 382 tree_ssa_operands.c. The version there runs much later and assumes 383 that aliasing information is already available. Here we are just 384 trying to find if the set of inputs and outputs contain references 385 or address of operations to local static variables. FN is the 386 function being analyzed and STMT is the actual asm statement. */ 387 388static void 389get_asm_expr_operands (ipa_reference_local_vars_info_t local, tree stmt) 390{ 391 int noutputs = list_length (ASM_OUTPUTS (stmt)); 392 const char **oconstraints 393 = (const char **) alloca ((noutputs) * sizeof (const char *)); 394 int i; 395 tree link; 396 const char *constraint; 397 bool allows_mem, allows_reg, is_inout; 398 399 for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) 400 { 401 oconstraints[i] = constraint 402 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 403 parse_output_constraint (&constraint, i, 0, 0, 404 &allows_mem, &allows_reg, &is_inout); 405 406 check_lhs_var (local, TREE_VALUE (link)); 407 } 408 409 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 410 { 411 constraint 412 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 413 parse_input_constraint (&constraint, 0, 0, noutputs, 0, 414 oconstraints, &allows_mem, &allows_reg); 415 416 check_rhs_var (local, TREE_VALUE (link)); 417 } 418 419 for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link)) 420 if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) 421 { 422 /* Abandon all hope, ye who enter here. */ 423 local->calls_read_all = true; 424 local->calls_write_all = true; 425 } 426} 427 428/* Check the parameters of a function call from CALLER to CALL_EXPR to 429 see if any of them are static vars. Also check to see if this is 430 either an indirect call, a call outside the compilation unit, or 431 has special attributes that effect the clobbers. The caller 432 parameter is the tree node for the caller and the second operand is 433 the tree node for the entire call expression. */ 434 435static void 436check_call (ipa_reference_local_vars_info_t local, tree call_expr) 437{ 438 int flags = call_expr_flags (call_expr); 439 tree operand_list = TREE_OPERAND (call_expr, 1); 440 tree operand; 441 tree callee_t = get_callee_fndecl (call_expr); 442 enum availability avail = AVAIL_NOT_AVAILABLE; 443 444 for (operand = operand_list; 445 operand != NULL_TREE; 446 operand = TREE_CHAIN (operand)) 447 { 448 tree argument = TREE_VALUE (operand); 449 check_rhs_var (local, argument); 450 } 451 452 if (callee_t) 453 { 454 struct cgraph_node* callee = cgraph_node(callee_t); 455 avail = cgraph_function_body_availability (callee); 456 } 457 458 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) 459 if (local) 460 { 461 if (flags & ECF_PURE) 462 local->calls_read_all = true; 463 else 464 { 465 local->calls_read_all = true; 466 local->calls_write_all = true; 467 } 468 } 469} 470 471/* TP is the part of the tree currently under the microscope. 472 WALK_SUBTREES is part of the walk_tree api but is unused here. 473 DATA is cgraph_node of the function being walked. */ 474 475/* FIXME: When this is converted to run over SSA form, this code 476 should be converted to use the operand scanner. */ 477 478static tree 479scan_for_static_refs (tree *tp, 480 int *walk_subtrees, 481 void *data) 482{ 483 struct cgraph_node *fn = data; 484 tree t = *tp; 485 ipa_reference_local_vars_info_t local = NULL; 486 if (fn) 487 local = get_reference_vars_info_from_cgraph (fn)->local; 488 489 switch (TREE_CODE (t)) 490 { 491 case VAR_DECL: 492 if (DECL_INITIAL (t)) 493 walk_tree (&DECL_INITIAL (t), scan_for_static_refs, fn, visited_nodes); 494 *walk_subtrees = 0; 495 break; 496 497 case MODIFY_EXPR: 498 { 499 /* First look on the lhs and see what variable is stored to */ 500 tree lhs = TREE_OPERAND (t, 0); 501 tree rhs = TREE_OPERAND (t, 1); 502 check_lhs_var (local, lhs); 503 504 /* For the purposes of figuring out what the cast affects */ 505 506 /* Next check the operands on the rhs to see if they are ok. */ 507 switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 508 { 509 case tcc_binary: 510 case tcc_comparison: 511 { 512 tree op0 = TREE_OPERAND (rhs, 0); 513 tree op1 = TREE_OPERAND (rhs, 1); 514 check_rhs_var (local, op0); 515 check_rhs_var (local, op1); 516 } 517 break; 518 case tcc_unary: 519 { 520 tree op0 = TREE_OPERAND (rhs, 0); 521 check_rhs_var (local, op0); 522 } 523 524 break; 525 case tcc_reference: 526 check_rhs_var (local, rhs); 527 break; 528 case tcc_declaration: 529 check_rhs_var (local, rhs); 530 break; 531 case tcc_expression: 532 switch (TREE_CODE (rhs)) 533 { 534 case ADDR_EXPR: 535 check_rhs_var (local, rhs); 536 break; 537 case CALL_EXPR: 538 check_call (local, rhs); 539 break; 540 default: 541 break; 542 } 543 break; 544 default: 545 break; 546 } 547 *walk_subtrees = 0; 548 } 549 break; 550 551 case ADDR_EXPR: 552 /* This case is here to find addresses on rhs of constructors in 553 decl_initial of static variables. */ 554 check_rhs_var (local, t); 555 *walk_subtrees = 0; 556 break; 557 558 case LABEL_EXPR: 559 if (DECL_NONLOCAL (TREE_OPERAND (t, 0))) 560 { 561 /* Target of long jump. */ 562 local->calls_read_all = true; 563 local->calls_write_all = true; 564 } 565 break; 566 567 case CALL_EXPR: 568 check_call (local, t); 569 *walk_subtrees = 0; 570 break; 571 572 case ASM_EXPR: 573 get_asm_expr_operands (local, t); 574 *walk_subtrees = 0; 575 break; 576 577 default: 578 break; 579 } 580 return NULL; 581} 582 583 584/* Lookup the tree node for the static variable that has UID. */ 585static tree 586get_static_decl (int index) 587{ 588 splay_tree_node stn = 589 splay_tree_lookup (reference_vars_to_consider, index); 590 if (stn) 591 return (tree)stn->value; 592 return NULL; 593} 594 595/* Lookup the tree node for the static variable that has UID and 596 convert the name to a string for debugging. */ 597 598static const char * 599get_static_name (int index) 600{ 601 splay_tree_node stn = 602 splay_tree_lookup (reference_vars_to_consider, index); 603 if (stn) 604 return lang_hooks.decl_printable_name ((tree)(stn->value), 2); 605 return NULL; 606} 607 608/* Or in all of the bits from every callee into X, the caller's, bit 609 vector. There are several cases to check to avoid the sparse 610 bitmap oring. */ 611 612static void 613propagate_bits (struct cgraph_node *x) 614{ 615 ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x); 616 ipa_reference_global_vars_info_t x_global = x_info->global; 617 618 struct cgraph_edge *e; 619 for (e = x->callees; e; e = e->next_callee) 620 { 621 struct cgraph_node *y = e->callee; 622 623 /* Only look at the master nodes and skip external nodes. */ 624 y = cgraph_master_clone (y); 625 if (y) 626 { 627 if (get_reference_vars_info_from_cgraph (y)) 628 { 629 ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y); 630 ipa_reference_global_vars_info_t y_global = y_info->global; 631 632 if (x_global->statics_read 633 != all_module_statics) 634 { 635 if (y_global->statics_read 636 == all_module_statics) 637 { 638 BITMAP_FREE (x_global->statics_read); 639 x_global->statics_read 640 = all_module_statics; 641 } 642 /* Skip bitmaps that are pointer equal to node's bitmap 643 (no reason to spin within the cycle). */ 644 else if (x_global->statics_read 645 != y_global->statics_read) 646 bitmap_ior_into (x_global->statics_read, 647 y_global->statics_read); 648 } 649 650 if (x_global->statics_written 651 != all_module_statics) 652 { 653 if (y_global->statics_written 654 == all_module_statics) 655 { 656 BITMAP_FREE (x_global->statics_written); 657 x_global->statics_written 658 = all_module_statics; 659 } 660 /* Skip bitmaps that are pointer equal to node's bitmap 661 (no reason to spin within the cycle). */ 662 else if (x_global->statics_written 663 != y_global->statics_written) 664 bitmap_ior_into (x_global->statics_written, 665 y_global->statics_written); 666 } 667 } 668 else 669 { 670 gcc_unreachable (); 671 } 672 } 673 } 674} 675 676/* Look at all of the callees of X to see which ones represent inlined 677 calls. For each of these callees, merge their local info into 678 TARGET and check their children recursively. 679 680 This function goes away when Jan changes the inliner and IPA 681 analysis so that this is not run between the time when inlining 682 decisions are made and when the inlining actually occurs. */ 683 684static void 685merge_callee_local_info (struct cgraph_node *target, 686 struct cgraph_node *x) 687{ 688 struct cgraph_edge *e; 689 ipa_reference_local_vars_info_t x_l = 690 get_reference_vars_info_from_cgraph (target)->local; 691 692 /* Make the world safe for tail recursion. */ 693 struct ipa_dfs_info *node_info = x->aux; 694 695 if (node_info->aux) 696 return; 697 698 node_info->aux = x; 699 700 for (e = x->callees; e; e = e->next_callee) 701 { 702 struct cgraph_node *y = e->callee; 703 if (y->global.inlined_to) 704 { 705 ipa_reference_vars_info_t y_info; 706 ipa_reference_local_vars_info_t y_l; 707 struct cgraph_node* orig_y = y; 708 709 y = cgraph_master_clone (y); 710 if (y) 711 { 712 y_info = get_reference_vars_info_from_cgraph (y); 713 y_l = y_info->local; 714 if (x_l != y_l) 715 { 716 bitmap_ior_into (x_l->statics_read, 717 y_l->statics_read); 718 bitmap_ior_into (x_l->statics_written, 719 y_l->statics_written); 720 } 721 x_l->calls_read_all |= y_l->calls_read_all; 722 x_l->calls_write_all |= y_l->calls_write_all; 723 merge_callee_local_info (target, y); 724 } 725 else 726 { 727 fprintf(stderr, "suspect inlining of "); 728 dump_cgraph_node (stderr, orig_y); 729 fprintf(stderr, "\ninto "); 730 dump_cgraph_node (stderr, target); 731 dump_cgraph (stderr); 732 gcc_assert(false); 733 } 734 } 735 } 736 737 node_info->aux = NULL; 738} 739 740/* The init routine for analyzing global static variable usage. See 741 comments at top for description. */ 742static void 743ipa_init (void) 744{ 745 struct cgraph_node *node; 746 memory_identifier_string = build_string(7, "memory"); 747 748 reference_vars_to_consider = 749 splay_tree_new_ggc (splay_tree_compare_ints); 750 751 bitmap_obstack_initialize (&ipa_obstack); 752 module_statics_escape = BITMAP_ALLOC (&ipa_obstack); 753 module_statics_written = BITMAP_ALLOC (&ipa_obstack); 754 all_module_statics = BITMAP_ALLOC (&ipa_obstack); 755 756 /* This will add NODE->DECL to the splay trees. */ 757 for (node = cgraph_nodes; node; node = node->next) 758 has_proper_scope_for_analysis (node->decl); 759 760 /* There are some shared nodes, in particular the initializers on 761 static declarations. We do not need to scan them more than once 762 since all we would be interested in are the addressof 763 operations. */ 764 visited_nodes = pointer_set_create (); 765} 766 767/* Check out the rhs of a static or global initialization VNODE to see 768 if any of them contain addressof operations. Note that some of 769 these variables may not even be referenced in the code in this 770 compilation unit but their right hand sides may contain references 771 to variables defined within this unit. */ 772 773static void 774analyze_variable (struct cgraph_varpool_node *vnode) 775{ 776 tree global = vnode->decl; 777 if (TREE_CODE (global) == VAR_DECL) 778 { 779 if (DECL_INITIAL (global)) 780 walk_tree (&DECL_INITIAL (global), scan_for_static_refs, 781 NULL, visited_nodes); 782 } 783 else gcc_unreachable (); 784} 785 786/* This is the main routine for finding the reference patterns for 787 global variables within a function FN. */ 788 789static void 790analyze_function (struct cgraph_node *fn) 791{ 792 ipa_reference_vars_info_t info 793 = xcalloc (1, sizeof (struct ipa_reference_vars_info_d)); 794 ipa_reference_local_vars_info_t l 795 = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d)); 796 tree decl = fn->decl; 797 798 /* Add the info to the tree's annotation. */ 799 get_function_ann (fn->decl)->reference_vars_info = info; 800 801 info->local = l; 802 l->statics_read = BITMAP_ALLOC (&ipa_obstack); 803 l->statics_written = BITMAP_ALLOC (&ipa_obstack); 804 805 if (dump_file) 806 fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn)); 807 808 { 809 struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 810 basic_block this_block; 811 812 FOR_EACH_BB_FN (this_block, this_cfun) 813 { 814 block_stmt_iterator bsi; 815 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 816 walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs, 817 fn, visited_nodes); 818 } 819 } 820 821 /* There may be const decls with interesting right hand sides. */ 822 if (DECL_STRUCT_FUNCTION (decl)) 823 { 824 tree step; 825 for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; 826 step; 827 step = TREE_CHAIN (step)) 828 { 829 tree var = TREE_VALUE (step); 830 if (TREE_CODE (var) == VAR_DECL 831 && DECL_INITIAL (var) 832 && !TREE_STATIC (var)) 833 walk_tree (&DECL_INITIAL (var), scan_for_static_refs, 834 fn, visited_nodes); 835 } 836 } 837} 838 839/* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit 840 vectors with worst case bit vectors. We had to analyze it above to 841 find out if it took the address of any statics. However, now that 842 we know that, we can get rid of all of the other side effects. */ 843 844static void 845clean_function (struct cgraph_node *fn) 846{ 847 ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn); 848 ipa_reference_local_vars_info_t l = info->local; 849 ipa_reference_global_vars_info_t g = info->global; 850 851 if (l) 852 { 853 if (l->statics_read 854 && l->statics_read != all_module_statics) 855 BITMAP_FREE (l->statics_read); 856 if (l->statics_written 857 &&l->statics_written != all_module_statics) 858 BITMAP_FREE (l->statics_written); 859 free (l); 860 } 861 862 if (g) 863 { 864 if (g->statics_read 865 && g->statics_read != all_module_statics) 866 BITMAP_FREE (g->statics_read); 867 868 if (g->statics_written 869 && g->statics_written != all_module_statics) 870 BITMAP_FREE (g->statics_written); 871 872 if (g->statics_not_read 873 && g->statics_not_read != all_module_statics) 874 BITMAP_FREE (g->statics_not_read); 875 876 if (g->statics_not_written 877 && g->statics_not_written != all_module_statics) 878 BITMAP_FREE (g->statics_not_written); 879 free (g); 880 } 881 882 883 free (get_function_ann (fn->decl)->reference_vars_info); 884 get_function_ann (fn->decl)->reference_vars_info = NULL; 885} 886 887 888/* Produce the global information by preforming a transitive closure 889 on the local information that was produced by ipa_analyze_function 890 and ipa_analyze_variable. */ 891 892static unsigned int 893static_execute (void) 894{ 895 struct cgraph_node *node; 896 struct cgraph_varpool_node *vnode; 897 struct cgraph_node *w; 898 struct cgraph_node **order = 899 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); 900 int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true); 901 int i; 902 903 ipa_init (); 904 905 /* Process all of the variables first. */ 906 for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) 907 analyze_variable (vnode); 908 909 /* Process all of the functions next. 910 911 We do not want to process any of the clones so we check that this 912 is a master clone. However, we do need to process any 913 AVAIL_OVERWRITABLE functions (these are never clones) because 914 they may cause a static variable to escape. The code that can 915 overwrite such a function cannot access the statics because it 916 would not be in the same compilation unit. When the analysis is 917 finished, the computed information of these AVAIL_OVERWRITABLE is 918 replaced with worst case info. 919 */ 920 for (node = cgraph_nodes; node; node = node->next) 921 if (node->analyzed 922 && (cgraph_is_master_clone (node) 923 || (cgraph_function_body_availability (node) 924 == AVAIL_OVERWRITABLE))) 925 analyze_function (node); 926 927 pointer_set_destroy (visited_nodes); 928 visited_nodes = NULL; 929 if (dump_file) 930 dump_cgraph (dump_file); 931 932 /* Prune out the variables that were found to behave badly 933 (i.e. have their address taken). */ 934 { 935 unsigned int index; 936 bitmap_iterator bi; 937 bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack); 938 bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack); 939 bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack); 940 941 EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi) 942 { 943 splay_tree_remove (reference_vars_to_consider, index); 944 } 945 946 bitmap_and_compl_into (all_module_statics, 947 module_statics_escape); 948 949 bitmap_and_compl (module_statics_readonly, all_module_statics, 950 module_statics_written); 951 952 /* If the address is not taken, we can unset the addressable bit 953 on this variable. */ 954 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) 955 { 956 tree var = get_static_decl (index); 957 TREE_ADDRESSABLE (var) = 0; 958 if (dump_file) 959 fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n", 960 get_static_name (index)); 961 } 962 963 /* If the variable is never written, we can set the TREE_READONLY 964 flag. Additionally if it has a DECL_INITIAL that is made up of 965 constants we can treat the entire global as a constant. */ 966 967 bitmap_and_compl (module_statics_readonly, all_module_statics, 968 module_statics_written); 969 EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi) 970 { 971 tree var = get_static_decl (index); 972 973 /* Readonly on a function decl is very different from the 974 variable. */ 975 if (TREE_CODE (var) == FUNCTION_DECL) 976 continue; 977 978 /* Ignore variables in named sections - changing TREE_READONLY 979 changes the section flags, potentially causing conflicts with 980 other variables in the same named section. */ 981 if (DECL_SECTION_NAME (var) == NULL_TREE) 982 { 983 TREE_READONLY (var) = 1; 984 if (dump_file) 985 fprintf (dump_file, "read-only var %s\n", 986 get_static_name (index)); 987 } 988 if (DECL_INITIAL (var) 989 && is_gimple_min_invariant (DECL_INITIAL (var))) 990 { 991 bitmap_set_bit (module_statics_const, index); 992 if (dump_file) 993 fprintf (dump_file, "read-only constant %s\n", 994 get_static_name (index)); 995 } 996 } 997 998 BITMAP_FREE(module_statics_escape); 999 BITMAP_FREE(module_statics_written); 1000 1001 if (dump_file) 1002 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) 1003 { 1004 fprintf (dump_file, "\nPromotable global:%s", 1005 get_static_name (index)); 1006 } 1007 1008 for (i = 0; i < order_pos; i++ ) 1009 { 1010 ipa_reference_local_vars_info_t l; 1011 node = order[i]; 1012 l = get_reference_vars_info_from_cgraph (node)->local; 1013 1014 /* Any variables that are not in all_module_statics are 1015 removed from the local maps. This will include all of the 1016 variables that were found to escape in the function 1017 scanning. */ 1018 bitmap_and_into (l->statics_read, 1019 all_module_statics); 1020 bitmap_and_into (l->statics_written, 1021 all_module_statics); 1022 } 1023 1024 BITMAP_FREE(module_statics_readonly); 1025 BITMAP_FREE(module_statics_const); 1026 BITMAP_FREE(bm_temp); 1027 } 1028 1029 if (dump_file) 1030 { 1031 for (i = 0; i < order_pos; i++ ) 1032 { 1033 unsigned int index; 1034 ipa_reference_local_vars_info_t l; 1035 bitmap_iterator bi; 1036 1037 node = order[i]; 1038 l = get_reference_vars_info_from_cgraph (node)->local; 1039 fprintf (dump_file, 1040 "\nFunction name:%s/%i:", 1041 cgraph_node_name (node), node->uid); 1042 fprintf (dump_file, "\n locals read: "); 1043 EXECUTE_IF_SET_IN_BITMAP (l->statics_read, 1044 0, index, bi) 1045 { 1046 fprintf (dump_file, "%s ", 1047 get_static_name (index)); 1048 } 1049 fprintf (dump_file, "\n locals written: "); 1050 EXECUTE_IF_SET_IN_BITMAP (l->statics_written, 1051 0, index, bi) 1052 { 1053 fprintf(dump_file, "%s ", 1054 get_static_name (index)); 1055 } 1056 } 1057 } 1058 1059 /* Propagate the local information thru the call graph to produce 1060 the global information. All the nodes within a cycle will have 1061 the same info so we collapse cycles first. Then we can do the 1062 propagation in one pass from the leaves to the roots. */ 1063 order_pos = ipa_utils_reduced_inorder (order, true, true); 1064 if (dump_file) 1065 ipa_utils_print_order(dump_file, "reduced", order, order_pos); 1066 1067 for (i = 0; i < order_pos; i++ ) 1068 { 1069 ipa_reference_vars_info_t node_info; 1070 ipa_reference_global_vars_info_t node_g = 1071 xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d)); 1072 ipa_reference_local_vars_info_t node_l; 1073 1074 bool read_all; 1075 bool write_all; 1076 struct ipa_dfs_info * w_info; 1077 1078 node = order[i]; 1079 node_info = get_reference_vars_info_from_cgraph (node); 1080 if (!node_info) 1081 { 1082 dump_cgraph_node (stderr, node); 1083 dump_cgraph (stderr); 1084 gcc_unreachable (); 1085 } 1086 1087 node_info->global = node_g; 1088 node_l = node_info->local; 1089 1090 read_all = node_l->calls_read_all; 1091 write_all = node_l->calls_write_all; 1092 1093 /* If any node in a cycle is calls_read_all or calls_write_all 1094 they all are. */ 1095 w_info = node->aux; 1096 w = w_info->next_cycle; 1097 while (w) 1098 { 1099 ipa_reference_local_vars_info_t w_l = 1100 get_reference_vars_info_from_cgraph (w)->local; 1101 read_all |= w_l->calls_read_all; 1102 write_all |= w_l->calls_write_all; 1103 1104 w_info = w->aux; 1105 w = w_info->next_cycle; 1106 } 1107 1108 /* Initialized the bitmaps for the reduced nodes */ 1109 if (read_all) 1110 node_g->statics_read = all_module_statics; 1111 else 1112 { 1113 node_g->statics_read = BITMAP_ALLOC (&ipa_obstack); 1114 bitmap_copy (node_g->statics_read, 1115 node_l->statics_read); 1116 } 1117 1118 if (write_all) 1119 node_g->statics_written = all_module_statics; 1120 else 1121 { 1122 node_g->statics_written = BITMAP_ALLOC (&ipa_obstack); 1123 bitmap_copy (node_g->statics_written, 1124 node_l->statics_written); 1125 } 1126 1127 w_info = node->aux; 1128 w = w_info->next_cycle; 1129 while (w) 1130 { 1131 ipa_reference_vars_info_t w_ri = 1132 get_reference_vars_info_from_cgraph (w); 1133 ipa_reference_local_vars_info_t w_l = w_ri->local; 1134 1135 /* All nodes within a cycle share the same global info bitmaps. */ 1136 w_ri->global = node_g; 1137 1138 /* These global bitmaps are initialized from the local info 1139 of all of the nodes in the region. However there is no 1140 need to do any work if the bitmaps were set to 1141 all_module_statics. */ 1142 if (!read_all) 1143 bitmap_ior_into (node_g->statics_read, 1144 w_l->statics_read); 1145 if (!write_all) 1146 bitmap_ior_into (node_g->statics_written, 1147 w_l->statics_written); 1148 w_info = w->aux; 1149 w = w_info->next_cycle; 1150 } 1151 1152 w = node; 1153 while (w) 1154 { 1155 propagate_bits (w); 1156 w_info = w->aux; 1157 w = w_info->next_cycle; 1158 } 1159 } 1160 1161 /* Need to fix up the local information sets. The information that 1162 has been gathered so far is preinlining. However, the 1163 compilation will progress post inlining so the local sets for the 1164 inlined calls need to be merged into the callers. Note that the 1165 local sets are not shared between all of the nodes in a cycle so 1166 those nodes in the cycle must be processed explicitly. */ 1167 for (i = 0; i < order_pos; i++ ) 1168 { 1169 struct ipa_dfs_info * w_info; 1170 node = order[i]; 1171 merge_callee_local_info (node, node); 1172 1173 w_info = node->aux; 1174 w = w_info->next_cycle; 1175 while (w) 1176 { 1177 merge_callee_local_info (w, w); 1178 w_info = w->aux; 1179 w = w_info->next_cycle; 1180 } 1181 } 1182 1183 if (dump_file) 1184 { 1185 for (i = 0; i < order_pos; i++ ) 1186 { 1187 ipa_reference_vars_info_t node_info; 1188 ipa_reference_global_vars_info_t node_g; 1189 ipa_reference_local_vars_info_t node_l; 1190 unsigned int index; 1191 bitmap_iterator bi; 1192 struct ipa_dfs_info * w_info; 1193 1194 node = order[i]; 1195 node_info = get_reference_vars_info_from_cgraph (node); 1196 node_g = node_info->global; 1197 node_l = node_info->local; 1198 fprintf (dump_file, 1199 "\nFunction name:%s/%i:", 1200 cgraph_node_name (node), node->uid); 1201 fprintf (dump_file, "\n locals read: "); 1202 EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read, 1203 0, index, bi) 1204 { 1205 fprintf (dump_file, "%s ", 1206 get_static_name (index)); 1207 } 1208 fprintf (dump_file, "\n locals written: "); 1209 EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written, 1210 0, index, bi) 1211 { 1212 fprintf(dump_file, "%s ", 1213 get_static_name (index)); 1214 } 1215 1216 w_info = node->aux; 1217 w = w_info->next_cycle; 1218 while (w) 1219 { 1220 ipa_reference_vars_info_t w_ri = 1221 get_reference_vars_info_from_cgraph (w); 1222 ipa_reference_local_vars_info_t w_l = w_ri->local; 1223 fprintf (dump_file, "\n next cycle: %s/%i ", 1224 cgraph_node_name (w), w->uid); 1225 fprintf (dump_file, "\n locals read: "); 1226 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read, 1227 0, index, bi) 1228 { 1229 fprintf (dump_file, "%s ", 1230 get_static_name (index)); 1231 } 1232 1233 fprintf (dump_file, "\n locals written: "); 1234 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written, 1235 0, index, bi) 1236 { 1237 fprintf(dump_file, "%s ", 1238 get_static_name (index)); 1239 } 1240 1241 1242 w_info = w->aux; 1243 w = w_info->next_cycle; 1244 } 1245 fprintf (dump_file, "\n globals read: "); 1246 EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read, 1247 0, index, bi) 1248 { 1249 fprintf (dump_file, "%s ", 1250 get_static_name (index)); 1251 } 1252 fprintf (dump_file, "\n globals written: "); 1253 EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written, 1254 0, index, bi) 1255 { 1256 fprintf (dump_file, "%s ", 1257 get_static_name (index)); 1258 } 1259 } 1260 } 1261 1262 /* Cleanup. */ 1263 for (i = 0; i < order_pos; i++ ) 1264 { 1265 ipa_reference_vars_info_t node_info; 1266 ipa_reference_global_vars_info_t node_g; 1267 node = order[i]; 1268 node_info = get_reference_vars_info_from_cgraph (node); 1269 node_g = node_info->global; 1270 1271 /* Create the complimentary sets. These are more useful for 1272 certain apis. */ 1273 node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack); 1274 node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack); 1275 1276 if (node_g->statics_read != all_module_statics) 1277 { 1278 bitmap_and_compl (node_g->statics_not_read, 1279 all_module_statics, 1280 node_g->statics_read); 1281 } 1282 1283 if (node_g->statics_written 1284 != all_module_statics) 1285 bitmap_and_compl (node_g->statics_not_written, 1286 all_module_statics, 1287 node_g->statics_written); 1288 } 1289 1290 free (order); 1291 1292 for (node = cgraph_nodes; node; node = node->next) 1293 { 1294 /* Get rid of the aux information. */ 1295 1296 if (node->aux) 1297 { 1298 free (node->aux); 1299 node->aux = NULL; 1300 } 1301 1302 if (node->analyzed 1303 && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)) 1304 clean_function (node); 1305 } 1306 return 0; 1307} 1308 1309 1310static bool 1311gate_reference (void) 1312{ 1313 return (flag_unit_at_a_time != 0 && flag_ipa_reference 1314 /* Don't bother doing anything if the program has errors. */ 1315 && !(errorcount || sorrycount)); 1316} 1317 1318struct tree_opt_pass pass_ipa_reference = 1319{ 1320 "static-var", /* name */ 1321 gate_reference, /* gate */ 1322 static_execute, /* execute */ 1323 NULL, /* sub */ 1324 NULL, /* next */ 1325 0, /* static_pass_number */ 1326 TV_IPA_REFERENCE, /* tv_id */ 1327 0, /* properties_required */ 1328 0, /* properties_provided */ 1329 0, /* properties_destroyed */ 1330 0, /* todo_flags_start */ 1331 0, /* todo_flags_finish */ 1332 0 /* letter */ 1333}; 1334 1335#include "gt-ipa-reference.h" 1336 1337