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