1169689Skan/* Callgraph based analysis of static variables. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan/* This file mark functions as being either const (TREE_READONLY) or 23169689Skan pure (DECL_IS_PURE). 24169689Skan 25169689Skan This must be run after inlining decisions have been made since 26169689Skan otherwise, the local sets will not contain information that is 27169689Skan consistent with post inlined state. The global sets are not prone 28169689Skan to this problem since they are by definition transitive. */ 29169689Skan 30169689Skan/* The code in this module is called by the ipa pass manager. It 31169689Skan should be one of the later passes since it's information is used by 32169689Skan the rest of the compilation. */ 33169689Skan 34169689Skan#include "config.h" 35169689Skan#include "system.h" 36169689Skan#include "coretypes.h" 37169689Skan#include "tm.h" 38169689Skan#include "tree.h" 39169689Skan#include "tree-flow.h" 40169689Skan#include "tree-inline.h" 41169689Skan#include "tree-pass.h" 42169689Skan#include "langhooks.h" 43169689Skan#include "pointer-set.h" 44169689Skan#include "ggc.h" 45169689Skan#include "ipa-utils.h" 46169689Skan#include "c-common.h" 47169689Skan#include "tree-gimple.h" 48169689Skan#include "cgraph.h" 49169689Skan#include "output.h" 50169689Skan#include "flags.h" 51169689Skan#include "timevar.h" 52169689Skan#include "diagnostic.h" 53169689Skan#include "langhooks.h" 54169689Skan#include "target.h" 55169689Skan 56169689Skanstatic struct pointer_set_t *visited_nodes; 57169689Skan 58169689Skan/* Lattice values for const and pure functions. Everything starts out 59169689Skan being const, then may drop to pure and then neither depending on 60169689Skan what is found. */ 61169689Skanenum pure_const_state_e 62169689Skan{ 63169689Skan IPA_CONST, 64169689Skan IPA_PURE, 65169689Skan IPA_NEITHER 66169689Skan}; 67169689Skan 68169689Skan/* Holder inserted into the ipa_dfs_info aux field to hold the 69169689Skan const_state. */ 70169689Skanstruct funct_state_d 71169689Skan{ 72169689Skan enum pure_const_state_e pure_const_state; 73169689Skan bool state_set_in_source; 74169689Skan}; 75169689Skan 76169689Skantypedef struct funct_state_d * funct_state; 77169689Skan 78169689Skan/* Return the function state from NODE. */ 79169689Skan 80169689Skanstatic inline funct_state 81169689Skanget_function_state (struct cgraph_node *node) 82169689Skan{ 83169689Skan struct ipa_dfs_info * info = node->aux; 84169689Skan return info->aux; 85169689Skan} 86169689Skan 87169689Skan/* Check to see if the use (or definition when CHECHING_WRITE is true) 88169689Skan variable T is legal in a function that is either pure or const. */ 89169689Skan 90169689Skanstatic inline void 91169689Skancheck_decl (funct_state local, 92169689Skan tree t, bool checking_write) 93169689Skan{ 94169689Skan /* If the variable has the "used" attribute, treat it as if it had a 95169689Skan been touched by the devil. */ 96169689Skan if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) 97169689Skan { 98169689Skan local->pure_const_state = IPA_NEITHER; 99169689Skan return; 100169689Skan } 101169689Skan 102169689Skan /* Do not want to do anything with volatile except mark any 103169689Skan function that uses one to be not const or pure. */ 104169689Skan if (TREE_THIS_VOLATILE (t)) 105169689Skan { 106169689Skan local->pure_const_state = IPA_NEITHER; 107169689Skan return; 108169689Skan } 109169689Skan 110169689Skan /* Do not care about a local automatic that is not static. */ 111169689Skan if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) 112169689Skan return; 113169689Skan 114169689Skan /* Since we have dealt with the locals and params cases above, if we 115169689Skan are CHECKING_WRITE, this cannot be a pure or constant 116169689Skan function. */ 117169689Skan if (checking_write) 118169689Skan local->pure_const_state = IPA_NEITHER; 119169689Skan 120169689Skan if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) 121169689Skan { 122169689Skan /* If the front end set the variable to be READONLY and 123169689Skan constant, we can allow this variable in pure or const 124169689Skan functions but the scope is too large for our analysis to set 125169689Skan these bits ourselves. */ 126169689Skan 127169689Skan if (TREE_READONLY (t) 128169689Skan && DECL_INITIAL (t) 129169689Skan && is_gimple_min_invariant (DECL_INITIAL (t))) 130169689Skan ; /* Read of a constant, do not change the function state. */ 131169689Skan else 132169689Skan { 133169689Skan /* Just a regular read. */ 134169689Skan if (local->pure_const_state == IPA_CONST) 135169689Skan local->pure_const_state = IPA_PURE; 136169689Skan } 137169689Skan } 138169689Skan 139169689Skan /* Compilation level statics can be read if they are readonly 140169689Skan variables. */ 141169689Skan if (TREE_READONLY (t)) 142169689Skan return; 143169689Skan 144169689Skan /* Just a regular read. */ 145169689Skan if (local->pure_const_state == IPA_CONST) 146169689Skan local->pure_const_state = IPA_PURE; 147169689Skan} 148169689Skan 149169689Skan/* If T is a VAR_DECL check to see if it is an allowed reference. */ 150169689Skan 151169689Skanstatic void 152169689Skancheck_operand (funct_state local, 153169689Skan tree t, bool checking_write) 154169689Skan{ 155169689Skan if (!t) return; 156169689Skan 157169689Skan if (TREE_CODE (t) == VAR_DECL) 158169689Skan check_decl (local, t, checking_write); 159169689Skan} 160169689Skan 161169689Skan/* Examine tree T for references. */ 162169689Skan 163169689Skanstatic void 164169689Skancheck_tree (funct_state local, tree t, bool checking_write) 165169689Skan{ 166169689Skan if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 167169689Skan return; 168169689Skan 169169689Skan /* Any tree which is volatile disqualifies thie function from being 170169689Skan const or pure. */ 171169689Skan if (TREE_THIS_VOLATILE (t)) 172169689Skan { 173169689Skan local->pure_const_state = IPA_NEITHER; 174169689Skan return; 175169689Skan } 176169689Skan 177169689Skan while (TREE_CODE (t) == REALPART_EXPR 178169689Skan || TREE_CODE (t) == IMAGPART_EXPR 179169689Skan || handled_component_p (t)) 180169689Skan { 181169689Skan if (TREE_CODE (t) == ARRAY_REF) 182169689Skan check_operand (local, TREE_OPERAND (t, 1), false); 183169689Skan t = TREE_OPERAND (t, 0); 184169689Skan } 185169689Skan 186169689Skan /* The bottom of an indirect reference can only be read, not 187169689Skan written. */ 188169689Skan if (INDIRECT_REF_P (t)) 189169689Skan { 190169689Skan check_tree (local, TREE_OPERAND (t, 0), false); 191169689Skan 192169689Skan /* Any indirect reference that occurs on the lhs 193169689Skan disqualifies the function from being pure or const. Any 194169689Skan indirect reference that occurs on the rhs disqualifies the 195169689Skan function from being const. */ 196169689Skan if (checking_write) 197169689Skan { 198169689Skan local->pure_const_state = IPA_NEITHER; 199169689Skan return; 200169689Skan } 201169689Skan else if (local->pure_const_state == IPA_CONST) 202169689Skan local->pure_const_state = IPA_PURE; 203169689Skan } 204169689Skan 205169689Skan if (SSA_VAR_P (t)) 206169689Skan check_operand (local, t, checking_write); 207169689Skan} 208169689Skan 209169689Skan/* Scan tree T to see if there are any addresses taken in within T. */ 210169689Skan 211169689Skanstatic void 212169689Skanlook_for_address_of (funct_state local, tree t) 213169689Skan{ 214169689Skan if (TREE_CODE (t) == ADDR_EXPR) 215169689Skan { 216169689Skan tree x = get_base_var (t); 217169689Skan if (TREE_CODE (x) == VAR_DECL) 218169689Skan { 219169689Skan check_decl (local, x, false); 220169689Skan 221169689Skan /* Taking the address of something appears to be reasonable 222169689Skan in PURE code. Not allowed in const. */ 223169689Skan if (local->pure_const_state == IPA_CONST) 224169689Skan local->pure_const_state = IPA_PURE; 225169689Skan } 226169689Skan } 227169689Skan} 228169689Skan 229169689Skan/* Check to see if T is a read or address of operation on a var we are 230169689Skan interested in analyzing. LOCAL is passed in to get access to its 231169689Skan bit vectors. */ 232169689Skan 233169689Skanstatic void 234169689Skancheck_rhs_var (funct_state local, tree t) 235169689Skan{ 236169689Skan look_for_address_of (local, t); 237169689Skan 238169689Skan /* Memcmp and strlen can both trap and they are declared pure. */ 239169689Skan if (tree_could_trap_p (t) 240169689Skan && local->pure_const_state == IPA_CONST) 241169689Skan local->pure_const_state = IPA_PURE; 242169689Skan 243169689Skan check_tree(local, t, false); 244169689Skan} 245169689Skan 246169689Skan/* Check to see if T is an assignment to a var we are interested in 247169689Skan analyzing. LOCAL is passed in to get access to its bit vectors. */ 248169689Skan 249169689Skanstatic void 250169689Skancheck_lhs_var (funct_state local, tree t) 251169689Skan{ 252169689Skan /* Memcmp and strlen can both trap and they are declared pure. 253169689Skan Which seems to imply that we can apply the same rule here. */ 254169689Skan if (tree_could_trap_p (t) 255169689Skan && local->pure_const_state == IPA_CONST) 256169689Skan local->pure_const_state = IPA_PURE; 257169689Skan 258169689Skan check_tree(local, t, true); 259169689Skan} 260169689Skan 261169689Skan/* This is a scaled down version of get_asm_expr_operands from 262169689Skan tree_ssa_operands.c. The version there runs much later and assumes 263169689Skan that aliasing information is already available. Here we are just 264169689Skan trying to find if the set of inputs and outputs contain references 265169689Skan or address of operations to local static variables. STMT is the 266169689Skan actual asm statement. */ 267169689Skan 268169689Skanstatic void 269169689Skanget_asm_expr_operands (funct_state local, tree stmt) 270169689Skan{ 271169689Skan int noutputs = list_length (ASM_OUTPUTS (stmt)); 272169689Skan const char **oconstraints 273169689Skan = (const char **) alloca ((noutputs) * sizeof (const char *)); 274169689Skan int i; 275169689Skan tree link; 276169689Skan const char *constraint; 277169689Skan bool allows_mem, allows_reg, is_inout; 278169689Skan 279169689Skan for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) 280169689Skan { 281169689Skan oconstraints[i] = constraint 282169689Skan = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 283169689Skan parse_output_constraint (&constraint, i, 0, 0, 284169689Skan &allows_mem, &allows_reg, &is_inout); 285169689Skan 286169689Skan check_lhs_var (local, TREE_VALUE (link)); 287169689Skan } 288169689Skan 289169689Skan for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 290169689Skan { 291169689Skan constraint 292169689Skan = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 293169689Skan parse_input_constraint (&constraint, 0, 0, noutputs, 0, 294169689Skan oconstraints, &allows_mem, &allows_reg); 295169689Skan 296169689Skan check_rhs_var (local, TREE_VALUE (link)); 297169689Skan } 298169689Skan 299169689Skan for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link)) 300169689Skan if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) 301169689Skan /* Abandon all hope, ye who enter here. */ 302169689Skan local->pure_const_state = IPA_NEITHER; 303169689Skan 304169689Skan if (ASM_VOLATILE_P (stmt)) 305169689Skan local->pure_const_state = IPA_NEITHER; 306169689Skan} 307169689Skan 308169689Skan/* Check the parameters of a function call to CALL_EXPR to see if 309169689Skan there are any references in the parameters that are not allowed for 310169689Skan pure or const functions. Also check to see if this is either an 311169689Skan indirect call, a call outside the compilation unit, or has special 312169689Skan attributes that may also effect the purity. The CALL_EXPR node for 313169689Skan the entire call expression. */ 314169689Skan 315169689Skanstatic void 316169689Skancheck_call (funct_state local, tree call_expr) 317169689Skan{ 318169689Skan int flags = call_expr_flags(call_expr); 319169689Skan tree operand_list = TREE_OPERAND (call_expr, 1); 320169689Skan tree operand; 321169689Skan tree callee_t = get_callee_fndecl (call_expr); 322169689Skan struct cgraph_node* callee; 323169689Skan enum availability avail = AVAIL_NOT_AVAILABLE; 324169689Skan 325169689Skan for (operand = operand_list; 326169689Skan operand != NULL_TREE; 327169689Skan operand = TREE_CHAIN (operand)) 328169689Skan { 329169689Skan tree argument = TREE_VALUE (operand); 330169689Skan check_rhs_var (local, argument); 331169689Skan } 332169689Skan 333169689Skan /* The const and pure flags are set by a variety of places in the 334169689Skan compiler (including here). If someone has already set the flags 335169689Skan for the callee, (such as for some of the builtins) we will use 336169689Skan them, otherwise we will compute our own information. 337169689Skan 338169689Skan Const and pure functions have less clobber effects than other 339169689Skan functions so we process these first. Otherwise if it is a call 340169689Skan outside the compilation unit or an indirect call we punt. This 341169689Skan leaves local calls which will be processed by following the call 342169689Skan graph. */ 343169689Skan if (callee_t) 344169689Skan { 345169689Skan callee = cgraph_node(callee_t); 346169689Skan avail = cgraph_function_body_availability (callee); 347169689Skan 348169689Skan /* When bad things happen to bad functions, they cannot be const 349169689Skan or pure. */ 350169689Skan if (setjmp_call_p (callee_t)) 351169689Skan local->pure_const_state = IPA_NEITHER; 352169689Skan 353169689Skan if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL) 354169689Skan switch (DECL_FUNCTION_CODE (callee_t)) 355169689Skan { 356169689Skan case BUILT_IN_LONGJMP: 357169689Skan case BUILT_IN_NONLOCAL_GOTO: 358169689Skan local->pure_const_state = IPA_NEITHER; 359169689Skan break; 360169689Skan default: 361169689Skan break; 362169689Skan } 363169689Skan } 364169689Skan 365169689Skan /* The callee is either unknown (indirect call) or there is just no 366169689Skan scannable code for it (external call) . We look to see if there 367169689Skan are any bits available for the callee (such as by declaration or 368169689Skan because it is builtin) and process solely on the basis of those 369169689Skan bits. */ 370169689Skan if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) 371169689Skan { 372169689Skan if (flags & ECF_PURE) 373169689Skan { 374169689Skan if (local->pure_const_state == IPA_CONST) 375169689Skan local->pure_const_state = IPA_PURE; 376169689Skan } 377169689Skan else 378169689Skan local->pure_const_state = IPA_NEITHER; 379169689Skan } 380169689Skan else 381169689Skan { 382169689Skan /* We have the code and we will scan it for the effects. */ 383169689Skan if (flags & ECF_PURE) 384169689Skan { 385169689Skan if (local->pure_const_state == IPA_CONST) 386169689Skan local->pure_const_state = IPA_PURE; 387169689Skan } 388169689Skan } 389169689Skan} 390169689Skan 391169689Skan/* TP is the part of the tree currently under the microscope. 392169689Skan WALK_SUBTREES is part of the walk_tree api but is unused here. 393169689Skan DATA is cgraph_node of the function being walked. */ 394169689Skan 395169689Skan/* FIXME: When this is converted to run over SSA form, this code 396169689Skan should be converted to use the operand scanner. */ 397169689Skan 398169689Skanstatic tree 399169689Skanscan_function (tree *tp, 400169689Skan int *walk_subtrees, 401169689Skan void *data) 402169689Skan{ 403169689Skan struct cgraph_node *fn = data; 404169689Skan tree t = *tp; 405169689Skan funct_state local = get_function_state (fn); 406169689Skan 407169689Skan switch (TREE_CODE (t)) 408169689Skan { 409169689Skan case VAR_DECL: 410169689Skan if (DECL_INITIAL (t)) 411169689Skan walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes); 412169689Skan *walk_subtrees = 0; 413169689Skan break; 414169689Skan 415169689Skan case MODIFY_EXPR: 416169689Skan { 417169689Skan /* First look on the lhs and see what variable is stored to */ 418169689Skan tree lhs = TREE_OPERAND (t, 0); 419169689Skan tree rhs = TREE_OPERAND (t, 1); 420169689Skan check_lhs_var (local, lhs); 421169689Skan 422169689Skan /* For the purposes of figuring out what the cast affects */ 423169689Skan 424169689Skan /* Next check the operands on the rhs to see if they are ok. */ 425169689Skan switch (TREE_CODE_CLASS (TREE_CODE (rhs))) 426169689Skan { 427169689Skan case tcc_binary: 428169689Skan { 429169689Skan tree op0 = TREE_OPERAND (rhs, 0); 430169689Skan tree op1 = TREE_OPERAND (rhs, 1); 431169689Skan check_rhs_var (local, op0); 432169689Skan check_rhs_var (local, op1); 433169689Skan } 434169689Skan break; 435169689Skan case tcc_unary: 436169689Skan { 437169689Skan tree op0 = TREE_OPERAND (rhs, 0); 438169689Skan check_rhs_var (local, op0); 439169689Skan } 440169689Skan 441169689Skan break; 442169689Skan case tcc_reference: 443169689Skan check_rhs_var (local, rhs); 444169689Skan break; 445169689Skan case tcc_declaration: 446169689Skan check_rhs_var (local, rhs); 447169689Skan break; 448169689Skan case tcc_expression: 449169689Skan switch (TREE_CODE (rhs)) 450169689Skan { 451169689Skan case ADDR_EXPR: 452169689Skan check_rhs_var (local, rhs); 453169689Skan break; 454169689Skan case CALL_EXPR: 455169689Skan check_call (local, rhs); 456169689Skan break; 457169689Skan default: 458169689Skan break; 459169689Skan } 460169689Skan break; 461169689Skan default: 462169689Skan break; 463169689Skan } 464169689Skan *walk_subtrees = 0; 465169689Skan } 466169689Skan break; 467169689Skan 468169689Skan case ADDR_EXPR: 469169689Skan /* This case is here to find addresses on rhs of constructors in 470169689Skan decl_initial of static variables. */ 471169689Skan check_rhs_var (local, t); 472169689Skan *walk_subtrees = 0; 473169689Skan break; 474169689Skan 475169689Skan case LABEL_EXPR: 476169689Skan if (DECL_NONLOCAL (TREE_OPERAND (t, 0))) 477169689Skan /* Target of long jump. */ 478169689Skan local->pure_const_state = IPA_NEITHER; 479169689Skan break; 480169689Skan 481169689Skan case CALL_EXPR: 482169689Skan check_call (local, t); 483169689Skan *walk_subtrees = 0; 484169689Skan break; 485169689Skan 486169689Skan case ASM_EXPR: 487169689Skan get_asm_expr_operands (local, t); 488169689Skan *walk_subtrees = 0; 489169689Skan break; 490169689Skan 491169689Skan default: 492169689Skan break; 493169689Skan } 494169689Skan return NULL; 495169689Skan} 496169689Skan 497169689Skan/* This is the main routine for finding the reference patterns for 498169689Skan global variables within a function FN. */ 499169689Skan 500169689Skanstatic void 501169689Skananalyze_function (struct cgraph_node *fn) 502169689Skan{ 503169689Skan funct_state l = XCNEW (struct funct_state_d); 504169689Skan tree decl = fn->decl; 505169689Skan struct ipa_dfs_info * w_info = fn->aux; 506169689Skan 507169689Skan w_info->aux = l; 508169689Skan 509169689Skan l->pure_const_state = IPA_CONST; 510169689Skan l->state_set_in_source = false; 511169689Skan 512169689Skan /* If this function does not return normally or does not bind local, 513169689Skan do not touch this unless it has been marked as const or pure by the 514169689Skan front end. */ 515169689Skan if (TREE_THIS_VOLATILE (decl) 516169689Skan || !targetm.binds_local_p (decl)) 517169689Skan { 518169689Skan l->pure_const_state = IPA_NEITHER; 519169689Skan return; 520169689Skan } 521169689Skan 522169689Skan if (TREE_READONLY (decl)) 523169689Skan { 524169689Skan l->pure_const_state = IPA_CONST; 525169689Skan l->state_set_in_source = true; 526169689Skan } 527169689Skan if (DECL_IS_PURE (decl)) 528169689Skan { 529169689Skan l->pure_const_state = IPA_PURE; 530169689Skan l->state_set_in_source = true; 531169689Skan } 532169689Skan 533169689Skan if (dump_file) 534169689Skan { 535169689Skan fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ", 536169689Skan cgraph_node_name (fn), 537169689Skan l->pure_const_state); 538169689Skan } 539169689Skan 540169689Skan if (!l->state_set_in_source) 541169689Skan { 542169689Skan struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); 543169689Skan basic_block this_block; 544169689Skan 545169689Skan FOR_EACH_BB_FN (this_block, this_cfun) 546169689Skan { 547169689Skan block_stmt_iterator bsi; 548169689Skan for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) 549169689Skan { 550169689Skan walk_tree (bsi_stmt_ptr (bsi), scan_function, 551169689Skan fn, visited_nodes); 552169689Skan if (l->pure_const_state == IPA_NEITHER) 553169689Skan goto end; 554169689Skan } 555169689Skan } 556169689Skan 557169689Skan if (l->pure_const_state != IPA_NEITHER) 558169689Skan { 559169689Skan tree old_decl = current_function_decl; 560169689Skan /* Const functions cannot have back edges (an 561169689Skan indication of possible infinite loop side 562169689Skan effect. */ 563169689Skan 564169689Skan current_function_decl = fn->decl; 565169689Skan 566169689Skan /* The C++ front end, has a tendency to some times jerk away 567169689Skan a function after it has created it. This should have 568169689Skan been fixed. */ 569169689Skan gcc_assert (DECL_STRUCT_FUNCTION (fn->decl)); 570169689Skan 571169689Skan push_cfun (DECL_STRUCT_FUNCTION (fn->decl)); 572169689Skan 573169689Skan if (mark_dfs_back_edges ()) 574169689Skan l->pure_const_state = IPA_NEITHER; 575169689Skan 576169689Skan current_function_decl = old_decl; 577169689Skan pop_cfun (); 578169689Skan } 579169689Skan } 580169689Skan 581169689Skanend: 582169689Skan if (dump_file) 583169689Skan { 584169689Skan fprintf (dump_file, "after local analysis of %s with initial value = %d\n ", 585169689Skan cgraph_node_name (fn), 586169689Skan l->pure_const_state); 587169689Skan } 588169689Skan} 589169689Skan 590169689Skan 591169689Skan/* Produce the global information by preforming a transitive closure 592169689Skan on the local information that was produced by ipa_analyze_function 593169689Skan and ipa_analyze_variable. */ 594169689Skan 595169689Skanstatic unsigned int 596169689Skanstatic_execute (void) 597169689Skan{ 598169689Skan struct cgraph_node *node; 599169689Skan struct cgraph_node *w; 600169689Skan struct cgraph_node **order = 601169689Skan XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 602169689Skan int order_pos = order_pos = ipa_utils_reduced_inorder (order, true, false); 603169689Skan int i; 604169689Skan struct ipa_dfs_info * w_info; 605169689Skan 606169689Skan if (!memory_identifier_string) 607169689Skan memory_identifier_string = build_string(7, "memory"); 608169689Skan 609169689Skan /* There are some shared nodes, in particular the initializers on 610169689Skan static declarations. We do not need to scan them more than once 611169689Skan since all we would be interested in are the addressof 612169689Skan operations. */ 613169689Skan visited_nodes = pointer_set_create (); 614169689Skan 615169689Skan /* Process all of the functions. 616169689Skan 617169689Skan We do not want to process any of the clones so we check that this 618169689Skan is a master clone. However, we do NOT process any 619169689Skan AVAIL_OVERWRITABLE functions (these are never clones) we cannot 620169689Skan guarantee that what we learn about the one we see will be true 621169689Skan for the one that overriders it. 622169689Skan */ 623169689Skan for (node = cgraph_nodes; node; node = node->next) 624169689Skan if (node->analyzed && cgraph_is_master_clone (node)) 625169689Skan analyze_function (node); 626169689Skan 627169689Skan pointer_set_destroy (visited_nodes); 628169689Skan visited_nodes = NULL; 629169689Skan if (dump_file) 630169689Skan { 631169689Skan dump_cgraph (dump_file); 632169689Skan ipa_utils_print_order(dump_file, "reduced", order, order_pos); 633169689Skan } 634169689Skan 635169689Skan /* Propagate the local information thru the call graph to produce 636169689Skan the global information. All the nodes within a cycle will have 637169689Skan the same info so we collapse cycles first. Then we can do the 638169689Skan propagation in one pass from the leaves to the roots. */ 639169689Skan for (i = 0; i < order_pos; i++ ) 640169689Skan { 641169689Skan enum pure_const_state_e pure_const_state = IPA_CONST; 642235623Spfg int count = 0; 643169689Skan node = order[i]; 644169689Skan 645169689Skan /* Find the worst state for any node in the cycle. */ 646169689Skan w = node; 647169689Skan while (w) 648169689Skan { 649169689Skan funct_state w_l = get_function_state (w); 650169689Skan if (pure_const_state < w_l->pure_const_state) 651169689Skan pure_const_state = w_l->pure_const_state; 652169689Skan 653169689Skan if (pure_const_state == IPA_NEITHER) 654169689Skan break; 655169689Skan 656169689Skan if (!w_l->state_set_in_source) 657169689Skan { 658169689Skan struct cgraph_edge *e; 659235623Spfg count++; 660235623Spfg 661235623Spfg /* FIXME!!! Because of pr33826, we cannot have either 662235623Spfg immediate or transitive recursive functions marked as 663235623Spfg pure or const because dce can delete a function that 664235623Spfg is in reality an infinite loop. A better solution 665235623Spfg than just outlawing them is to add another bit the 666235623Spfg functions to distinguish recursive from non recursive 667235623Spfg pure and const function. This would allow the 668235623Spfg recursive ones to be cse'd but not dce'd. In this 669235623Spfg same vein, we could allow functions with loops to 670235623Spfg also be cse'd but not dce'd. 671235623Spfg 672235623Spfg Unfortunately we are late in stage 3, and the fix 673235623Spfg described above is is not appropriate. */ 674235623Spfg if (count > 1) 675235623Spfg { 676235623Spfg pure_const_state = IPA_NEITHER; 677235623Spfg break; 678235623Spfg } 679235623Spfg 680169689Skan for (e = w->callees; e; e = e->next_callee) 681169689Skan { 682169689Skan struct cgraph_node *y = e->callee; 683169689Skan /* Only look at the master nodes and skip external nodes. */ 684169689Skan y = cgraph_master_clone (y); 685235623Spfg 686235623Spfg /* Check for immediate recursive functions. See the 687235623Spfg FIXME above. */ 688235623Spfg if (w == y) 689235623Spfg { 690235623Spfg pure_const_state = IPA_NEITHER; 691235623Spfg break; 692235623Spfg } 693169689Skan if (y) 694169689Skan { 695169689Skan funct_state y_l = get_function_state (y); 696169689Skan if (pure_const_state < y_l->pure_const_state) 697169689Skan pure_const_state = y_l->pure_const_state; 698169689Skan if (pure_const_state == IPA_NEITHER) 699169689Skan break; 700169689Skan } 701169689Skan } 702169689Skan } 703169689Skan w_info = w->aux; 704169689Skan w = w_info->next_cycle; 705169689Skan } 706169689Skan 707169689Skan /* Copy back the region's pure_const_state which is shared by 708169689Skan all nodes in the region. */ 709169689Skan w = node; 710169689Skan while (w) 711169689Skan { 712169689Skan funct_state w_l = get_function_state (w); 713169689Skan 714169689Skan /* All nodes within a cycle share the same info. */ 715169689Skan if (!w_l->state_set_in_source) 716169689Skan { 717169689Skan w_l->pure_const_state = pure_const_state; 718169689Skan switch (pure_const_state) 719169689Skan { 720169689Skan case IPA_CONST: 721169689Skan TREE_READONLY (w->decl) = 1; 722169689Skan if (dump_file) 723169689Skan fprintf (dump_file, "Function found to be const: %s\n", 724169689Skan lang_hooks.decl_printable_name(w->decl, 2)); 725169689Skan break; 726169689Skan 727169689Skan case IPA_PURE: 728169689Skan DECL_IS_PURE (w->decl) = 1; 729169689Skan if (dump_file) 730169689Skan fprintf (dump_file, "Function found to be pure: %s\n", 731169689Skan lang_hooks.decl_printable_name(w->decl, 2)); 732169689Skan break; 733169689Skan 734169689Skan default: 735169689Skan break; 736169689Skan } 737169689Skan } 738169689Skan w_info = w->aux; 739169689Skan w = w_info->next_cycle; 740169689Skan } 741169689Skan } 742169689Skan 743169689Skan /* Cleanup. */ 744169689Skan for (node = cgraph_nodes; node; node = node->next) 745169689Skan /* Get rid of the aux information. */ 746169689Skan if (node->aux) 747169689Skan { 748169689Skan w_info = node->aux; 749169689Skan if (w_info->aux) 750169689Skan free (w_info->aux); 751169689Skan free (node->aux); 752169689Skan node->aux = NULL; 753169689Skan } 754169689Skan 755169689Skan free (order); 756169689Skan return 0; 757169689Skan} 758169689Skan 759169689Skanstatic bool 760169689Skangate_pure_const (void) 761169689Skan{ 762169689Skan return (flag_unit_at_a_time != 0 && flag_ipa_pure_const 763169689Skan /* Don't bother doing anything if the program has errors. */ 764169689Skan && !(errorcount || sorrycount)); 765169689Skan} 766169689Skan 767169689Skanstruct tree_opt_pass pass_ipa_pure_const = 768169689Skan{ 769169689Skan "pure-const", /* name */ 770169689Skan gate_pure_const, /* gate */ 771169689Skan static_execute, /* execute */ 772169689Skan NULL, /* sub */ 773169689Skan NULL, /* next */ 774169689Skan 0, /* static_pass_number */ 775169689Skan TV_IPA_PURE_CONST, /* tv_id */ 776169689Skan 0, /* properties_required */ 777169689Skan 0, /* properties_provided */ 778169689Skan 0, /* properties_destroyed */ 779169689Skan 0, /* todo_flags_start */ 780169689Skan 0, /* todo_flags_finish */ 781169689Skan 0 /* letter */ 782169689Skan}; 783169689Skan 784169689Skan 785