1 /* Callgraph based analysis of static variables. 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* This file gathers information about how variables whose scope is 22 confined to the compilation unit are used. 23 24 The transitive call site specific clobber effects are computed 25 for the variables whose scope is contained within this compilation 26 unit. 27 28 First each function and static variable initialization is analyzed 29 to determine which local static variables are either read, written, 30 or have their address taken. Any local static that has its address 31 taken is removed from consideration. Once the local read and 32 writes are determined, a transitive closure of this information is 33 performed over the call graph to determine the worst case set of 34 side effects of each call. In later parts of the compiler, these 35 local and global sets are examined to make the call clobbering less 36 traumatic, promote some statics to registers, and improve aliasing 37 information. */ 38 39 #include "config.h" 40 #include "system.h" 41 #include "coretypes.h" 42 #include "backend.h" 43 #include "tree.h" 44 #include "gimple.h" 45 #include "tree-pass.h" 46 #include "cgraph.h" 47 #include "data-streamer.h" 48 #include "calls.h" 49 #include "splay-tree.h" 50 #include "ipa-utils.h" 51 #include "ipa-reference.h" 52 53 static void remove_node_data (struct cgraph_node *node, 54 void *data ATTRIBUTE_UNUSED); 55 static void duplicate_node_data (struct cgraph_node *src, 56 struct cgraph_node *dst, 57 void *data ATTRIBUTE_UNUSED); 58 59 /* The static variables defined within the compilation unit that are 60 loaded or stored directly by function that owns this structure. */ 61 62 struct ipa_reference_local_vars_info_d 63 { 64 bitmap statics_read; 65 bitmap statics_written; 66 }; 67 68 /* Statics that are read and written by some set of functions. The 69 local ones are based on the loads and stores local to the function. 70 The global ones are based on the local info as well as the 71 transitive closure of the functions that are called. */ 72 73 struct ipa_reference_global_vars_info_d 74 { 75 bitmap statics_read; 76 bitmap statics_written; 77 }; 78 79 /* Information we save about every function after ipa-reference is completed. */ 80 81 struct ipa_reference_optimization_summary_d 82 { 83 bitmap statics_not_read; 84 bitmap statics_not_written; 85 }; 86 87 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t; 88 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t; 89 typedef struct ipa_reference_optimization_summary_d *ipa_reference_optimization_summary_t; 90 91 struct ipa_reference_vars_info_d 92 { 93 struct ipa_reference_local_vars_info_d local; 94 struct ipa_reference_global_vars_info_d global; 95 }; 96 97 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t; 98 99 /* This splay tree contains all of the static variables that are 100 being considered by the compilation level alias analysis. */ 101 static splay_tree reference_vars_to_consider; 102 103 /* Set of all interesting module statics. A bit is set for every module 104 static we are considering. This is added to the local info when asm 105 code is found that clobbers all memory. */ 106 static bitmap all_module_statics; 107 /* Set of all statics that should be ignored because they are touched by 108 -fno-ipa-reference code. */ 109 static bitmap ignore_module_statics; 110 111 /* Obstack holding bitmaps of local analysis (live from analysis to 112 propagation) */ 113 static bitmap_obstack local_info_obstack; 114 /* Obstack holding global analysis live forever. */ 115 static bitmap_obstack optimization_summary_obstack; 116 117 /* Holders of ipa cgraph hooks: */ 118 static struct cgraph_2node_hook_list *node_duplication_hook_holder; 119 static struct cgraph_node_hook_list *node_removal_hook_holder; 120 121 /* Vector where the reference var infos are actually stored. 122 Indexed by UID of call graph nodes. */ 123 static vec<ipa_reference_vars_info_t> ipa_reference_vars_vector; 124 125 /* TODO: find a place where we should release the vector. */ 126 static vec<ipa_reference_optimization_summary_t> ipa_reference_opt_sum_vector; 127 128 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */ 129 static inline ipa_reference_vars_info_t 130 get_reference_vars_info (struct cgraph_node *node) 131 { 132 if (!ipa_reference_vars_vector.exists () 133 || ipa_reference_vars_vector.length () <= (unsigned int) node->uid) 134 return NULL; 135 return ipa_reference_vars_vector[node->uid]; 136 } 137 138 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */ 139 static inline ipa_reference_optimization_summary_t 140 get_reference_optimization_summary (struct cgraph_node *node) 141 { 142 if (!ipa_reference_opt_sum_vector.exists () 143 || (ipa_reference_opt_sum_vector.length () <= (unsigned int) node->uid)) 144 return NULL; 145 return ipa_reference_opt_sum_vector[node->uid]; 146 } 147 148 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */ 149 static inline void 150 set_reference_vars_info (struct cgraph_node *node, 151 ipa_reference_vars_info_t info) 152 { 153 if (!ipa_reference_vars_vector.exists () 154 || ipa_reference_vars_vector.length () <= (unsigned int) node->uid) 155 ipa_reference_vars_vector.safe_grow_cleared (node->uid + 1); 156 ipa_reference_vars_vector[node->uid] = info; 157 } 158 159 /* Return the ipa_reference_vars structure starting from the cgraph NODE. */ 160 static inline void 161 set_reference_optimization_summary (struct cgraph_node *node, 162 ipa_reference_optimization_summary_t info) 163 { 164 if (!ipa_reference_opt_sum_vector.exists () 165 || (ipa_reference_opt_sum_vector.length () <= (unsigned int) node->uid)) 166 ipa_reference_opt_sum_vector.safe_grow_cleared (node->uid + 1); 167 ipa_reference_opt_sum_vector[node->uid] = info; 168 } 169 170 /* Return a bitmap indexed by ipa_reference_var_uid for the static variables 171 that are *not* read during the execution of the function FN. Returns 172 NULL if no data is available. */ 173 174 bitmap 175 ipa_reference_get_not_read_global (struct cgraph_node *fn) 176 { 177 if (!opt_for_fn (current_function_decl, flag_ipa_reference)) 178 return NULL; 179 180 enum availability avail; 181 struct cgraph_node *fn2 = fn->function_symbol (&avail); 182 ipa_reference_optimization_summary_t info = 183 get_reference_optimization_summary (fn2); 184 185 if (info 186 && (avail >= AVAIL_AVAILABLE 187 || (avail == AVAIL_INTERPOSABLE 188 && flags_from_decl_or_type (fn->decl) & ECF_LEAF)) 189 && opt_for_fn (fn2->decl, flag_ipa_reference)) 190 return info->statics_not_read; 191 else if (avail == AVAIL_NOT_AVAILABLE 192 && flags_from_decl_or_type (fn->decl) & ECF_LEAF) 193 return all_module_statics; 194 else 195 return NULL; 196 } 197 198 /* Return a bitmap indexed by ipa_reference_var_uid for the static variables 199 that are *not* written during the execution of the function FN. Note 200 that variables written may or may not be read during the function 201 call. Returns NULL if no data is available. */ 202 203 bitmap 204 ipa_reference_get_not_written_global (struct cgraph_node *fn) 205 { 206 if (!opt_for_fn (current_function_decl, flag_ipa_reference)) 207 return NULL; 208 209 enum availability avail; 210 struct cgraph_node *fn2 = fn->function_symbol (&avail); 211 ipa_reference_optimization_summary_t info = 212 get_reference_optimization_summary (fn2); 213 214 if (info 215 && (avail >= AVAIL_AVAILABLE 216 || (avail == AVAIL_INTERPOSABLE 217 && flags_from_decl_or_type (fn->decl) & ECF_LEAF)) 218 && opt_for_fn (fn2->decl, flag_ipa_reference)) 219 return info->statics_not_written; 220 else if (avail == AVAIL_NOT_AVAILABLE 221 && flags_from_decl_or_type (fn->decl) & ECF_LEAF) 222 return all_module_statics; 223 else 224 return NULL; 225 } 226 227 228 /* Hepler for is_proper_for_analysis. */ 229 static bool 230 is_improper (symtab_node *n, void *v ATTRIBUTE_UNUSED) 231 { 232 tree t = n->decl; 233 /* If the variable has the "used" attribute, treat it as if it had a 234 been touched by the devil. */ 235 if (DECL_PRESERVE_P (t)) 236 return true; 237 238 /* Do not want to do anything with volatile except mark any 239 function that uses one to be not const or pure. */ 240 if (TREE_THIS_VOLATILE (t)) 241 return true; 242 243 /* We do not need to analyze readonly vars, we already know they do not 244 alias. */ 245 if (TREE_READONLY (t)) 246 return true; 247 248 /* We can not track variables with address taken. */ 249 if (TREE_ADDRESSABLE (t)) 250 return true; 251 252 /* TODO: We could track public variables that are not addressable, but 253 currently frontends don't give us those. */ 254 if (TREE_PUBLIC (t)) 255 return true; 256 257 return false; 258 } 259 260 /* Return true if the variable T is the right kind of static variable to 261 perform compilation unit scope escape analysis. */ 262 263 static inline bool 264 is_proper_for_analysis (tree t) 265 { 266 if (bitmap_bit_p (ignore_module_statics, ipa_reference_var_uid (t))) 267 return false; 268 269 if (symtab_node::get (t) 270 ->call_for_symbol_and_aliases (is_improper, NULL, true)) 271 return false; 272 273 return true; 274 } 275 276 /* Lookup the tree node for the static variable that has UID and 277 convert the name to a string for debugging. */ 278 279 static const char * 280 get_static_name (int index) 281 { 282 splay_tree_node stn = 283 splay_tree_lookup (reference_vars_to_consider, index); 284 return fndecl_name ((tree)(stn->value)); 285 } 286 287 /* Dump a set of static vars to FILE. */ 288 static void 289 dump_static_vars_set_to_file (FILE *f, bitmap set) 290 { 291 unsigned int index; 292 bitmap_iterator bi; 293 if (set == NULL) 294 return; 295 else if (set == all_module_statics) 296 fprintf (f, "ALL"); 297 else 298 EXECUTE_IF_SET_IN_BITMAP (set, 0, index, bi) 299 { 300 fprintf (f, "%s ", get_static_name (index)); 301 } 302 } 303 304 /* Compute X |= Y, taking into account the possibility that 305 either X or Y is already the maximum set. 306 Return true if X is the maximum set after taking the union with Y. */ 307 308 static bool 309 union_static_var_sets (bitmap &x, bitmap y) 310 { 311 if (x != all_module_statics) 312 { 313 if (y == all_module_statics) 314 { 315 BITMAP_FREE (x); 316 x = all_module_statics; 317 } 318 else if (bitmap_ior_into (x, y)) 319 { 320 /* The union may have reduced X to the maximum set. 321 In that case, we want to make that visible explicitly. 322 Even though bitmap_equal_p can be very expensive, it 323 turns out to be an overall win to check this here for 324 an LTO bootstrap of GCC itself. Liberally extrapoliate 325 that result to be applicable to all cases. */ 326 if (bitmap_equal_p (x, all_module_statics)) 327 { 328 BITMAP_FREE (x); 329 x = all_module_statics; 330 } 331 } 332 } 333 return x == all_module_statics; 334 } 335 336 /* Return a copy of SET on the bitmap obstack containing SET. 337 But if SET is NULL or the maximum set, return that instead. */ 338 339 static bitmap 340 copy_static_var_set (bitmap set) 341 { 342 if (set == NULL || set == all_module_statics) 343 return set; 344 bitmap_obstack *o = set->obstack; 345 gcc_checking_assert (o); 346 bitmap copy = BITMAP_ALLOC (o); 347 bitmap_copy (copy, set); 348 return copy; 349 } 350 351 /* Compute the union all of the statics read and written by every callee of X 352 into X_GLOBAL->statics_read and X_GLOBAL->statics_written. X_GLOBAL is 353 actually the set representing the cycle containing X. If the read and 354 written sets of X_GLOBAL has been reduced to the maximum set, we don't 355 have to look at the remaining callees. */ 356 357 static void 358 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x) 359 { 360 struct cgraph_edge *e; 361 bool read_all = x_global->statics_read == all_module_statics; 362 bool write_all = x_global->statics_written == all_module_statics; 363 for (e = x->callees; 364 e && !(read_all && write_all); 365 e = e->next_callee) 366 { 367 enum availability avail; 368 struct cgraph_node *y = e->callee->function_symbol (&avail); 369 if (!y) 370 continue; 371 372 /* Only look into nodes we can propagate something. */ 373 int flags = flags_from_decl_or_type (y->decl); 374 if (opt_for_fn (y->decl, flag_ipa_reference) 375 && (avail > AVAIL_INTERPOSABLE 376 || (avail == AVAIL_INTERPOSABLE && (flags & ECF_LEAF)))) 377 { 378 if (get_reference_vars_info (y)) 379 { 380 ipa_reference_vars_info_t y_info = get_reference_vars_info (y); 381 ipa_reference_global_vars_info_t y_global = &y_info->global; 382 383 /* Calls in the current cycle do not have their global set 384 computed yet (but everything else does because we're 385 visiting nodes in topological order). */ 386 if (!y_global->statics_read) 387 continue; 388 389 /* If the function is const, it reads no memory even if it 390 seems so to local analysis. */ 391 if (flags & ECF_CONST) 392 continue; 393 394 union_static_var_sets (x_global->statics_read, 395 y_global->statics_read); 396 397 /* If the function is pure, it has no stores even if it 398 seems so to local analysis. If we cannot return from 399 the function, we can safely ignore the call. */ 400 if ((flags & ECF_PURE) 401 || e->cannot_lead_to_return_p ()) 402 continue; 403 404 union_static_var_sets (x_global->statics_written, 405 y_global->statics_written); 406 } 407 else 408 gcc_unreachable (); 409 } 410 } 411 } 412 413 static bool ipa_init_p = false; 414 415 /* The init routine for analyzing global static variable usage. See 416 comments at top for description. */ 417 static void 418 ipa_init (void) 419 { 420 if (ipa_init_p) 421 return; 422 423 ipa_init_p = true; 424 425 if (dump_file) 426 reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0); 427 428 bitmap_obstack_initialize (&local_info_obstack); 429 bitmap_obstack_initialize (&optimization_summary_obstack); 430 all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack); 431 ignore_module_statics = BITMAP_ALLOC (&optimization_summary_obstack); 432 433 node_removal_hook_holder = 434 symtab->add_cgraph_removal_hook (&remove_node_data, NULL); 435 node_duplication_hook_holder = 436 symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL); 437 } 438 439 440 /* Set up the persistent info for FN. */ 441 442 static ipa_reference_local_vars_info_t 443 init_function_info (struct cgraph_node *fn) 444 { 445 ipa_reference_vars_info_t info 446 = XCNEW (struct ipa_reference_vars_info_d); 447 448 /* Add the info to the tree's annotation. */ 449 set_reference_vars_info (fn, info); 450 451 info->local.statics_read = BITMAP_ALLOC (&local_info_obstack); 452 info->local.statics_written = BITMAP_ALLOC (&local_info_obstack); 453 454 return &info->local; 455 } 456 457 458 /* This is the main routine for finding the reference patterns for 459 global variables within a function FN. */ 460 461 static void 462 analyze_function (struct cgraph_node *fn) 463 { 464 ipa_reference_local_vars_info_t local; 465 struct ipa_ref *ref = NULL; 466 int i; 467 tree var; 468 469 if (!opt_for_fn (fn->decl, flag_ipa_reference)) 470 return; 471 local = init_function_info (fn); 472 for (i = 0; fn->iterate_reference (i, ref); i++) 473 { 474 if (!is_a <varpool_node *> (ref->referred)) 475 continue; 476 var = ref->referred->decl; 477 if (!is_proper_for_analysis (var)) 478 continue; 479 /* This is a variable we care about. Check if we have seen it 480 before, and if not add it the set of variables we care about. */ 481 if (all_module_statics 482 && bitmap_set_bit (all_module_statics, ipa_reference_var_uid (var))) 483 { 484 if (dump_file) 485 splay_tree_insert (reference_vars_to_consider, 486 ipa_reference_var_uid (var), 487 (splay_tree_value)var); 488 } 489 switch (ref->use) 490 { 491 case IPA_REF_LOAD: 492 bitmap_set_bit (local->statics_read, ipa_reference_var_uid (var)); 493 break; 494 case IPA_REF_STORE: 495 if (ref->cannot_lead_to_return ()) 496 break; 497 bitmap_set_bit (local->statics_written, ipa_reference_var_uid (var)); 498 break; 499 case IPA_REF_ADDR: 500 break; 501 default: 502 gcc_unreachable (); 503 } 504 } 505 506 if (fn->cannot_return_p ()) 507 bitmap_clear (local->statics_written); 508 } 509 510 511 /* Called when new clone is inserted to callgraph late. */ 512 513 static void 514 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst, 515 void *data ATTRIBUTE_UNUSED) 516 { 517 ipa_reference_optimization_summary_t ginfo; 518 ipa_reference_optimization_summary_t dst_ginfo; 519 520 ginfo = get_reference_optimization_summary (src); 521 if (!ginfo) 522 return; 523 dst_ginfo = XCNEW (struct ipa_reference_optimization_summary_d); 524 set_reference_optimization_summary (dst, dst_ginfo); 525 dst_ginfo->statics_not_read = 526 copy_static_var_set (ginfo->statics_not_read); 527 dst_ginfo->statics_not_written = 528 copy_static_var_set (ginfo->statics_not_written); 529 } 530 531 /* Called when node is removed. */ 532 533 static void 534 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED) 535 { 536 ipa_reference_optimization_summary_t ginfo; 537 ginfo = get_reference_optimization_summary (node); 538 if (ginfo) 539 { 540 if (ginfo->statics_not_read 541 && ginfo->statics_not_read != all_module_statics) 542 BITMAP_FREE (ginfo->statics_not_read); 543 544 if (ginfo->statics_not_written 545 && ginfo->statics_not_written != all_module_statics) 546 BITMAP_FREE (ginfo->statics_not_written); 547 free (ginfo); 548 set_reference_optimization_summary (node, NULL); 549 } 550 } 551 552 /* Analyze each function in the cgraph to see which global or statics 553 are read or written. */ 554 555 static void 556 generate_summary (void) 557 { 558 struct cgraph_node *node; 559 unsigned int index; 560 bitmap_iterator bi; 561 562 ipa_init (); 563 564 /* Process all of the functions next. */ 565 FOR_EACH_DEFINED_FUNCTION (node) 566 if (!node->alias && !opt_for_fn (node->decl, flag_ipa_reference)) 567 { 568 struct ipa_ref *ref = NULL; 569 int i; 570 tree var; 571 for (i = 0; node->iterate_reference (i, ref); i++) 572 { 573 if (!is_a <varpool_node *> (ref->referred)) 574 continue; 575 var = ref->referred->decl; 576 if (!is_proper_for_analysis (var)) 577 continue; 578 bitmap_set_bit (ignore_module_statics, ipa_reference_var_uid (var)); 579 } 580 } 581 FOR_EACH_DEFINED_FUNCTION (node) 582 analyze_function (node); 583 584 if (dump_file) 585 EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) 586 { 587 fprintf (dump_file, "\nPromotable global:%s (uid=%u)\n", 588 get_static_name (index), index); 589 } 590 591 if (dump_file) 592 FOR_EACH_DEFINED_FUNCTION (node) 593 if (node->get_availability () >= AVAIL_INTERPOSABLE 594 && opt_for_fn (node->decl, flag_ipa_reference)) 595 { 596 ipa_reference_local_vars_info_t l; 597 unsigned int index; 598 bitmap_iterator bi; 599 600 l = &get_reference_vars_info (node)->local; 601 fprintf (dump_file, 602 "\nFunction name:%s:", node->dump_name ()); 603 fprintf (dump_file, "\n locals read: "); 604 if (l->statics_read) 605 EXECUTE_IF_SET_IN_BITMAP (l->statics_read, 606 0, index, bi) 607 { 608 fprintf (dump_file, "%s ", 609 get_static_name (index)); 610 } 611 fprintf (dump_file, "\n locals written: "); 612 if (l->statics_written) 613 EXECUTE_IF_SET_IN_BITMAP (l->statics_written, 614 0, index, bi) 615 { 616 fprintf (dump_file, "%s ", get_static_name (index)); 617 } 618 } 619 } 620 621 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE. */ 622 623 static void 624 read_write_all_from_decl (struct cgraph_node *node, 625 bool &read_all, bool &write_all) 626 { 627 tree decl = node->decl; 628 int flags = flags_from_decl_or_type (decl); 629 if ((flags & ECF_LEAF) 630 && node->get_availability () < AVAIL_INTERPOSABLE) 631 ; 632 else if (flags & ECF_CONST) 633 ; 634 else if ((flags & ECF_PURE) || node->cannot_return_p ()) 635 { 636 read_all = true; 637 if (dump_file && (dump_flags & TDF_DETAILS)) 638 fprintf (dump_file, " %s -> read all\n", node->dump_name ()); 639 } 640 else 641 { 642 /* TODO: To be able to produce sane results, we should also handle 643 common builtins, in particular throw. */ 644 read_all = true; 645 write_all = true; 646 if (dump_file && (dump_flags & TDF_DETAILS)) 647 fprintf (dump_file, " %s -> read all, write all\n", 648 node->dump_name ()); 649 } 650 } 651 652 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE or any member 653 in the cycle of NODE. */ 654 655 static void 656 get_read_write_all_from_node (struct cgraph_node *node, 657 bool &read_all, bool &write_all) 658 { 659 struct cgraph_edge *e, *ie; 660 661 /* When function is overwritable, we can not assume anything. */ 662 if (node->get_availability () <= AVAIL_INTERPOSABLE 663 || (node->analyzed && !opt_for_fn (node->decl, flag_ipa_reference))) 664 read_write_all_from_decl (node, read_all, write_all); 665 666 for (e = node->callees; 667 e && !(read_all && write_all); 668 e = e->next_callee) 669 { 670 enum availability avail; 671 struct cgraph_node *callee = e->callee->function_symbol (&avail); 672 gcc_checking_assert (callee); 673 if (avail <= AVAIL_INTERPOSABLE 674 || (callee->analyzed && !opt_for_fn (callee->decl, flag_ipa_reference))) 675 read_write_all_from_decl (callee, read_all, write_all); 676 } 677 678 for (ie = node->indirect_calls; 679 ie && !(read_all && write_all); 680 ie = ie->next_callee) 681 if (!(ie->indirect_info->ecf_flags & ECF_CONST)) 682 { 683 read_all = true; 684 if (dump_file && (dump_flags & TDF_DETAILS)) 685 fprintf (dump_file, " indirect call -> read all\n"); 686 if (!ie->cannot_lead_to_return_p () 687 && !(ie->indirect_info->ecf_flags & ECF_PURE)) 688 { 689 if (dump_file && (dump_flags & TDF_DETAILS)) 690 fprintf (dump_file, " indirect call -> write all\n"); 691 write_all = true; 692 } 693 } 694 } 695 696 /* Skip edges from and to nodes without ipa_reference enables. This leave 697 them out of strongy connected coponents and makes them easyto skip in the 698 propagation loop bellow. */ 699 700 static bool 701 ignore_edge_p (cgraph_edge *e) 702 { 703 return (!opt_for_fn (e->caller->decl, flag_ipa_reference) 704 || !opt_for_fn (e->callee->function_symbol ()->decl, 705 flag_ipa_reference)); 706 } 707 708 /* Produce the global information by preforming a transitive closure 709 on the local information that was produced by ipa_analyze_function. */ 710 711 static unsigned int 712 propagate (void) 713 { 714 struct cgraph_node *node; 715 struct cgraph_node **order = 716 XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); 717 int order_pos; 718 int i; 719 bool remove_p; 720 721 if (dump_file) 722 cgraph_node::dump_cgraph (dump_file); 723 724 remove_p = ipa_discover_readonly_nonaddressable_vars (); 725 generate_summary (); 726 727 /* Propagate the local information through the call graph to produce 728 the global information. All the nodes within a cycle will have 729 the same info so we collapse cycles first. Then we can do the 730 propagation in one pass from the leaves to the roots. */ 731 order_pos = ipa_reduced_postorder (order, true, ignore_edge_p); 732 if (dump_file) 733 ipa_print_order (dump_file, "reduced", order, order_pos); 734 735 for (i = 0; i < order_pos; i++ ) 736 { 737 unsigned x; 738 struct cgraph_node *w; 739 ipa_reference_vars_info_t node_info; 740 ipa_reference_global_vars_info_t node_g; 741 ipa_reference_local_vars_info_t node_l; 742 bool read_all = false; 743 bool write_all = false; 744 745 node = order[i]; 746 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference)) 747 continue; 748 749 node_info = get_reference_vars_info (node); 750 gcc_assert (node_info); 751 node_l = &node_info->local; 752 node_g = &node_info->global; 753 754 if (dump_file && (dump_flags & TDF_DETAILS)) 755 fprintf (dump_file, "Starting cycle with %s\n", node->dump_name ()); 756 757 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node); 758 759 /* If any node in a cycle is read_all or write_all, they all are. */ 760 FOR_EACH_VEC_ELT (cycle_nodes, x, w) 761 { 762 if (dump_file && (dump_flags & TDF_DETAILS)) 763 fprintf (dump_file, " Visiting %s\n", w->dump_asm_name ()); 764 get_read_write_all_from_node (w, read_all, write_all); 765 if (read_all && write_all) 766 break; 767 } 768 769 /* Initialized the bitmaps global sets for the reduced node. */ 770 if (read_all) 771 node_g->statics_read = all_module_statics; 772 else 773 node_g->statics_read = copy_static_var_set (node_l->statics_read); 774 if (write_all) 775 node_g->statics_written = all_module_statics; 776 else 777 node_g->statics_written = copy_static_var_set (node_l->statics_written); 778 779 /* Merge the sets of this cycle with all sets of callees reached 780 from this cycle. */ 781 FOR_EACH_VEC_ELT (cycle_nodes, x, w) 782 { 783 if (read_all && write_all) 784 break; 785 786 if (w != node) 787 { 788 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w); 789 ipa_reference_local_vars_info_t w_l = &w_ri->local; 790 int flags = flags_from_decl_or_type (w->decl); 791 792 if (!(flags & ECF_CONST)) 793 read_all = union_static_var_sets (node_g->statics_read, 794 w_l->statics_read); 795 if (!(flags & ECF_PURE) 796 && !w->cannot_return_p ()) 797 write_all = union_static_var_sets (node_g->statics_written, 798 w_l->statics_written); 799 } 800 801 propagate_bits (node_g, w); 802 } 803 804 /* All nodes within a cycle have the same global info bitmaps. */ 805 FOR_EACH_VEC_ELT (cycle_nodes, x, w) 806 { 807 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w); 808 w_ri->global = *node_g; 809 } 810 811 cycle_nodes.release (); 812 } 813 814 if (dump_file) 815 { 816 for (i = 0; i < order_pos; i++) 817 { 818 unsigned x; 819 struct cgraph_node *w; 820 821 node = order[i]; 822 if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference)) 823 continue; 824 825 fprintf (dump_file, "\nFunction name:%s:", node->dump_asm_name ()); 826 827 ipa_reference_vars_info_t node_info = get_reference_vars_info (node); 828 ipa_reference_global_vars_info_t node_g = &node_info->global; 829 830 vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node); 831 FOR_EACH_VEC_ELT (cycle_nodes, x, w) 832 { 833 ipa_reference_vars_info_t w_ri = get_reference_vars_info (w); 834 ipa_reference_local_vars_info_t w_l = &w_ri->local; 835 if (w != node) 836 fprintf (dump_file, "\n next cycle: %s ", w->dump_asm_name ()); 837 fprintf (dump_file, "\n locals read: "); 838 dump_static_vars_set_to_file (dump_file, w_l->statics_read); 839 fprintf (dump_file, "\n locals written: "); 840 dump_static_vars_set_to_file (dump_file, w_l->statics_written); 841 } 842 cycle_nodes.release (); 843 844 fprintf (dump_file, "\n globals read: "); 845 dump_static_vars_set_to_file (dump_file, node_g->statics_read); 846 fprintf (dump_file, "\n globals written: "); 847 dump_static_vars_set_to_file (dump_file, node_g->statics_written); 848 fprintf (dump_file, "\n"); 849 } 850 } 851 852 /* Cleanup. */ 853 FOR_EACH_DEFINED_FUNCTION (node) 854 { 855 ipa_reference_vars_info_t node_info; 856 ipa_reference_global_vars_info_t node_g; 857 ipa_reference_optimization_summary_t opt; 858 859 node_info = get_reference_vars_info (node); 860 if (!node->alias && opt_for_fn (node->decl, flag_ipa_reference) 861 && (node->get_availability () > AVAIL_INTERPOSABLE 862 || (flags_from_decl_or_type (node->decl) & ECF_LEAF))) 863 { 864 node_g = &node_info->global; 865 866 opt = XCNEW (struct ipa_reference_optimization_summary_d); 867 set_reference_optimization_summary (node, opt); 868 869 /* Create the complimentary sets. */ 870 871 if (bitmap_empty_p (node_g->statics_read)) 872 opt->statics_not_read = all_module_statics; 873 else 874 { 875 opt->statics_not_read 876 = BITMAP_ALLOC (&optimization_summary_obstack); 877 if (node_g->statics_read != all_module_statics) 878 bitmap_and_compl (opt->statics_not_read, 879 all_module_statics, 880 node_g->statics_read); 881 } 882 883 if (bitmap_empty_p (node_g->statics_written)) 884 opt->statics_not_written = all_module_statics; 885 else 886 { 887 opt->statics_not_written 888 = BITMAP_ALLOC (&optimization_summary_obstack); 889 if (node_g->statics_written != all_module_statics) 890 bitmap_and_compl (opt->statics_not_written, 891 all_module_statics, 892 node_g->statics_written); 893 } 894 } 895 free (node_info); 896 } 897 898 ipa_free_postorder_info (); 899 free (order); 900 901 bitmap_obstack_release (&local_info_obstack); 902 ipa_reference_vars_vector.release (); 903 if (dump_file) 904 splay_tree_delete (reference_vars_to_consider); 905 reference_vars_to_consider = NULL; 906 return remove_p ? TODO_remove_functions : 0; 907 } 908 909 /* Return true if we need to write summary of NODE. */ 910 911 static bool 912 write_node_summary_p (struct cgraph_node *node, 913 lto_symtab_encoder_t encoder, 914 bitmap ltrans_statics) 915 { 916 ipa_reference_optimization_summary_t info; 917 918 /* See if we have (non-empty) info. */ 919 if (!node->definition || node->global.inlined_to) 920 return false; 921 info = get_reference_optimization_summary (node); 922 if (!info || (bitmap_empty_p (info->statics_not_read) 923 && bitmap_empty_p (info->statics_not_written))) 924 return false; 925 926 /* See if we want to encode it. 927 Encode also referenced functions since constant folding might turn it into 928 a direct call. 929 930 In future we might also want to include summaries of functions references 931 by initializers of constant variables references in current unit. */ 932 if (!reachable_from_this_partition_p (node, encoder) 933 && !referenced_from_this_partition_p (node, encoder)) 934 return false; 935 936 /* See if the info has non-empty intersections with vars we want to encode. */ 937 if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics) 938 && !bitmap_intersect_p (info->statics_not_written, ltrans_statics)) 939 return false; 940 return true; 941 } 942 943 /* Stream out BITS<RANS_STATICS as list of decls to OB. 944 LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS 945 or -1. When it is positive, just output -1 when 946 BITS<RANS_STATICS == BITS<RANS_STATICS. */ 947 948 static void 949 stream_out_bitmap (struct lto_simple_output_block *ob, 950 bitmap bits, bitmap ltrans_statics, 951 int ltrans_statics_bitcount) 952 { 953 int count = 0; 954 unsigned int index; 955 bitmap_iterator bi; 956 if (bits == all_module_statics) 957 { 958 streamer_write_hwi_stream (ob->main_stream, -1); 959 return; 960 } 961 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi) 962 count ++; 963 if (count == ltrans_statics_bitcount) 964 { 965 streamer_write_hwi_stream (ob->main_stream, -1); 966 return; 967 } 968 streamer_write_hwi_stream (ob->main_stream, count); 969 if (!count) 970 return; 971 EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi) 972 { 973 tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value; 974 lto_output_var_decl_index (ob->decl_state, ob->main_stream, decl); 975 } 976 } 977 978 /* Serialize the ipa info for lto. */ 979 980 static void 981 ipa_reference_write_optimization_summary (void) 982 { 983 struct lto_simple_output_block *ob 984 = lto_create_simple_output_block (LTO_section_ipa_reference); 985 unsigned int count = 0; 986 int ltrans_statics_bitcount = 0; 987 lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder; 988 auto_bitmap ltrans_statics; 989 int i; 990 991 reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0); 992 993 /* See what variables we are interested in. */ 994 for (i = 0; i < lto_symtab_encoder_size (encoder); i++) 995 { 996 symtab_node *snode = lto_symtab_encoder_deref (encoder, i); 997 varpool_node *vnode = dyn_cast <varpool_node *> (snode); 998 if (vnode 999 && bitmap_bit_p (all_module_statics, 1000 ipa_reference_var_uid (vnode->decl)) 1001 && referenced_from_this_partition_p (vnode, encoder)) 1002 { 1003 tree decl = vnode->decl; 1004 bitmap_set_bit (ltrans_statics, ipa_reference_var_uid (decl)); 1005 splay_tree_insert (reference_vars_to_consider, 1006 ipa_reference_var_uid (decl), 1007 (splay_tree_value)decl); 1008 ltrans_statics_bitcount ++; 1009 } 1010 } 1011 1012 1013 if (ltrans_statics_bitcount) 1014 for (i = 0; i < lto_symtab_encoder_size (encoder); i++) 1015 { 1016 symtab_node *snode = lto_symtab_encoder_deref (encoder, i); 1017 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode); 1018 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics)) 1019 count++; 1020 } 1021 1022 streamer_write_uhwi_stream (ob->main_stream, count); 1023 if (count) 1024 stream_out_bitmap (ob, ltrans_statics, ltrans_statics, 1025 -1); 1026 1027 /* Process all of the functions. */ 1028 if (ltrans_statics_bitcount) 1029 for (i = 0; i < lto_symtab_encoder_size (encoder); i++) 1030 { 1031 symtab_node *snode = lto_symtab_encoder_deref (encoder, i); 1032 cgraph_node *cnode = dyn_cast <cgraph_node *> (snode); 1033 if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics)) 1034 { 1035 ipa_reference_optimization_summary_t info; 1036 int node_ref; 1037 1038 info = get_reference_optimization_summary (cnode); 1039 node_ref = lto_symtab_encoder_encode (encoder, snode); 1040 streamer_write_uhwi_stream (ob->main_stream, node_ref); 1041 1042 stream_out_bitmap (ob, info->statics_not_read, ltrans_statics, 1043 ltrans_statics_bitcount); 1044 stream_out_bitmap (ob, info->statics_not_written, ltrans_statics, 1045 ltrans_statics_bitcount); 1046 } 1047 } 1048 lto_destroy_simple_output_block (ob); 1049 splay_tree_delete (reference_vars_to_consider); 1050 } 1051 1052 /* Deserialize the ipa info for lto. */ 1053 1054 static void 1055 ipa_reference_read_optimization_summary (void) 1056 { 1057 struct lto_file_decl_data ** file_data_vec 1058 = lto_get_file_decl_data (); 1059 struct lto_file_decl_data * file_data; 1060 unsigned int j = 0; 1061 bitmap_obstack_initialize (&optimization_summary_obstack); 1062 1063 node_removal_hook_holder = 1064 symtab->add_cgraph_removal_hook (&remove_node_data, NULL); 1065 node_duplication_hook_holder = 1066 symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL); 1067 all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack); 1068 1069 while ((file_data = file_data_vec[j++])) 1070 { 1071 const char *data; 1072 size_t len; 1073 struct lto_input_block *ib 1074 = lto_create_simple_input_block (file_data, 1075 LTO_section_ipa_reference, 1076 &data, &len); 1077 if (ib) 1078 { 1079 unsigned int i; 1080 unsigned int f_count = streamer_read_uhwi (ib); 1081 int b_count; 1082 if (!f_count) 1083 continue; 1084 b_count = streamer_read_hwi (ib); 1085 if (dump_file) 1086 fprintf (dump_file, "all module statics:"); 1087 for (i = 0; i < (unsigned int)b_count; i++) 1088 { 1089 unsigned int var_index = streamer_read_uhwi (ib); 1090 tree v_decl = lto_file_decl_data_get_var_decl (file_data, 1091 var_index); 1092 bitmap_set_bit (all_module_statics, 1093 ipa_reference_var_uid (v_decl)); 1094 if (dump_file) 1095 fprintf (dump_file, " %s", fndecl_name (v_decl)); 1096 } 1097 1098 for (i = 0; i < f_count; i++) 1099 { 1100 unsigned int j, index; 1101 struct cgraph_node *node; 1102 ipa_reference_optimization_summary_t info; 1103 int v_count; 1104 lto_symtab_encoder_t encoder; 1105 1106 index = streamer_read_uhwi (ib); 1107 encoder = file_data->symtab_node_encoder; 1108 node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref 1109 (encoder, index)); 1110 info = XCNEW (struct ipa_reference_optimization_summary_d); 1111 set_reference_optimization_summary (node, info); 1112 info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack); 1113 info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack); 1114 if (dump_file) 1115 fprintf (dump_file, 1116 "\nFunction name:%s:\n static not read:", 1117 node->dump_asm_name ()); 1118 1119 /* Set the statics not read. */ 1120 v_count = streamer_read_hwi (ib); 1121 if (v_count == -1) 1122 { 1123 info->statics_not_read = all_module_statics; 1124 if (dump_file) 1125 fprintf (dump_file, " all module statics"); 1126 } 1127 else 1128 for (j = 0; j < (unsigned int)v_count; j++) 1129 { 1130 unsigned int var_index = streamer_read_uhwi (ib); 1131 tree v_decl = lto_file_decl_data_get_var_decl (file_data, 1132 var_index); 1133 bitmap_set_bit (info->statics_not_read, 1134 ipa_reference_var_uid (v_decl)); 1135 if (dump_file) 1136 fprintf (dump_file, " %s", fndecl_name (v_decl)); 1137 } 1138 1139 if (dump_file) 1140 fprintf (dump_file, 1141 "\n static not written:"); 1142 /* Set the statics not written. */ 1143 v_count = streamer_read_hwi (ib); 1144 if (v_count == -1) 1145 { 1146 info->statics_not_written = all_module_statics; 1147 if (dump_file) 1148 fprintf (dump_file, " all module statics"); 1149 } 1150 else 1151 for (j = 0; j < (unsigned int)v_count; j++) 1152 { 1153 unsigned int var_index = streamer_read_uhwi (ib); 1154 tree v_decl = lto_file_decl_data_get_var_decl (file_data, 1155 var_index); 1156 bitmap_set_bit (info->statics_not_written, 1157 ipa_reference_var_uid (v_decl)); 1158 if (dump_file) 1159 fprintf (dump_file, " %s", fndecl_name (v_decl)); 1160 } 1161 if (dump_file) 1162 fprintf (dump_file, "\n"); 1163 } 1164 1165 lto_destroy_simple_input_block (file_data, 1166 LTO_section_ipa_reference, 1167 ib, data, len); 1168 } 1169 else 1170 /* Fatal error here. We do not want to support compiling ltrans units with 1171 different version of compiler or different flags than the WPA unit, so 1172 this should never happen. */ 1173 fatal_error (input_location, 1174 "ipa reference summary is missing in ltrans unit"); 1175 } 1176 } 1177 1178 namespace { 1179 1180 const pass_data pass_data_ipa_reference = 1181 { 1182 IPA_PASS, /* type */ 1183 "static-var", /* name */ 1184 OPTGROUP_NONE, /* optinfo_flags */ 1185 TV_IPA_REFERENCE, /* tv_id */ 1186 0, /* properties_required */ 1187 0, /* properties_provided */ 1188 0, /* properties_destroyed */ 1189 0, /* todo_flags_start */ 1190 0, /* todo_flags_finish */ 1191 }; 1192 1193 class pass_ipa_reference : public ipa_opt_pass_d 1194 { 1195 public: 1196 pass_ipa_reference (gcc::context *ctxt) 1197 : ipa_opt_pass_d (pass_data_ipa_reference, ctxt, 1198 NULL, /* generate_summary */ 1199 NULL, /* write_summary */ 1200 NULL, /* read_summary */ 1201 ipa_reference_write_optimization_summary, /* 1202 write_optimization_summary */ 1203 ipa_reference_read_optimization_summary, /* 1204 read_optimization_summary */ 1205 NULL, /* stmt_fixup */ 1206 0, /* function_transform_todo_flags_start */ 1207 NULL, /* function_transform */ 1208 NULL) /* variable_transform */ 1209 {} 1210 1211 /* opt_pass methods: */ 1212 virtual bool gate (function *) 1213 { 1214 return ((in_lto_p || flag_ipa_reference) 1215 /* Don't bother doing anything if the program has errors. */ 1216 && !seen_error ()); 1217 } 1218 1219 virtual unsigned int execute (function *) { return propagate (); } 1220 1221 }; // class pass_ipa_reference 1222 1223 } // anon namespace 1224 1225 ipa_opt_pass_d * 1226 make_pass_ipa_reference (gcc::context *ctxt) 1227 { 1228 return new pass_ipa_reference (ctxt); 1229 } 1230 1231 /* Reset all state within ipa-reference.c so that we can rerun the compiler 1232 within the same process. For use by toplev::finalize. */ 1233 1234 void 1235 ipa_reference_c_finalize (void) 1236 { 1237 if (ipa_init_p) 1238 { 1239 bitmap_obstack_release (&optimization_summary_obstack); 1240 ipa_init_p = false; 1241 } 1242 1243 if (node_removal_hook_holder) 1244 { 1245 symtab->remove_cgraph_removal_hook (node_removal_hook_holder); 1246 node_removal_hook_holder = NULL; 1247 } 1248 if (node_duplication_hook_holder) 1249 { 1250 symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder); 1251 node_duplication_hook_holder = NULL; 1252 } 1253 } 1254