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_var_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_var_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_var_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) 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) 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 { 511 tree op0 = TREE_OPERAND (rhs, 0); 512 tree op1 = TREE_OPERAND (rhs, 1); 513 check_rhs_var (local, op0); 514 check_rhs_var (local, op1); 515 } 516 break; 517 case tcc_unary: 518 { 519 tree op0 = TREE_OPERAND (rhs, 0); 520 check_rhs_var (local, op0); 521 } 522 523 break; 524 case tcc_reference: 525 check_rhs_var (local, rhs); 526 break; 527 case tcc_declaration: 528 check_rhs_var (local, rhs); 529 break; 530 case tcc_expression: 531 switch (TREE_CODE (rhs)) 532 { 533 case ADDR_EXPR: 534 check_rhs_var (local, rhs); 535 break; 536 case CALL_EXPR: 537 check_call (local, rhs); 538 break; 539 default: 540 break; 541 } 542 break; 543 default: 544 break; 545 } 546 *walk_subtrees = 0; 547 } 548 break; 549 550 case ADDR_EXPR: 551 /* This case is here to find addresses on rhs of constructors in 552 decl_initial of static variables. */ 553 check_rhs_var (local, t); 554 *walk_subtrees = 0; 555 break; 556 557 case LABEL_EXPR: 558 if (DECL_NONLOCAL (TREE_OPERAND (t, 0))) 559 { 560 /* Target of long jump. */ 561 local->calls_read_all = true; 562 local->calls_write_all = true; 563 } 564 break; 565 566 case CALL_EXPR: 567 check_call (local, t); 568 *walk_subtrees = 0; 569 break; 570 571 case ASM_EXPR: 572 get_asm_expr_operands (local, t); 573 *walk_subtrees = 0; 574 break; 575 576 default: 577 break; 578 } 579 return NULL; 580} 581 582 583/* Lookup the tree node for the static variable that has UID. */ 584static tree 585get_static_decl (int index) 586{ 587 splay_tree_node stn = 588 splay_tree_lookup (reference_vars_to_consider, index); 589 if (stn) 590 return (tree)stn->value; 591 return NULL; 592} 593 594/* Lookup the tree node for the static variable that has UID and 595 convert the name to a string for debugging. */ 596 597static const char * 598get_static_name (int index) 599{ 600 splay_tree_node stn = 601 splay_tree_lookup (reference_vars_to_consider, index); 602 if (stn) 603 return lang_hooks.decl_printable_name ((tree)(stn->value), 2); 604 return NULL; 605} 606 607/* Or in all of the bits from every callee into X, the caller's, bit 608 vector. There are several cases to check to avoid the sparse 609 bitmap oring. */ 610 611static void 612propagate_bits (struct cgraph_node *x) 613{ 614 ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x); 615 ipa_reference_global_vars_info_t x_global = x_info->global; 616 617 struct cgraph_edge *e; 618 for (e = x->callees; e; e = e->next_callee) 619 { 620 struct cgraph_node *y = e->callee; 621 622 /* Only look at the master nodes and skip external nodes. */ 623 y = cgraph_master_clone (y); 624 if (y) 625 { 626 if (get_reference_vars_info_from_cgraph (y)) 627 { 628 ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y); 629 ipa_reference_global_vars_info_t y_global = y_info->global; 630 631 if (x_global->statics_read 632 != all_module_statics) 633 { 634 if (y_global->statics_read 635 == all_module_statics) 636 { 637 BITMAP_FREE (x_global->statics_read); 638 x_global->statics_read 639 = all_module_statics; 640 } 641 /* Skip bitmaps that are pointer equal to node's bitmap 642 (no reason to spin within the cycle). */ 643 else if (x_global->statics_read 644 != y_global->statics_read) 645 bitmap_ior_into (x_global->statics_read, 646 y_global->statics_read); 647 } 648 649 if (x_global->statics_written 650 != all_module_statics) 651 { 652 if (y_global->statics_written 653 == all_module_statics) 654 { 655 BITMAP_FREE (x_global->statics_written); 656 x_global->statics_written 657 = all_module_statics; 658 } 659 /* Skip bitmaps that are pointer equal to node's bitmap 660 (no reason to spin within the cycle). */ 661 else if (x_global->statics_written 662 != y_global->statics_written) 663 bitmap_ior_into (x_global->statics_written, 664 y_global->statics_written); 665 } 666 } 667 else 668 { 669 gcc_unreachable (); 670 } 671 } 672 } 673} 674 675/* Look at all of the callees of X to see which ones represent inlined 676 calls. For each of these callees, merge their local info into 677 TARGET and check their children recursively. 678 679 This function goes away when Jan changes the inliner and IPA 680 analysis so that this is not run between the time when inlining 681 decisions are made and when the inlining actually occurs. */ 682 683static void 684merge_callee_local_info (struct cgraph_node *target, 685 struct cgraph_node *x) 686{ 687 struct cgraph_edge *e; 688 ipa_reference_local_vars_info_t x_l = 689 get_reference_vars_info_from_cgraph (target)->local; 690 691 /* Make the world safe for tail recursion. */ 692 struct ipa_dfs_info *node_info = x->aux; 693 694 if (node_info->aux) 695 return; 696 697 node_info->aux = x; 698 699 for (e = x->callees; e; e = e->next_callee) 700 { 701 struct cgraph_node *y = e->callee; 702 if (y->global.inlined_to) 703 { 704 ipa_reference_vars_info_t y_info; 705 ipa_reference_local_vars_info_t y_l; 706 struct cgraph_node* orig_y = y; 707 708 y = cgraph_master_clone (y); 709 if (y) 710 { 711 y_info = get_reference_vars_info_from_cgraph (y); 712 y_l = y_info->local; 713 if (x_l != y_l) 714 { 715 bitmap_ior_into (x_l->statics_read, 716 y_l->statics_read); 717 bitmap_ior_into (x_l->statics_written, 718 y_l->statics_written); 719 } 720 x_l->calls_read_all |= y_l->calls_read_all; 721 x_l->calls_write_all |= y_l->calls_write_all; 722 merge_callee_local_info (target, y); 723 } 724 else 725 { 726 fprintf(stderr, "suspect inlining of "); 727 dump_cgraph_node (stderr, orig_y); 728 fprintf(stderr, "\ninto "); 729 dump_cgraph_node (stderr, target); 730 dump_cgraph (stderr); 731 gcc_assert(false); 732 } 733 } 734 } 735 736 node_info->aux = NULL; 737} 738 739/* The init routine for analyzing global static variable usage. See 740 comments at top for description. */ 741static void 742ipa_init (void) 743{ 744 memory_identifier_string = build_string(7, "memory"); 745 746 reference_vars_to_consider = 747 splay_tree_new_ggc (splay_tree_compare_ints); 748 749 bitmap_obstack_initialize (&ipa_obstack); 750 module_statics_escape = BITMAP_ALLOC (&ipa_obstack); 751 module_statics_written = BITMAP_ALLOC (&ipa_obstack); 752 all_module_statics = BITMAP_ALLOC (&ipa_obstack); 753 754 /* There are some shared nodes, in particular the initializers on 755 static declarations. We do not need to scan them more than once 756 since all we would be interested in are the addressof 757 operations. */ 758 visited_nodes = pointer_set_create (); 759} 760 761/* Check out the rhs of a static or global initialization VNODE to see 762 if any of them contain addressof operations. Note that some of 763 these variables may not even be referenced in the code in this 764 compilation unit but their right hand sides may contain references 765 to variables defined within this unit. */ 766 767static void 768analyze_variable (struct cgraph_varpool_node *vnode) 769{ 770 tree global = vnode->decl; 771 if (TREE_CODE (global) == VAR_DECL) 772 { 773 if (DECL_INITIAL (global)) 774 walk_tree (&DECL_INITIAL (global), scan_for_static_refs, 775 NULL, visited_nodes); 776 } 777 else gcc_unreachable (); 778} 779 780/* This is the main routine for finding the reference patterns for 781 global variables within a function FN. */ 782 783static void 784analyze_function (struct cgraph_node *fn) 785{ 786 ipa_reference_vars_info_t info 787 = xcalloc (1, sizeof (struct ipa_reference_vars_info_d)); 788 ipa_reference_local_vars_info_t l 789 = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d)); 790 tree decl = fn->decl; 791 792 /* Add the info to the tree's annotation. */ 793 get_var_ann (fn->decl)->reference_vars_info = info; 794 795 info->local = l; 796 l->statics_read = BITMAP_ALLOC (&ipa_obstack); 797 l->statics_written = BITMAP_ALLOC (&ipa_obstack); 798 799 if (dump_file) 800 fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn)); 801 802 { 803 struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 804 basic_block this_block; 805 806 FOR_EACH_BB_FN (this_block, this_cfun) 807 { 808 block_stmt_iterator bsi; 809 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 810 walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs, 811 fn, visited_nodes); 812 } 813 } 814 815 /* There may be const decls with interesting right hand sides. */ 816 if (DECL_STRUCT_FUNCTION (decl)) 817 { 818 tree step; 819 for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; 820 step; 821 step = TREE_CHAIN (step)) 822 { 823 tree var = TREE_VALUE (step); 824 if (TREE_CODE (var) == VAR_DECL 825 && DECL_INITIAL (var) 826 && !TREE_STATIC (var)) 827 walk_tree (&DECL_INITIAL (var), scan_for_static_refs, 828 fn, visited_nodes); 829 } 830 } 831} 832 833/* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit 834 vectors with worst case bit vectors. We had to analyze it above to 835 find out if it took the address of any statics. However, now that 836 we know that, we can get rid of all of the other side effects. */ 837 838static void 839clean_function (struct cgraph_node *fn) 840{ 841 ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn); 842 ipa_reference_local_vars_info_t l = info->local; 843 ipa_reference_global_vars_info_t g = info->global; 844 845 if (l) 846 { 847 if (l->statics_read 848 && l->statics_read != all_module_statics) 849 BITMAP_FREE (l->statics_read); 850 if (l->statics_written 851 &&l->statics_written != all_module_statics) 852 BITMAP_FREE (l->statics_written); 853 free (l); 854 } 855 856 if (g) 857 { 858 if (g->statics_read 859 && g->statics_read != all_module_statics) 860 BITMAP_FREE (g->statics_read); 861 862 if (g->statics_written 863 && g->statics_written != all_module_statics) 864 BITMAP_FREE (g->statics_written); 865 866 if (g->statics_not_read 867 && g->statics_not_read != all_module_statics) 868 BITMAP_FREE (g->statics_not_read); 869 870 if (g->statics_not_written 871 && g->statics_not_written != all_module_statics) 872 BITMAP_FREE (g->statics_not_written); 873 free (g); 874 } 875 876 877 free (get_var_ann (fn->decl)->reference_vars_info); 878 get_var_ann (fn->decl)->reference_vars_info = NULL; 879} 880 881 882/* Produce the global information by preforming a transitive closure 883 on the local information that was produced by ipa_analyze_function 884 and ipa_analyze_variable. */ 885 886static void 887static_execute (void) 888{ 889 struct cgraph_node *node; 890 struct cgraph_varpool_node *vnode; 891 struct cgraph_node *w; 892 struct cgraph_node **order = 893 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); 894 int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true); 895 int i; 896 897 ipa_init (); 898 899 /* Process all of the variables first. */ 900 for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) 901 analyze_variable (vnode); 902 903 /* Process all of the functions next. 904 905 We do not want to process any of the clones so we check that this 906 is a master clone. However, we do need to process any 907 AVAIL_OVERWRITABLE functions (these are never clones) because 908 they may cause a static variable to escape. The code that can 909 overwrite such a function cannot access the statics because it 910 would not be in the same compilation unit. When the analysis is 911 finished, the computed information of these AVAIL_OVERWRITABLE is 912 replaced with worst case info. 913 */ 914 for (node = cgraph_nodes; node; node = node->next) 915 if (node->analyzed 916 && (cgraph_is_master_clone (node) 917 || (cgraph_function_body_availability (node) 918 == AVAIL_OVERWRITABLE))) 919 analyze_function (node); 920 921 pointer_set_destroy (visited_nodes); 922 visited_nodes = NULL; 923 if (dump_file) 924 dump_cgraph (dump_file); 925 926 /* Prune out the variables that were found to behave badly 927 (i.e. have their address taken). */ 928 { 929 unsigned int index; 930 bitmap_iterator bi; 931 bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack); 932 bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack); 933 bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack); 934 935 EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi) 936 { 937 splay_tree_remove (reference_vars_to_consider, index); 938 } 939 940 bitmap_and_compl_into (all_module_statics, 941 module_statics_escape); 942 943 bitmap_and_compl (module_statics_readonly, all_module_statics, 944 module_statics_written); 945 946 /* If the address is not taken, we can unset the addressable bit 947 on this variable. */ 948 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) 949 { 950 tree var = get_static_decl (index); 951 TREE_ADDRESSABLE (var) = 0; 952 if (dump_file) 953 fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n", 954 get_static_name (index)); 955 } 956 957 /* If the variable is never written, we can set the TREE_READONLY 958 flag. Additionally if it has a DECL_INITIAL that is made up of 959 constants we can treat the entire global as a constant. */ 960 961 bitmap_and_compl (module_statics_readonly, all_module_statics, 962 module_statics_written); 963 EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi) 964 { 965 tree var = get_static_decl (index); 966 967 /* Ignore variables in named sections - changing TREE_READONLY 968 changes the section flags, potentially causing conflicts with 969 other variables in the same named section. */ 970 if (DECL_SECTION_NAME (var) == NULL_TREE) 971 { 972 TREE_READONLY (var) = 1; 973 if (dump_file) 974 fprintf (dump_file, "read-only var %s\n", 975 get_static_name (index)); 976 } 977 if (DECL_INITIAL (var) 978 && is_gimple_min_invariant (DECL_INITIAL (var))) 979 { 980 bitmap_set_bit (module_statics_const, index); 981 if (dump_file) 982 fprintf (dump_file, "read-only constant %s\n", 983 get_static_name (index)); 984 } 985 } 986 987 BITMAP_FREE(module_statics_escape); 988 BITMAP_FREE(module_statics_written); 989 990 if (dump_file) 991 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) 992 { 993 fprintf (dump_file, "\nPromotable global:%s", 994 get_static_name (index)); 995 } 996 997 for (i = 0; i < order_pos; i++ ) 998 { 999 ipa_reference_local_vars_info_t l; 1000 node = order[i]; 1001 l = get_reference_vars_info_from_cgraph (node)->local; 1002 1003 /* Any variables that are not in all_module_statics are 1004 removed from the local maps. This will include all of the 1005 variables that were found to escape in the function 1006 scanning. */ 1007 bitmap_and_into (l->statics_read, 1008 all_module_statics); 1009 bitmap_and_into (l->statics_written, 1010 all_module_statics); 1011 } 1012 1013 BITMAP_FREE(module_statics_readonly); 1014 BITMAP_FREE(module_statics_const); 1015 BITMAP_FREE(bm_temp); 1016 } 1017 1018 if (dump_file) 1019 { 1020 for (i = 0; i < order_pos; i++ ) 1021 { 1022 unsigned int index; 1023 ipa_reference_local_vars_info_t l; 1024 bitmap_iterator bi; 1025 1026 node = order[i]; 1027 l = get_reference_vars_info_from_cgraph (node)->local; 1028 fprintf (dump_file, 1029 "\nFunction name:%s/%i:", 1030 cgraph_node_name (node), node->uid); 1031 fprintf (dump_file, "\n locals read: "); 1032 EXECUTE_IF_SET_IN_BITMAP (l->statics_read, 1033 0, index, bi) 1034 { 1035 fprintf (dump_file, "%s ", 1036 get_static_name (index)); 1037 } 1038 fprintf (dump_file, "\n locals written: "); 1039 EXECUTE_IF_SET_IN_BITMAP (l->statics_written, 1040 0, index, bi) 1041 { 1042 fprintf(dump_file, "%s ", 1043 get_static_name (index)); 1044 } 1045 } 1046 } 1047 1048 /* Propagate the local information thru the call graph to produce 1049 the global information. All the nodes within a cycle will have 1050 the same info so we collapse cycles first. Then we can do the 1051 propagation in one pass from the leaves to the roots. */ 1052 order_pos = ipa_utils_reduced_inorder (order, true, true); 1053 if (dump_file) 1054 ipa_utils_print_order(dump_file, "reduced", order, order_pos); 1055 1056 for (i = 0; i < order_pos; i++ ) 1057 { 1058 ipa_reference_vars_info_t node_info; 1059 ipa_reference_global_vars_info_t node_g = 1060 xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d)); 1061 ipa_reference_local_vars_info_t node_l; 1062 1063 bool read_all; 1064 bool write_all; 1065 struct ipa_dfs_info * w_info; 1066 1067 node = order[i]; 1068 node_info = get_reference_vars_info_from_cgraph (node); 1069 if (!node_info) 1070 { 1071 dump_cgraph_node (stderr, node); 1072 dump_cgraph (stderr); 1073 gcc_unreachable (); 1074 } 1075 1076 node_info->global = node_g; 1077 node_l = node_info->local; 1078 1079 read_all = node_l->calls_read_all; 1080 write_all = node_l->calls_write_all; 1081 1082 /* If any node in a cycle is calls_read_all or calls_write_all 1083 they all are. */ 1084 w_info = node->aux; 1085 w = w_info->next_cycle; 1086 while (w) 1087 { 1088 ipa_reference_local_vars_info_t w_l = 1089 get_reference_vars_info_from_cgraph (w)->local; 1090 read_all |= w_l->calls_read_all; 1091 write_all |= w_l->calls_write_all; 1092 1093 w_info = w->aux; 1094 w = w_info->next_cycle; 1095 } 1096 1097 /* Initialized the bitmaps for the reduced nodes */ 1098 if (read_all) 1099 node_g->statics_read = all_module_statics; 1100 else 1101 { 1102 node_g->statics_read = BITMAP_ALLOC (&ipa_obstack); 1103 bitmap_copy (node_g->statics_read, 1104 node_l->statics_read); 1105 } 1106 1107 if (write_all) 1108 node_g->statics_written = all_module_statics; 1109 else 1110 { 1111 node_g->statics_written = BITMAP_ALLOC (&ipa_obstack); 1112 bitmap_copy (node_g->statics_written, 1113 node_l->statics_written); 1114 } 1115 1116 w_info = node->aux; 1117 w = w_info->next_cycle; 1118 while (w) 1119 { 1120 ipa_reference_vars_info_t w_ri = 1121 get_reference_vars_info_from_cgraph (w); 1122 ipa_reference_local_vars_info_t w_l = w_ri->local; 1123 1124 /* All nodes within a cycle share the same global info bitmaps. */ 1125 w_ri->global = node_g; 1126 1127 /* These global bitmaps are initialized from the local info 1128 of all of the nodes in the region. However there is no 1129 need to do any work if the bitmaps were set to 1130 all_module_statics. */ 1131 if (!read_all) 1132 bitmap_ior_into (node_g->statics_read, 1133 w_l->statics_read); 1134 if (!write_all) 1135 bitmap_ior_into (node_g->statics_written, 1136 w_l->statics_written); 1137 w_info = w->aux; 1138 w = w_info->next_cycle; 1139 } 1140 1141 w = node; 1142 while (w) 1143 { 1144 propagate_bits (w); 1145 w_info = w->aux; 1146 w = w_info->next_cycle; 1147 } 1148 } 1149 1150 /* Need to fix up the local information sets. The information that 1151 has been gathered so far is preinlining. However, the 1152 compilation will progress post inlining so the local sets for the 1153 inlined calls need to be merged into the callers. Note that the 1154 local sets are not shared between all of the nodes in a cycle so 1155 those nodes in the cycle must be processed explicitly. */ 1156 for (i = 0; i < order_pos; i++ ) 1157 { 1158 struct ipa_dfs_info * w_info; 1159 node = order[i]; 1160 merge_callee_local_info (node, node); 1161 1162 w_info = node->aux; 1163 w = w_info->next_cycle; 1164 while (w) 1165 { 1166 merge_callee_local_info (w, w); 1167 w_info = w->aux; 1168 w = w_info->next_cycle; 1169 } 1170 } 1171 1172 if (dump_file) 1173 { 1174 for (i = 0; i < order_pos; i++ ) 1175 { 1176 ipa_reference_vars_info_t node_info; 1177 ipa_reference_global_vars_info_t node_g; 1178 ipa_reference_local_vars_info_t node_l; 1179 unsigned int index; 1180 bitmap_iterator bi; 1181 struct ipa_dfs_info * w_info; 1182 1183 node = order[i]; 1184 node_info = get_reference_vars_info_from_cgraph (node); 1185 node_g = node_info->global; 1186 node_l = node_info->local; 1187 fprintf (dump_file, 1188 "\nFunction name:%s/%i:", 1189 cgraph_node_name (node), node->uid); 1190 fprintf (dump_file, "\n locals read: "); 1191 EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read, 1192 0, index, bi) 1193 { 1194 fprintf (dump_file, "%s ", 1195 get_static_name (index)); 1196 } 1197 fprintf (dump_file, "\n locals written: "); 1198 EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written, 1199 0, index, bi) 1200 { 1201 fprintf(dump_file, "%s ", 1202 get_static_name (index)); 1203 } 1204 1205 w_info = node->aux; 1206 w = w_info->next_cycle; 1207 while (w) 1208 { 1209 ipa_reference_vars_info_t w_ri = 1210 get_reference_vars_info_from_cgraph (w); 1211 ipa_reference_local_vars_info_t w_l = w_ri->local; 1212 fprintf (dump_file, "\n next cycle: %s/%i ", 1213 cgraph_node_name (w), w->uid); 1214 fprintf (dump_file, "\n locals read: "); 1215 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read, 1216 0, index, bi) 1217 { 1218 fprintf (dump_file, "%s ", 1219 get_static_name (index)); 1220 } 1221 1222 fprintf (dump_file, "\n locals written: "); 1223 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written, 1224 0, index, bi) 1225 { 1226 fprintf(dump_file, "%s ", 1227 get_static_name (index)); 1228 } 1229 1230 1231 w_info = w->aux; 1232 w = w_info->next_cycle; 1233 } 1234 fprintf (dump_file, "\n globals read: "); 1235 EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read, 1236 0, index, bi) 1237 { 1238 fprintf (dump_file, "%s ", 1239 get_static_name (index)); 1240 } 1241 fprintf (dump_file, "\n globals written: "); 1242 EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written, 1243 0, index, bi) 1244 { 1245 fprintf (dump_file, "%s ", 1246 get_static_name (index)); 1247 } 1248 } 1249 } 1250 1251 /* Cleanup. */ 1252 for (i = 0; i < order_pos; i++ ) 1253 { 1254 ipa_reference_vars_info_t node_info; 1255 ipa_reference_global_vars_info_t node_g; 1256 node = order[i]; 1257 node_info = get_reference_vars_info_from_cgraph (node); 1258 node_g = node_info->global; 1259 1260 /* Create the complimentary sets. These are more useful for 1261 certain apis. */ 1262 node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack); 1263 node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack); 1264 1265 if (node_g->statics_read != all_module_statics) 1266 { 1267 bitmap_and_compl (node_g->statics_not_read, 1268 all_module_statics, 1269 node_g->statics_read); 1270 } 1271 1272 if (node_g->statics_written 1273 != all_module_statics) 1274 bitmap_and_compl (node_g->statics_not_written, 1275 all_module_statics, 1276 node_g->statics_written); 1277 } 1278 1279 free (order); 1280 1281 for (node = cgraph_nodes; node; node = node->next) 1282 { 1283 /* Get rid of the aux information. */ 1284 1285 if (node->aux) 1286 { 1287 free (node->aux); 1288 node->aux = NULL; 1289 } 1290 1291 if (node->analyzed 1292 && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)) 1293 clean_function (node); 1294 } 1295} 1296 1297 1298static bool 1299gate_reference (void) 1300{ 1301 return (flag_unit_at_a_time != 0 && flag_ipa_reference 1302 /* Don't bother doing anything if the program has errors. */ 1303 && !(errorcount || sorrycount)); 1304} 1305 1306struct tree_opt_pass pass_ipa_reference = 1307{ 1308 "static-var", /* name */ 1309 gate_reference, /* gate */ 1310 static_execute, /* execute */ 1311 NULL, /* sub */ 1312 NULL, /* next */ 1313 0, /* static_pass_number */ 1314 TV_IPA_REFERENCE, /* tv_id */ 1315 0, /* properties_required */ 1316 0, /* properties_provided */ 1317 0, /* properties_destroyed */ 1318 0, /* todo_flags_start */ 1319 0, /* todo_flags_finish */ 1320 0 /* letter */ 1321}; 1322 1323#include "gt-ipa-reference.h" 1324 1325