gcc/ipa-pure-const.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004, 2005, 2007, 2008 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 marks functions as being either const (TREE_READONLY) or
  22    pure (DECL_PURE_P).  It can also set a variant of these that
  23    are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
  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 "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
  56 static 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.  */
  61 enum pure_const_state_e
  62 {
  63   IPA_CONST,
  64   IPA_PURE,
  65   IPA_NEITHER
  66 };
  67
  68 /* Holder for the const_state.  There is one of these per function
  69    decl.  */
  70 struct funct_state_d
  71 {
  72   /* See above.  */
  73   enum pure_const_state_e pure_const_state;
  74
  75   /* True if the function could possibly infinite loop.  There are a
  76      lot of ways that this could be determined.  We are pretty
  77      conservative here.  While it is possible to cse pure and const
  78      calls, it is not legal to have dce get rid of the call if there
  79      is a possibility that the call could infinite loop since this is
  80      a behavioral change.  */
  81   bool looping;
  82
  83   /* If the state of the function was set in the source, then assume
  84      that it was done properly even if the analysis we do would be
  85      more pessimestic.  */
  86   bool state_set_in_source;
  87 };
  88
  89 typedef struct funct_state_d * funct_state;
  90
  91 /* The storage of the funct_state is abstracted because there is the
  92    possibility that it may be desirable to move this to the cgraph
  93    local info.  */
  94
  95 /* Array, indexed by cgraph node uid, of function states.  */
  96
  97 DEF_VEC_P (funct_state);
  98 DEF_VEC_ALLOC_P (funct_state, heap);
  99 static VEC (funct_state, heap) *funct_state_vec;
 100
 101 /* Holders of ipa cgraph hooks: */
 102 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 103 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 104 static struct cgraph_node_hook_list *node_removal_hook_holder;
 105
 106 /* Init the function state.  */
 107
 108 static void
 109 finish_state (void)
 110 {
 111   free (funct_state_vec);
 112 }
 113
 114
 115 /* Return the function state from NODE.  */
 116
 117 static inline funct_state
 118 get_function_state (struct cgraph_node *node)
 119 {
 120   if (!funct_state_vec
 121       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 122     return NULL;
 123   return VEC_index (funct_state, funct_state_vec, node->uid);
 124 }
 125
 126 /* Set the function state S for NODE.  */
 127
 128 static inline void
 129 set_function_state (struct cgraph_node *node, funct_state s)
 130 {
 131   if (!funct_state_vec
 132       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 133      VEC_safe_grow_cleared (funct_state, heap, funct_state_vec, node->uid + 1);
 134   VEC_replace (funct_state, funct_state_vec, node->uid, s);
 135 }
 136
 137 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 138    variable T is legal in a function that is either pure or const.  */
 139
 140 static inline void
 141 check_decl (funct_state local,
 142             tree t, bool checking_write)
 143 {
 144   /* If the variable has the "used" attribute, treat it as if it had a
 145      been touched by the devil.  */
 146   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
 147     {
 148       local->pure_const_state = IPA_NEITHER;
 149       local->looping = false;
 150       return;
 151     }
 152
 153   /* Do not want to do anything with volatile except mark any
 154      function that uses one to be not const or pure.  */
 155   if (TREE_THIS_VOLATILE (t))
 156     {
 157       local->pure_const_state = IPA_NEITHER;
 158       local->looping = false;
 159       return;
 160     }
 161
 162   /* Do not care about a local automatic that is not static.  */
 163   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 164     return;
 165
 166   /* Since we have dealt with the locals and params cases above, if we
 167      are CHECKING_WRITE, this cannot be a pure or constant
 168      function.  */
 169   if (checking_write)
 170     {
 171       local->pure_const_state = IPA_NEITHER;
 172       local->looping = false;
 173       return;
 174     }
 175
 176   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 177     {
 178       /* If the front end set the variable to be READONLY and
 179          constant, we can allow this variable in pure or const
 180          functions but the scope is too large for our analysis to set
 181          these bits ourselves.  */
 182
 183       if (TREE_READONLY (t)
 184           && DECL_INITIAL (t)
 185           && is_gimple_min_invariant (DECL_INITIAL (t)))
 186         ; /* Read of a constant, do not change the function state.  */
 187       else
 188         {
 189           /* Just a regular read.  */
 190           if (local->pure_const_state == IPA_CONST)
 191             local->pure_const_state = IPA_PURE;
 192         }
 193     }
 194
 195   /* Compilation level statics can be read if they are readonly
 196      variables.  */
 197   if (TREE_READONLY (t))
 198     return;
 199
 200   /* Just a regular read.  */
 201   if (local->pure_const_state == IPA_CONST)
 202     local->pure_const_state = IPA_PURE;
 203 }
 204
 205 /* If T is a VAR_DECL check to see if it is an allowed reference.  */
 206
 207 static void
 208 check_operand (funct_state local,
 209                tree t, bool checking_write)
 210 {
 211   if (!t) return;
 212
 213   if (TREE_CODE (t) == VAR_DECL)
 214     check_decl (local, t, checking_write);
 215 }
 216
 217 /* Examine tree T for references.  */
 218
 219 static void
 220 check_tree (funct_state local, tree t, bool checking_write)
 221 {
 222   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)
 223       || TREE_CODE (t) == SSA_NAME)
 224     return;
 225
 226   /* Any tree which is volatile disqualifies this function from being
 227      const or pure. */
 228   if (TREE_THIS_VOLATILE (t))
 229     {
 230       local->pure_const_state = IPA_NEITHER;
 231       local->looping = false;
 232       return;
 233     }
 234
 235   while (TREE_CODE (t) == REALPART_EXPR
 236          || TREE_CODE (t) == IMAGPART_EXPR
 237          || handled_component_p (t))
 238     {
 239       if (TREE_CODE (t) == ARRAY_REF)
 240         check_operand (local, TREE_OPERAND (t, 1), false);
 241       t = TREE_OPERAND (t, 0);
 242     }
 243
 244   /* The bottom of an indirect reference can only be read, not
 245      written.  */
 246   if (INDIRECT_REF_P (t))
 247     {
 248       check_tree (local, TREE_OPERAND (t, 0), false);
 249
 250       /* Any indirect reference that occurs on the lhs
 251          disqualifies the function from being pure or const. Any
 252          indirect reference that occurs on the rhs disqualifies the
 253          function from being const.  */
 254       if (checking_write)
 255         {
 256           local->pure_const_state = IPA_NEITHER;
 257           local->looping = false;
 258           return;
 259         }
 260       else if (local->pure_const_state == IPA_CONST)
 261         local->pure_const_state = IPA_PURE;
 262     }
 263
 264   if (SSA_VAR_P (t))
 265     check_operand (local, t, checking_write);
 266 }
 267
 268 /* Scan tree T to see if there are any addresses taken in within T.  */
 269
 270 static void
 271 look_for_address_of (funct_state local, tree t)
 272 {
 273   if (TREE_CODE (t) == ADDR_EXPR)
 274     {
 275       tree x = get_base_var (t);
 276       if (TREE_CODE (x) == VAR_DECL)
 277         {
 278           check_decl (local, x, false);
 279
 280           /* Taking the address of something appears to be reasonable
 281              in PURE code.  Not allowed in const.  */
 282           if (local->pure_const_state == IPA_CONST)
 283             local->pure_const_state = IPA_PURE;
 284         }
 285     }
 286 }
 287
 288 /* Check to see if T is a read or address of operation on a var we are
 289    interested in analyzing.  LOCAL is passed in to get access to its
 290    bit vectors.  */
 291
 292 static void
 293 check_rhs_var (funct_state local, tree t)
 294 {
 295   look_for_address_of (local, t);
 296
 297   /* Memcmp and strlen can both trap and they are declared pure.  */
 298   if (tree_could_trap_p (t)
 299       && local->pure_const_state == IPA_CONST)
 300     local->pure_const_state = IPA_PURE;
 301
 302   check_tree(local, t, false);
 303 }
 304
 305 /* Check to see if T is an assignment to a var we are interested in
 306    analyzing.  LOCAL is passed in to get access to its bit vectors. */
 307
 308 static void
 309 check_lhs_var (funct_state local, tree t)
 310 {
 311   /* Memcmp and strlen can both trap and they are declared pure.
 312      Which seems to imply that we can apply the same rule here.  */
 313   if (tree_could_trap_p (t)
 314       && local->pure_const_state == IPA_CONST)
 315     local->pure_const_state = IPA_PURE;
 316
 317   check_tree(local, t, true);
 318 }
 319
 320 /* This is a scaled down version of get_asm_expr_operands from
 321    tree_ssa_operands.c.  The version there runs much later and assumes
 322    that aliasing information is already available. Here we are just
 323    trying to find if the set of inputs and outputs contain references
 324    or address of operations to local static variables.  STMT is the
 325    actual asm statement.  */
 326
 327 static void
 328 get_asm_expr_operands (funct_state local, gimple stmt)
 329 {
 330   size_t noutputs = gimple_asm_noutputs (stmt);
 331   const char **oconstraints
 332     = (const char **) alloca ((noutputs) * sizeof (const char *));
 333   size_t i;
 334   tree op;
 335   const char *constraint;
 336   bool allows_mem, allows_reg, is_inout;
 337
 338   for (i = 0; i < noutputs; i++)
 339     {
 340       op = gimple_asm_output_op (stmt, i);
 341       oconstraints[i] = constraint
 342         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
 343       parse_output_constraint (&constraint, i, 0, 0,
 344                                &allows_mem, &allows_reg, &is_inout);
 345
 346       check_lhs_var (local, TREE_VALUE (op));
 347     }
 348
 349   for (i = 0; i < gimple_asm_ninputs (stmt); i++)
 350     {
 351       op = gimple_asm_input_op (stmt, i);
 352       constraint
 353         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
 354       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
 355                               oconstraints, &allows_mem, &allows_reg);
 356
 357       check_rhs_var (local, TREE_VALUE (op));
 358     }
 359
 360   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 361     {
 362       op = gimple_asm_clobber_op (stmt, i);
 363       if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1)
 364         /* Abandon all hope, ye who enter here. */
 365         local->pure_const_state = IPA_NEITHER;
 366     }
 367
 368   if (gimple_asm_volatile_p (stmt))
 369     local->pure_const_state = IPA_NEITHER;
 370 }
 371
 372 /* Check the parameters of a function call to CALL_EXPR to see if
 373    there are any references in the parameters that are not allowed for
 374    pure or const functions.  Also check to see if this is either an
 375    indirect call, a call outside the compilation unit, or has special
 376    attributes that may also effect the purity.  The CALL_EXPR node for
 377    the entire call expression.  */
 378
 379 static void
 380 check_call (funct_state local, gimple call)
 381 {
 382   int flags = gimple_call_flags (call);
 383   tree lhs, callee_t = gimple_call_fndecl (call);
 384   struct cgraph_node* callee;
 385   enum availability avail = AVAIL_NOT_AVAILABLE;
 386   size_t i;
 387
 388   lhs = gimple_call_lhs (call);
 389   if (lhs)
 390     check_lhs_var (local, lhs);
 391
 392   for (i = 0; i < gimple_call_num_args (call); i++)
 393     check_rhs_var (local, gimple_call_arg (call, i));
 394
 395   /* The const and pure flags are set by a variety of places in the
 396      compiler (including here).  If someone has already set the flags
 397      for the callee, (such as for some of the builtins) we will use
 398      them, otherwise we will compute our own information.
 399
 400      Const and pure functions have less clobber effects than other
 401      functions so we process these first.  Otherwise if it is a call
 402      outside the compilation unit or an indirect call we punt.  This
 403      leaves local calls which will be processed by following the call
 404      graph.  */
 405   if (callee_t)
 406     {
 407       callee = cgraph_node(callee_t);
 408       avail = cgraph_function_body_availability (callee);
 409
 410       /* When bad things happen to bad functions, they cannot be const
 411          or pure.  */
 412       if (setjmp_call_p (callee_t))
 413         {
 414           local->pure_const_state = IPA_NEITHER;
 415           local->looping = false;
 416         }
 417
 418       if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
 419         switch (DECL_FUNCTION_CODE (callee_t))
 420           {
 421           case BUILT_IN_LONGJMP:
 422           case BUILT_IN_NONLOCAL_GOTO:
 423             local->pure_const_state = IPA_NEITHER;
 424             local->looping = false;
 425             break;
 426           default:
 427             break;
 428           }
 429     }
 430
 431   /* The callee is either unknown (indirect call) or there is just no
 432      scannable code for it (external call) .  We look to see if there
 433      are any bits available for the callee (such as by declaration or
 434      because it is builtin) and process solely on the basis of those
 435      bits. */
 436   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 437     {
 438       if (flags & ECF_PURE)
 439         {
 440           if (local->pure_const_state == IPA_CONST)
 441             local->pure_const_state = IPA_PURE;
 442         }
 443       else
 444         local->pure_const_state = IPA_NEITHER;
 445     }
 446   else
 447     {
 448       /* We have the code and we will scan it for the effects. */
 449       if (flags & ECF_PURE)
 450         {
 451           if (local->pure_const_state == IPA_CONST)
 452             local->pure_const_state = IPA_PURE;
 453         }
 454     }
 455 }
 456
 457 /* TP is the part of the tree currently under the microscope.
 458    WALK_SUBTREES is part of the walk_tree api but is unused here.
 459    DATA is cgraph_node of the function being walked.  */
 460
 461 /* FIXME: When this is converted to run over SSA form, this code
 462    should be converted to use the operand scanner.  */
 463
 464 static tree
 465 scan_function_op (tree *tp, int *walk_subtrees, void *data)
 466 {
 467   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 468   struct cgraph_node *fn = (struct cgraph_node *) wi->info;
 469   tree t = *tp;
 470   funct_state local = get_function_state (fn);
 471
 472   switch (TREE_CODE (t))
 473     {
 474     case VAR_DECL:
 475       if (DECL_INITIAL (t))
 476         walk_tree (&DECL_INITIAL (t), scan_function_op, data, visited_nodes);
 477       *walk_subtrees = 0;
 478       break;
 479
 480     case ADDR_EXPR:
 481       /* This case is here to find addresses on rhs of constructors in
 482          decl_initial of static variables. */
 483       check_rhs_var (local, t);
 484       *walk_subtrees = 0;
 485       break;
 486
 487     default:
 488       break;
 489     }
 490   return NULL;
 491 }
 492
 493 static tree
 494 scan_function_stmt (gimple_stmt_iterator *gsi_p,
 495                     bool *handled_ops_p,
 496                     struct walk_stmt_info *wi)
 497 {
 498   struct cgraph_node *fn = (struct cgraph_node *) wi->info;
 499   gimple stmt = gsi_stmt (*gsi_p);
 500   funct_state local = get_function_state (fn);
 501
 502   switch (gimple_code (stmt))
 503     {
 504     case GIMPLE_ASSIGN:
 505       {
 506         /* First look on the lhs and see what variable is stored to */
 507         tree lhs = gimple_assign_lhs (stmt);
 508         tree rhs1 = gimple_assign_rhs1 (stmt);
 509         tree rhs2 = gimple_assign_rhs2 (stmt);
 510         enum tree_code code = gimple_assign_rhs_code (stmt);
 511
 512         check_lhs_var (local, lhs);
 513
 514         /* For the purposes of figuring out what the cast affects */
 515
 516         /* Next check the operands on the rhs to see if they are ok. */
 517         switch (TREE_CODE_CLASS (code))
 518           {
 519           case tcc_binary:
 520             {
 521               check_rhs_var (local, rhs1);
 522               check_rhs_var (local, rhs2);
 523             }
 524             break;
 525           case tcc_unary:
 526             {
 527               check_rhs_var (local, rhs1);
 528             }
 529
 530             break;
 531           case tcc_reference:
 532             check_rhs_var (local, rhs1);
 533             break;
 534           case tcc_declaration:
 535             check_rhs_var (local, rhs1);
 536             break;
 537           case tcc_expression:
 538             switch (code)
 539               {
 540               case ADDR_EXPR:
 541                 check_rhs_var (local, rhs1);
 542                 break;
 543               default:
 544                 break;
 545               }
 546             break;
 547           default:
 548             break;
 549           }
 550         *handled_ops_p = true;
 551       }
 552       break;
 553
 554     case GIMPLE_LABEL:
 555       if (DECL_NONLOCAL (gimple_label_label (stmt)))
 556         /* Target of long jump. */
 557         {
 558           local->pure_const_state = IPA_NEITHER;
 559           local->looping = false;
 560         }
 561       break;
 562
 563     case GIMPLE_CALL:
 564       check_call (local, stmt);
 565       *handled_ops_p = true;
 566       break;
 567
 568     case GIMPLE_ASM:
 569       get_asm_expr_operands (local, stmt);
 570       *handled_ops_p = true;
 571       break;
 572
 573     default:
 574       break;
 575     }
 576   return NULL;
 577 }
 578
 579
 580 /* This is the main routine for finding the reference patterns for
 581    global variables within a function FN.  */
 582
 583 static void
 584 analyze_function (struct cgraph_node *fn)
 585 {
 586   tree decl = fn->decl;
 587   funct_state l = XCNEW (struct funct_state_d);
 588
 589  if (cgraph_function_body_availability (fn) <= AVAIL_OVERWRITABLE)
 590    return;
 591
 592   set_function_state (fn, l);
 593
 594   l->pure_const_state = IPA_CONST;
 595   l->state_set_in_source = false;
 596   if (DECL_LOOPING_CONST_OR_PURE_P (decl))
 597     l->looping = true;
 598   else
 599     l->looping = false;
 600
 601   /* If this function does not return normally or does not bind local,
 602      do not touch this unless it has been marked as const or pure by the
 603      front end.  */
 604   if (TREE_THIS_VOLATILE (decl)
 605       || !targetm.binds_local_p (decl))
 606     {
 607       l->pure_const_state = IPA_NEITHER;
 608       return;
 609     }
 610
 611   if (TREE_READONLY (decl))
 612     {
 613       l->pure_const_state = IPA_CONST;
 614       l->state_set_in_source = true;
 615     }
 616   if (DECL_PURE_P (decl))
 617     {
 618       l->pure_const_state = IPA_PURE;
 619       l->state_set_in_source = true;
 620     }
 621
 622   if (dump_file)
 623     {
 624       fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ",
 625                cgraph_node_name (fn),
 626                l->pure_const_state);
 627     }
 628
 629   if (!l->state_set_in_source)
 630     {
 631       struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 632       basic_block this_block;
 633
 634       FOR_EACH_BB_FN (this_block, this_cfun)
 635         {
 636           gimple_stmt_iterator gsi;
 637           struct walk_stmt_info wi;
 638
 639           memset (&wi, 0, sizeof(wi));
 640           for (gsi = gsi_start_bb (this_block);
 641                !gsi_end_p (gsi);
 642                gsi_next (&gsi))
 643             {
 644               wi.info = fn;
 645               wi.pset = visited_nodes;
 646               walk_gimple_stmt (&gsi, scan_function_stmt, scan_function_op,
 647                                 &wi);
 648               if (l->pure_const_state == IPA_NEITHER)
 649                 goto end;
 650             }
 651         }
 652
 653       if (l->pure_const_state != IPA_NEITHER)
 654         {
 655           tree old_decl = current_function_decl;
 656           /* Const functions cannot have back edges (an
 657              indication of possible infinite loop side
 658              effect.  */
 659
 660           current_function_decl = fn->decl;
 661
 662           /* The C++ front end, has a tendency to some times jerk away
 663              a function after it has created it.  This should have
 664              been fixed.  */
 665           gcc_assert (DECL_STRUCT_FUNCTION (fn->decl));
 666
 667           push_cfun (DECL_STRUCT_FUNCTION (fn->decl));
 668
 669           if (mark_dfs_back_edges ())
 670             l->pure_const_state = IPA_NEITHER;
 671
 672           current_function_decl = old_decl;
 673           pop_cfun ();
 674         }
 675     }
 676
 677 end:
 678   if (dump_file)
 679     {
 680       fprintf (dump_file, "after local analysis of %s with initial value = %d\n ",
 681                cgraph_node_name (fn),
 682                l->pure_const_state);
 683     }
 684 }
 685
 686 /* Called when new function is inserted to callgraph late.  */
 687 static void
 688 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 689 {
 690  if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 691    return;
 692   /* There are some shared nodes, in particular the initializers on
 693      static declarations.  We do not need to scan them more than once
 694      since all we would be interested in are the addressof
 695      operations.  */
 696   visited_nodes = pointer_set_create ();
 697   analyze_function (node);
 698   pointer_set_destroy (visited_nodes);
 699   visited_nodes = NULL;
 700 }
 701
 702 /* Called when new clone is inserted to callgraph late.  */
 703
 704 static void
 705 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 706                      void *data ATTRIBUTE_UNUSED)
 707 {
 708   if (get_function_state (src))
 709     {
 710       funct_state l = XNEW (struct funct_state_d);
 711       gcc_assert (!get_function_state (dst));
 712       memcpy (l, get_function_state (src), sizeof (*l));
 713       set_function_state (dst, l);
 714     }
 715 }
 716
 717 /* Called when new clone is inserted to callgraph late.  */
 718
 719 static void
 720 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 721 {
 722   if (get_function_state (node))
 723     {
 724       free (get_function_state (node));
 725       set_function_state (node, NULL);
 726     }
 727 }
 728
 729 \f
 730 /* Analyze each function in the cgraph to see if it is locally PURE or
 731    CONST.  */
 732
 733 static void
 734 generate_summary (void)
 735 {
 736   struct cgraph_node *node;
 737
 738   node_removal_hook_holder =
 739       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 740   node_duplication_hook_holder =
 741       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 742   function_insertion_hook_holder =
 743       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 744   /* There are some shared nodes, in particular the initializers on
 745      static declarations.  We do not need to scan them more than once
 746      since all we would be interested in are the addressof
 747      operations.  */
 748   visited_nodes = pointer_set_create ();
 749
 750   /* Process all of the functions.
 751
 752      We do NOT process any AVAIL_OVERWRITABLE functions, we cannot
 753      guarantee that what we learn about the one we see will be true
 754      for the one that overrides it.
 755   */
 756   for (node = cgraph_nodes; node; node = node->next)
 757     if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 758       analyze_function (node);
 759
 760   pointer_set_destroy (visited_nodes);
 761   visited_nodes = NULL;
 762 }
 763
 764 /* Produce the global information by preforming a transitive closure
 765    on the local information that was produced by generate_summary.
 766    Note that there is no function_transform pass since this only
 767    updates the function_decl.  */
 768
 769 static unsigned int
 770 propagate (void)
 771 {
 772   struct cgraph_node *node;
 773   struct cgraph_node *w;
 774   struct cgraph_node **order =
 775     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 776   int order_pos;
 777   int i;
 778   struct ipa_dfs_info * w_info;
 779
 780   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
 781   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
 782   cgraph_remove_node_removal_hook (node_removal_hook_holder);
 783   order_pos = ipa_utils_reduced_inorder (order, true, false);
 784   if (dump_file)
 785     {
 786       dump_cgraph (dump_file);
 787       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 788     }
 789
 790   /* Propagate the local information thru the call graph to produce
 791      the global information.  All the nodes within a cycle will have
 792      the same info so we collapse cycles first.  Then we can do the
 793      propagation in one pass from the leaves to the roots.  */
 794   for (i = 0; i < order_pos; i++ )
 795     {
 796       enum pure_const_state_e pure_const_state = IPA_CONST;
 797       bool looping = false;
 798       int count = 0;
 799       node = order[i];
 800
 801       /* Find the worst state for any node in the cycle.  */
 802       w = node;
 803       while (w)
 804         {
 805           funct_state w_l = get_function_state (w);
 806           if (pure_const_state < w_l->pure_const_state)
 807             pure_const_state = w_l->pure_const_state;
 808
 809           if (w_l->looping)
 810             looping = true;
 811
 812           if (pure_const_state == IPA_NEITHER)
 813             break;
 814
 815           if (!w_l->state_set_in_source)
 816             {
 817               struct cgraph_edge *e;
 818               count++;
 819
 820               if (count > 1)
 821                 looping = true;
 822
 823               for (e = w->callees; e; e = e->next_callee)
 824                 {
 825                   struct cgraph_node *y = e->callee;
 826
 827                   if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 828                     {
 829                       funct_state y_l = get_function_state (y);
 830                       if (pure_const_state < y_l->pure_const_state)
 831                         pure_const_state = y_l->pure_const_state;
 832                       if (pure_const_state == IPA_NEITHER)
 833                         break;
 834                       if (y_l->looping)
 835                         looping = true;
 836                     }
 837                 }
 838             }
 839           w_info = (struct ipa_dfs_info *) w->aux;
 840           w = w_info->next_cycle;
 841         }
 842
 843       /* Copy back the region's pure_const_state which is shared by
 844          all nodes in the region.  */
 845       w = node;
 846       while (w)
 847         {
 848           funct_state w_l = get_function_state (w);
 849
 850           /* All nodes within a cycle share the same info.  */
 851           if (!w_l->state_set_in_source)
 852             {
 853               w_l->pure_const_state = pure_const_state;
 854               w_l->looping = looping;
 855
 856               switch (pure_const_state)
 857                 {
 858                 case IPA_CONST:
 859                   TREE_READONLY (w->decl) = 1;
 860                   DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
 861                   if (dump_file)
 862                     fprintf (dump_file, "Function found to be %sconst: %s\n",
 863                              looping ? "looping " : "",
 864                              lang_hooks.decl_printable_name(w->decl, 2));
 865                   break;
 866
 867                 case IPA_PURE:
 868                   DECL_PURE_P (w->decl) = 1;
 869                   DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
 870                   if (dump_file)
 871                     fprintf (dump_file, "Function found to be %spure: %s\n",
 872                              looping ? "looping " : "",
 873                              lang_hooks.decl_printable_name(w->decl, 2));
 874                   break;
 875
 876                 default:
 877                   break;
 878                 }
 879             }
 880           w_info = (struct ipa_dfs_info *) w->aux;
 881           w = w_info->next_cycle;
 882         }
 883     }
 884
 885   /* Cleanup. */
 886   for (node = cgraph_nodes; node; node = node->next)
 887     {
 888       /* Get rid of the aux information.  */
 889       if (node->aux)
 890         {
 891           w_info = (struct ipa_dfs_info *) node->aux;
 892           free (node->aux);
 893           node->aux = NULL;
 894         }
 895       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 896         free (get_function_state (node));
 897     }
 898
 899   free (order);
 900   VEC_free (funct_state, heap, funct_state_vec);
 901   finish_state ();
 902   return 0;
 903 }
 904
 905 static bool
 906 gate_pure_const (void)
 907 {
 908   return (flag_ipa_pure_const
 909           /* Don't bother doing anything if the program has errors.  */
 910           && !(errorcount || sorrycount));
 911 }
 912
 913 struct ipa_opt_pass pass_ipa_pure_const =
 914 {
 915  {
 916   IPA_PASS,
 917   "pure-const",                         /* name */
 918   gate_pure_const,                      /* gate */
 919   propagate,                            /* execute */
 920   NULL,                                 /* sub */
 921   NULL,                                 /* next */
 922   0,                                    /* static_pass_number */
 923   TV_IPA_PURE_CONST,                    /* tv_id */
 924   0,                                    /* properties_required */
 925   0,                                    /* properties_provided */
 926   0,                                    /* properties_destroyed */
 927   0,                                    /* todo_flags_start */
 928   0                                     /* todo_flags_finish */
 929  },
 930  generate_summary,                      /* generate_summary */
 931  NULL,                                  /* write_summary */
 932  NULL,                                  /* read_summary */
 933  NULL,                                  /* function_read_summary */
 934  0,                                     /* TODOs */
 935  NULL,                                  /* function_transform */
 936  NULL                                   /* variable_transform */
 937 };