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/* This file mark functions as being either const (TREE_READONLY) or 23 pure (DECL_IS_PURE). 24 25 This must be run after inlining decisions have been made since 26 otherwise, the local sets will not contain information that is 27 consistent with post inlined state. The global sets are not prone 28 to this problem since they are by definition transitive. */ 29 30/* The code in this module is called by the ipa pass manager. It 31 should be one of the later passes since it's information is used by 32 the rest of the compilation. */ 33 34#include "config.h" 35#include "system.h" 36#include "coretypes.h" 37#include "tm.h" 38#include "tree.h" 39#include "tree-flow.h" 40#include "tree-inline.h" 41#include "tree-pass.h" 42#include "langhooks.h" 43#include "pointer-set.h" 44#include "ggc.h" 45#include "ipa-utils.h" 46#include "c-common.h" 47#include "tree-gimple.h" 48#include "cgraph.h" 49#include "output.h" 50#include "flags.h" 51#include "timevar.h" 52#include "diagnostic.h" 53#include "langhooks.h" 54#include "target.h" 55 56static struct pointer_set_t *visited_nodes; 57 58/* Lattice values for const and pure functions. Everything starts out 59 being const, then may drop to pure and then neither depending on 60 what is found. */ 61enum pure_const_state_e 62{ 63 IPA_CONST, 64 IPA_PURE, 65 IPA_NEITHER 66}; 67 68/* Holder inserted into the ipa_dfs_info aux field to hold the 69 const_state. */ 70struct funct_state_d 71{ 72 enum pure_const_state_e pure_const_state; 73 bool state_set_in_source; 74}; 75 76typedef struct funct_state_d * funct_state; 77 78/* Return the function state from NODE. */ 79 80static inline funct_state 81get_function_state (struct cgraph_node *node) 82{ 83 struct ipa_dfs_info * info = node->aux; 84 return info->aux; 85} 86 87/* Check to see if the use (or definition when CHECHING_WRITE is true) 88 variable T is legal in a function that is either pure or const. */ 89 90static inline void 91check_decl (funct_state local, 92 tree t, bool checking_write) 93{ 94 /* If the variable has the "used" attribute, treat it as if it had a 95 been touched by the devil. */ 96 if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) 97 { 98 local->pure_const_state = IPA_NEITHER; 99 return; 100 } 101 102 /* Do not want to do anything with volatile except mark any 103 function that uses one to be not const or pure. */ 104 if (TREE_THIS_VOLATILE (t)) 105 { 106 local->pure_const_state = IPA_NEITHER; 107 return; 108 } 109 110 /* Do not care about a local automatic that is not static. */ 111 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) 112 return; 113 114 /* Since we have dealt with the locals and params cases above, if we 115 are CHECKING_WRITE, this cannot be a pure or constant 116 function. */ 117 if (checking_write) 118 local->pure_const_state = IPA_NEITHER; 119 120 if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) 121 { 122 /* If the front end set the variable to be READONLY and 123 constant, we can allow this variable in pure or const 124 functions but the scope is too large for our analysis to set 125 these bits ourselves. */ 126 127 if (TREE_READONLY (t) 128 && DECL_INITIAL (t) 129 && is_gimple_min_invariant (DECL_INITIAL (t))) 130 ; /* Read of a constant, do not change the function state. */ 131 else 132 { 133 /* Just a regular read. */ 134 if (local->pure_const_state == IPA_CONST) 135 local->pure_const_state = IPA_PURE; 136 } 137 } 138 139 /* Compilation level statics can be read if they are readonly 140 variables. */ 141 if (TREE_READONLY (t)) 142 return; 143 144 /* Just a regular read. */ 145 if (local->pure_const_state == IPA_CONST) 146 local->pure_const_state = IPA_PURE; 147} 148 149/* If T is a VAR_DECL check to see if it is an allowed reference. */ 150 151static void 152check_operand (funct_state local, 153 tree t, bool checking_write) 154{ 155 if (!t) return; 156 157 if (TREE_CODE (t) == VAR_DECL) 158 check_decl (local, t, checking_write); 159} 160 161/* Examine tree T for references. */ 162 163static void 164check_tree (funct_state local, tree t, bool checking_write) 165{ 166 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 167 return; 168 169 /* Any tree which is volatile disqualifies thie function from being 170 const or pure. */ 171 if (TREE_THIS_VOLATILE (t)) 172 { 173 local->pure_const_state = IPA_NEITHER; 174 return; 175 } 176 177 while (TREE_CODE (t) == REALPART_EXPR 178 || TREE_CODE (t) == IMAGPART_EXPR 179 || handled_component_p (t)) 180 { 181 if (TREE_CODE (t) == ARRAY_REF) 182 check_operand (local, TREE_OPERAND (t, 1), false); 183 t = TREE_OPERAND (t, 0); 184 } 185 186 /* The bottom of an indirect reference can only be read, not 187 written. */ 188 if (INDIRECT_REF_P (t)) 189 { 190 check_tree (local, TREE_OPERAND (t, 0), false); 191 192 /* Any indirect reference that occurs on the lhs 193 disqualifies the function from being pure or const. Any 194 indirect reference that occurs on the rhs disqualifies the 195 function from being const. */ 196 if (checking_write) 197 { 198 local->pure_const_state = IPA_NEITHER; 199 return; 200 } 201 else if (local->pure_const_state == IPA_CONST) 202 local->pure_const_state = IPA_PURE; 203 } 204 205 if (SSA_VAR_P (t)) 206 check_operand (local, t, checking_write); 207} 208 209/* Scan tree T to see if there are any addresses taken in within T. */ 210 211static void 212look_for_address_of (funct_state local, tree t) 213{ 214 if (TREE_CODE (t) == ADDR_EXPR) 215 { 216 tree x = get_base_var (t); 217 if (TREE_CODE (x) == VAR_DECL) 218 { 219 check_decl (local, x, false); 220 221 /* Taking the address of something appears to be reasonable 222 in PURE code. Not allowed in const. */ 223 if (local->pure_const_state == IPA_CONST) 224 local->pure_const_state = IPA_PURE; 225 } 226 } 227} 228 229/* Check to see if T is a read or address of operation on a var we are 230 interested in analyzing. LOCAL is passed in to get access to its 231 bit vectors. */ 232 233static void 234check_rhs_var (funct_state local, tree t) 235{ 236 look_for_address_of (local, t); 237 238 /* Memcmp and strlen can both trap and they are declared pure. */ 239 if (tree_could_trap_p (t) 240 && local->pure_const_state == IPA_CONST) 241 local->pure_const_state = IPA_PURE; 242 243 check_tree(local, t, false); 244} 245 246/* Check to see if T is an assignment to a var we are interested in 247 analyzing. LOCAL is passed in to get access to its bit vectors. */ 248 249static void 250check_lhs_var (funct_state local, tree t) 251{ 252 /* Memcmp and strlen can both trap and they are declared pure. 253 Which seems to imply that we can apply the same rule here. */ 254 if (tree_could_trap_p (t) 255 && local->pure_const_state == IPA_CONST) 256 local->pure_const_state = IPA_PURE; 257 258 check_tree(local, t, true); 259} 260 261/* This is a scaled down version of get_asm_expr_operands from 262 tree_ssa_operands.c. The version there runs much later and assumes 263 that aliasing information is already available. Here we are just 264 trying to find if the set of inputs and outputs contain references 265 or address of operations to local static variables. STMT is the 266 actual asm statement. */ 267 268static void 269get_asm_expr_operands (funct_state local, tree stmt) 270{ 271 int noutputs = list_length (ASM_OUTPUTS (stmt)); 272 const char **oconstraints 273 = (const char **) alloca ((noutputs) * sizeof (const char *)); 274 int i; 275 tree link; 276 const char *constraint; 277 bool allows_mem, allows_reg, is_inout; 278 279 for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) 280 { 281 oconstraints[i] = constraint 282 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 283 parse_output_constraint (&constraint, i, 0, 0, 284 &allows_mem, &allows_reg, &is_inout); 285 286 check_lhs_var (local, TREE_VALUE (link)); 287 } 288 289 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 290 { 291 constraint 292 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 293 parse_input_constraint (&constraint, 0, 0, noutputs, 0, 294 oconstraints, &allows_mem, &allows_reg); 295 296 check_rhs_var (local, TREE_VALUE (link)); 297 } 298 299 for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link)) 300 if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) 301 /* Abandon all hope, ye who enter here. */ 302 local->pure_const_state = IPA_NEITHER; 303 304 if (ASM_VOLATILE_P (stmt)) 305 local->pure_const_state = IPA_NEITHER; 306} 307 308/* Check the parameters of a function call to CALL_EXPR to see if 309 there are any references in the parameters that are not allowed for 310 pure or const functions. Also check to see if this is either an 311 indirect call, a call outside the compilation unit, or has special 312 attributes that may also effect the purity. The CALL_EXPR node for 313 the entire call expression. */ 314 315static void 316check_call (funct_state local, tree call_expr) 317{ 318 int flags = call_expr_flags(call_expr); 319 tree operand_list = TREE_OPERAND (call_expr, 1); 320 tree operand; 321 tree callee_t = get_callee_fndecl (call_expr); 322 struct cgraph_node* callee; 323 enum availability avail = AVAIL_NOT_AVAILABLE; 324 325 for (operand = operand_list; 326 operand != NULL_TREE; 327 operand = TREE_CHAIN (operand)) 328 { 329 tree argument = TREE_VALUE (operand); 330 check_rhs_var (local, argument); 331 } 332 333 /* The const and pure flags are set by a variety of places in the 334 compiler (including here). If someone has already set the flags 335 for the callee, (such as for some of the builtins) we will use 336 them, otherwise we will compute our own information. 337 338 Const and pure functions have less clobber effects than other 339 functions so we process these first. Otherwise if it is a call 340 outside the compilation unit or an indirect call we punt. This 341 leaves local calls which will be processed by following the call 342 graph. */ 343 if (callee_t) 344 { 345 callee = cgraph_node(callee_t); 346 avail = cgraph_function_body_availability (callee); 347 348 /* When bad things happen to bad functions, they cannot be const 349 or pure. */ 350 if (setjmp_call_p (callee_t)) 351 local->pure_const_state = IPA_NEITHER; 352 353 if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL) 354 switch (DECL_FUNCTION_CODE (callee_t)) 355 { 356 case BUILT_IN_LONGJMP: 357 case BUILT_IN_NONLOCAL_GOTO: 358 local->pure_const_state = IPA_NEITHER; 359 break; 360 default: 361 break; 362 } 363 } 364 365 /* The callee is either unknown (indirect call) or there is just no 366 scannable code for it (external call) . We look to see if there 367 are any bits available for the callee (such as by declaration or 368 because it is builtin) and process solely on the basis of those 369 bits. */ 370 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) 371 { 372 if (flags & ECF_PURE) 373 { 374 if (local->pure_const_state == IPA_CONST) 375 local->pure_const_state = IPA_PURE; 376 } 377 else 378 local->pure_const_state = IPA_NEITHER; 379 } 380 else 381 { 382 /* We have the code and we will scan it for the effects. */ 383 if (flags & ECF_PURE) 384 { 385 if (local->pure_const_state == IPA_CONST) 386 local->pure_const_state = IPA_PURE; 387 } 388 } 389} 390 391/* TP is the part of the tree currently under the microscope. 392 WALK_SUBTREES is part of the walk_tree api but is unused here. 393 DATA is cgraph_node of the function being walked. */ 394 395/* FIXME: When this is converted to run over SSA form, this code 396 should be converted to use the operand scanner. */ 397 398static tree 399scan_function (tree *tp, 400 int *walk_subtrees, 401 void *data) 402{ 403 struct cgraph_node *fn = data; 404 tree t = *tp; 405 funct_state local = get_function_state (fn); 406 407 switch (TREE_CODE (t)) 408 { 409 case VAR_DECL: 410 if (DECL_INITIAL (t)) 411 walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes); 412 *walk_subtrees = 0; 413 break; 414 415 case MODIFY_EXPR: 416 { 417 /* First look on the lhs and see what variable is stored to */ 418 tree lhs = TREE_OPERAND (t, 0); 419 tree rhs = TREE_OPERAND (t, 1); 420 check_lhs_var (local, lhs); 421 422 /* For the purposes of figuring out what the cast affects */ 423 424 /* Next check the operands on the rhs to see if they are ok. */ 425 switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 426 { 427 case tcc_binary: 428 { 429 tree op0 = TREE_OPERAND (rhs, 0); 430 tree op1 = TREE_OPERAND (rhs, 1); 431 check_rhs_var (local, op0); 432 check_rhs_var (local, op1); 433 } 434 break; 435 case tcc_unary: 436 { 437 tree op0 = TREE_OPERAND (rhs, 0); 438 check_rhs_var (local, op0); 439 } 440 441 break; 442 case tcc_reference: 443 check_rhs_var (local, rhs); 444 break; 445 case tcc_declaration: 446 check_rhs_var (local, rhs); 447 break; 448 case tcc_expression: 449 switch (TREE_CODE (rhs)) 450 { 451 case ADDR_EXPR: 452 check_rhs_var (local, rhs); 453 break; 454 case CALL_EXPR: 455 check_call (local, rhs); 456 break; 457 default: 458 break; 459 } 460 break; 461 default: 462 break; 463 } 464 *walk_subtrees = 0; 465 } 466 break; 467 468 case ADDR_EXPR: 469 /* This case is here to find addresses on rhs of constructors in 470 decl_initial of static variables. */ 471 check_rhs_var (local, t); 472 *walk_subtrees = 0; 473 break; 474 475 case LABEL_EXPR: 476 if (DECL_NONLOCAL (TREE_OPERAND (t, 0))) 477 /* Target of long jump. */ 478 local->pure_const_state = IPA_NEITHER; 479 break; 480 481 case CALL_EXPR: 482 check_call (local, t); 483 *walk_subtrees = 0; 484 break; 485 486 case ASM_EXPR: 487 get_asm_expr_operands (local, t); 488 *walk_subtrees = 0; 489 break; 490 491 default: 492 break; 493 } 494 return NULL; 495} 496 497/* This is the main routine for finding the reference patterns for 498 global variables within a function FN. */ 499 500static void 501analyze_function (struct cgraph_node *fn) 502{ 503 funct_state l = XCNEW (struct funct_state_d); 504 tree decl = fn->decl; 505 struct ipa_dfs_info * w_info = fn->aux; 506 507 w_info->aux = l; 508 509 l->pure_const_state = IPA_CONST; 510 l->state_set_in_source = false; 511 512 /* If this function does not return normally or does not bind local, 513 do not touch this unless it has been marked as const or pure by the 514 front end. */ 515 if (TREE_THIS_VOLATILE (decl) 516 || !targetm.binds_local_p (decl)) 517 { 518 l->pure_const_state = IPA_NEITHER; 519 return; 520 } 521 522 if (TREE_READONLY (decl)) 523 { 524 l->pure_const_state = IPA_CONST; 525 l->state_set_in_source = true; 526 } 527 if (DECL_IS_PURE (decl)) 528 { 529 l->pure_const_state = IPA_PURE; 530 l->state_set_in_source = true; 531 } 532 533 if (dump_file) 534 { 535 fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ", 536 cgraph_node_name (fn), 537 l->pure_const_state); 538 } 539 540 if (!l->state_set_in_source) 541 { 542 struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 543 basic_block this_block; 544 545 FOR_EACH_BB_FN (this_block, this_cfun) 546 { 547 block_stmt_iterator bsi; 548 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 549 { 550 walk_tree (bsi_stmt_ptr (bsi), scan_function, 551 fn, visited_nodes); 552 if (l->pure_const_state == IPA_NEITHER) 553 goto end; 554 } 555 } 556 557 if (l->pure_const_state != IPA_NEITHER) 558 { 559 tree old_decl = current_function_decl; 560 /* Const functions cannot have back edges (an 561 indication of possible infinite loop side 562 effect. */ 563 564 current_function_decl = fn->decl; 565 566 /* The C++ front end, has a tendency to some times jerk away 567 a function after it has created it. This should have 568 been fixed. */ 569 gcc_assert (DECL_STRUCT_FUNCTION (fn->decl)); 570 571 push_cfun (DECL_STRUCT_FUNCTION (fn->decl)); 572 573 if (mark_dfs_back_edges ()) 574 l->pure_const_state = IPA_NEITHER; 575 576 current_function_decl = old_decl; 577 pop_cfun (); 578 } 579 } 580 581end: 582 if (dump_file) 583 { 584 fprintf (dump_file, "after local analysis of %s with initial value = %d\n ", 585 cgraph_node_name (fn), 586 l->pure_const_state); 587 } 588} 589 590 591/* Produce the global information by preforming a transitive closure 592 on the local information that was produced by ipa_analyze_function 593 and ipa_analyze_variable. */ 594 595static unsigned int 596static_execute (void) 597{ 598 struct cgraph_node *node; 599 struct cgraph_node *w; 600 struct cgraph_node **order = 601 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 602 int order_pos = order_pos = ipa_utils_reduced_inorder (order, true, false); 603 int i; 604 struct ipa_dfs_info * w_info; 605 606 if (!memory_identifier_string) 607 memory_identifier_string = build_string(7, "memory"); 608 609 /* There are some shared nodes, in particular the initializers on 610 static declarations. We do not need to scan them more than once 611 since all we would be interested in are the addressof 612 operations. */ 613 visited_nodes = pointer_set_create (); 614 615 /* Process all of the functions. 616 617 We do not want to process any of the clones so we check that this 618 is a master clone. However, we do NOT process any 619 AVAIL_OVERWRITABLE functions (these are never clones) we cannot 620 guarantee that what we learn about the one we see will be true 621 for the one that overriders it. 622 */ 623 for (node = cgraph_nodes; node; node = node->next) 624 if (node->analyzed && cgraph_is_master_clone (node)) 625 analyze_function (node); 626 627 pointer_set_destroy (visited_nodes); 628 visited_nodes = NULL; 629 if (dump_file) 630 { 631 dump_cgraph (dump_file); 632 ipa_utils_print_order(dump_file, "reduced", order, order_pos); 633 } 634 635 /* Propagate the local information thru the call graph to produce 636 the global information. All the nodes within a cycle will have 637 the same info so we collapse cycles first. Then we can do the 638 propagation in one pass from the leaves to the roots. */ 639 for (i = 0; i < order_pos; i++ ) 640 { 641 enum pure_const_state_e pure_const_state = IPA_CONST; 642 int count = 0; 643 node = order[i]; 644 645 /* Find the worst state for any node in the cycle. */ 646 w = node; 647 while (w) 648 { 649 funct_state w_l = get_function_state (w); 650 if (pure_const_state < w_l->pure_const_state) 651 pure_const_state = w_l->pure_const_state; 652 653 if (pure_const_state == IPA_NEITHER) 654 break; 655 656 if (!w_l->state_set_in_source) 657 { 658 struct cgraph_edge *e; 659 count++; 660 661 /* FIXME!!! Because of pr33826, we cannot have either 662 immediate or transitive recursive functions marked as 663 pure or const because dce can delete a function that 664 is in reality an infinite loop. A better solution 665 than just outlawing them is to add another bit the 666 functions to distinguish recursive from non recursive 667 pure and const function. This would allow the 668 recursive ones to be cse'd but not dce'd. In this 669 same vein, we could allow functions with loops to 670 also be cse'd but not dce'd. 671 672 Unfortunately we are late in stage 3, and the fix 673 described above is is not appropriate. */ 674 if (count > 1) 675 { 676 pure_const_state = IPA_NEITHER; 677 break; 678 } 679 680 for (e = w->callees; e; e = e->next_callee) 681 { 682 struct cgraph_node *y = e->callee; 683 /* Only look at the master nodes and skip external nodes. */ 684 y = cgraph_master_clone (y); 685 686 /* Check for immediate recursive functions. See the 687 FIXME above. */ 688 if (w == y) 689 { 690 pure_const_state = IPA_NEITHER; 691 break; 692 } 693 if (y) 694 { 695 funct_state y_l = get_function_state (y); 696 if (pure_const_state < y_l->pure_const_state) 697 pure_const_state = y_l->pure_const_state; 698 if (pure_const_state == IPA_NEITHER) 699 break; 700 } 701 } 702 } 703 w_info = w->aux; 704 w = w_info->next_cycle; 705 } 706 707 /* Copy back the region's pure_const_state which is shared by 708 all nodes in the region. */ 709 w = node; 710 while (w) 711 { 712 funct_state w_l = get_function_state (w); 713 714 /* All nodes within a cycle share the same info. */ 715 if (!w_l->state_set_in_source) 716 { 717 w_l->pure_const_state = pure_const_state; 718 switch (pure_const_state) 719 { 720 case IPA_CONST: 721 TREE_READONLY (w->decl) = 1; 722 if (dump_file) 723 fprintf (dump_file, "Function found to be const: %s\n", 724 lang_hooks.decl_printable_name(w->decl, 2)); 725 break; 726 727 case IPA_PURE: 728 DECL_IS_PURE (w->decl) = 1; 729 if (dump_file) 730 fprintf (dump_file, "Function found to be pure: %s\n", 731 lang_hooks.decl_printable_name(w->decl, 2)); 732 break; 733 734 default: 735 break; 736 } 737 } 738 w_info = w->aux; 739 w = w_info->next_cycle; 740 } 741 } 742 743 /* Cleanup. */ 744 for (node = cgraph_nodes; node; node = node->next) 745 /* Get rid of the aux information. */ 746 if (node->aux) 747 { 748 w_info = node->aux; 749 if (w_info->aux) 750 free (w_info->aux); 751 free (node->aux); 752 node->aux = NULL; 753 } 754 755 free (order); 756 return 0; 757} 758 759static bool 760gate_pure_const (void) 761{ 762 return (flag_unit_at_a_time != 0 && flag_ipa_pure_const 763 /* Don't bother doing anything if the program has errors. */ 764 && !(errorcount || sorrycount)); 765} 766 767struct tree_opt_pass pass_ipa_pure_const = 768{ 769 "pure-const", /* name */ 770 gate_pure_const, /* gate */ 771 static_execute, /* execute */ 772 NULL, /* sub */ 773 NULL, /* next */ 774 0, /* static_pass_number */ 775 TV_IPA_PURE_CONST, /* tv_id */ 776 0, /* properties_required */ 777 0, /* properties_provided */ 778 0, /* properties_destroyed */ 779 0, /* todo_flags_start */ 780 0, /* todo_flags_finish */ 781 0 /* letter */ 782}; 783 784 785