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   /* What user set here; we can be always sure about this.  */
  75   enum pure_const_state_e state_set_in_source;
  76
  77   /* True if the function could possibly infinite loop.  There are a
  78      lot of ways that this could be determined.  We are pretty
  79      conservative here.  While it is possible to cse pure and const
  80      calls, it is not legal to have dce get rid of the call if there
  81      is a possibility that the call could infinite loop since this is
  82      a behavioral change.  */
  83   bool looping;
  84
  85   bool can_throw;
  86 };
  87
  88 typedef struct funct_state_d * funct_state;
  89
  90 /* The storage of the funct_state is abstracted because there is the
  91    possibility that it may be desirable to move this to the cgraph
  92    local info.  */
  93
  94 /* Array, indexed by cgraph node uid, of function states.  */
  95
  96 DEF_VEC_P (funct_state);
  97 DEF_VEC_ALLOC_P (funct_state, heap);
  98 static VEC (funct_state, heap) *funct_state_vec;
  99
 100 /* Holders of ipa cgraph hooks: */
 101 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 102 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 103 static struct cgraph_node_hook_list *node_removal_hook_holder;
 104
 105 /* Init the function state.  */
 106
 107 static void
 108 finish_state (void)
 109 {
 110   free (funct_state_vec);
 111 }
 112
 113
 114 /* Return the function state from NODE.  */
 115
 116 static inline funct_state
 117 get_function_state (struct cgraph_node *node)
 118 {
 119   if (!funct_state_vec
 120       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 121     return NULL;
 122   return VEC_index (funct_state, funct_state_vec, node->uid);
 123 }
 124
 125 /* Set the function state S for NODE.  */
 126
 127 static inline void
 128 set_function_state (struct cgraph_node *node, funct_state s)
 129 {
 130   if (!funct_state_vec
 131       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 132      VEC_safe_grow_cleared (funct_state, heap, funct_state_vec, node->uid + 1);
 133   VEC_replace (funct_state, 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   /* Do not want to do anything with volatile except mark any
 144      function that uses one to be not const or pure.  */
 145   if (TREE_THIS_VOLATILE (t))
 146     {
 147       local->pure_const_state = IPA_NEITHER;
 148       if (dump_file)
 149         fprintf (dump_file, "    Volatile operand is not const/pure");
 150       return;
 151     }
 152
 153   /* Do not care about a local automatic that is not static.  */
 154   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 155     return;
 156
 157   /* If the variable has the "used" attribute, treat it as if it had a
 158      been touched by the devil.  */
 159   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
 160     {
 161       local->pure_const_state = IPA_NEITHER;
 162       if (dump_file)
 163         fprintf (dump_file, "    Used static/global variable is not const/pure\n");
 164       return;
 165     }
 166
 167   /* Since we have dealt with the locals and params cases above, if we
 168      are CHECKING_WRITE, this cannot be a pure or constant
 169      function.  */
 170   if (checking_write)
 171     {
 172       local->pure_const_state = IPA_NEITHER;
 173       if (dump_file)
 174         fprintf (dump_file, "    static/global memory write is not const/pure\n");
 175       return;
 176     }
 177
 178   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 179     {
 180       /* Readonly reads are safe.  */
 181       if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
 182         return; /* Read of a constant, do not change the function state.  */
 183       else
 184         {
 185           if (dump_file)
 186             fprintf (dump_file, "    global memory read is not const\n");
 187           /* Just a regular read.  */
 188           if (local->pure_const_state == IPA_CONST)
 189             local->pure_const_state = IPA_PURE;
 190         }
 191     }
 192   else
 193     {
 194       /* Compilation level statics can be read if they are readonly
 195          variables.  */
 196       if (TREE_READONLY (t))
 197         return;
 198
 199       if (dump_file)
 200         fprintf (dump_file, "    static memory read is not const\n");
 201       /* Just a regular read.  */
 202       if (local->pure_const_state == IPA_CONST)
 203         local->pure_const_state = IPA_PURE;
 204     }
 205 }
 206
 207
 208 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 209    variable T is legal in a function that is either pure or const.  */
 210
 211 static inline void
 212 check_op (funct_state local, tree t, bool checking_write)
 213 {
 214   if (TREE_THIS_VOLATILE (t))
 215     {
 216       local->pure_const_state = IPA_NEITHER;
 217       if (dump_file)
 218         fprintf (dump_file, "    Volatile indirect ref is not const/pure\n");
 219       return;
 220     }
 221   else if (checking_write)
 222     {
 223       local->pure_const_state = IPA_NEITHER;
 224       if (dump_file)
 225         fprintf (dump_file, "    Indirect ref write is not const/pure\n");
 226       return;
 227     }
 228   else
 229     {
 230       if (dump_file)
 231         fprintf (dump_file, "    Indirect ref read is not const\n");
 232       if (local->pure_const_state == IPA_CONST)
 233         local->pure_const_state = IPA_PURE;
 234     }
 235 }
 236
 237 /* Check the parameters of a function call to CALL_EXPR to see if
 238    there are any references in the parameters that are not allowed for
 239    pure or const functions.  Also check to see if this is either an
 240    indirect call, a call outside the compilation unit, or has special
 241    attributes that may also effect the purity.  The CALL_EXPR node for
 242    the entire call expression.  */
 243
 244 static void
 245 check_call (funct_state local, gimple call, bool ipa)
 246 {
 247   int flags = gimple_call_flags (call);
 248   tree callee_t = gimple_call_fndecl (call);
 249   struct cgraph_node* callee;
 250   enum availability avail = AVAIL_NOT_AVAILABLE;
 251   bool possibly_throws = stmt_could_throw_p (call);
 252   bool possibly_throws_externally = (possibly_throws
 253                                      && stmt_can_throw_external (call));
 254
 255   if (possibly_throws)
 256     {
 257       unsigned int i;
 258       for (i = 0; i < gimple_num_ops (call); i++)
 259         if (gimple_op (call, i)
 260             && tree_could_throw_p (gimple_op (call, i)))
 261           {
 262             if (possibly_throws && flag_non_call_exceptions)
 263               {
 264                 if (dump_file)
 265                   fprintf (dump_file, "    operand can throw; looping\n");
 266                 local->looping = true;
 267               }
 268             if (possibly_throws_externally)
 269               {
 270                 if (dump_file)
 271                   fprintf (dump_file, "    operand can throw externally\n");
 272                 local->can_throw = true;
 273               }
 274           }
 275     }
 276
 277   /* The const and pure flags are set by a variety of places in the
 278      compiler (including here).  If someone has already set the flags
 279      for the callee, (such as for some of the builtins) we will use
 280      them, otherwise we will compute our own information.
 281
 282      Const and pure functions have less clobber effects than other
 283      functions so we process these first.  Otherwise if it is a call
 284      outside the compilation unit or an indirect call we punt.  This
 285      leaves local calls which will be processed by following the call
 286      graph.  */
 287   if (callee_t)
 288     {
 289       callee = cgraph_node(callee_t);
 290       avail = cgraph_function_body_availability (callee);
 291
 292       /* When bad things happen to bad functions, they cannot be const
 293          or pure.  */
 294       if (setjmp_call_p (callee_t))
 295         {
 296           if (dump_file)
 297             fprintf (dump_file, "    setjmp is not const/pure\n");
 298           local->looping = true;
 299           local->pure_const_state = IPA_NEITHER;
 300         }
 301
 302       if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
 303         switch (DECL_FUNCTION_CODE (callee_t))
 304           {
 305           case BUILT_IN_LONGJMP:
 306           case BUILT_IN_NONLOCAL_GOTO:
 307             if (dump_file)
 308               fprintf (dump_file, "    longjmp and nonlocal goto is not const/pure\n");
 309             local->pure_const_state = IPA_NEITHER;
 310             local->looping = true;
 311             break;
 312           default:
 313             break;
 314           }
 315     }
 316
 317   /* When not in IPA mode, we can still handle self recursion.  */
 318   if (!ipa && callee_t == current_function_decl)
 319     local->looping = true;
 320   /* The callee is either unknown (indirect call) or there is just no
 321      scannable code for it (external call) .  We look to see if there
 322      are any bits available for the callee (such as by declaration or
 323      because it is builtin) and process solely on the basis of those
 324      bits. */
 325   else if (avail <= AVAIL_OVERWRITABLE || !ipa)
 326     {
 327       if (possibly_throws && flag_non_call_exceptions)
 328         {
 329           if (dump_file)
 330             fprintf (dump_file, "    can throw; looping\n");
 331           local->looping = true;
 332         }
 333       if (possibly_throws_externally)
 334         {
 335           if (dump_file)
 336             {
 337               fprintf (dump_file, "    can throw externally in region %i\n",
 338                        lookup_stmt_eh_region (call));
 339               if (callee_t)
 340                 fprintf (dump_file, "     callee:%s\n",
 341                          IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t)));
 342             }
 343           local->can_throw = true;
 344         }
 345       if (flags & ECF_CONST)
 346         {
 347           if (callee_t && DECL_LOOPING_CONST_OR_PURE_P (callee_t))
 348             local->looping = true;
 349          }
 350       else if (flags & ECF_PURE)
 351         {
 352           if (callee_t && DECL_LOOPING_CONST_OR_PURE_P (callee_t))
 353             local->looping = true;
 354           if (dump_file)
 355             fprintf (dump_file, "    pure function call in not const\n");
 356           if (local->pure_const_state == IPA_CONST)
 357             local->pure_const_state = IPA_PURE;
 358         }
 359       else
 360         {
 361           if (dump_file)
 362             fprintf (dump_file, "    uknown function call is not const/pure\n");
 363           local->pure_const_state = IPA_NEITHER;
 364           local->looping = true;
 365         }
 366     }
 367   /* Direct functions calls are handled by IPA propagation.  */
 368 }
 369
 370 /* Wrapper around check_decl for loads.  */
 371
 372 static bool
 373 check_load (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 374 {
 375   if (DECL_P (op))
 376     check_decl ((funct_state)data, op, false);
 377   else
 378     check_op ((funct_state)data, op, false);
 379   return false;
 380 }
 381
 382 /* Wrapper around check_decl for stores.  */
 383
 384 static bool
 385 check_store (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 386 {
 387   if (DECL_P (op))
 388     check_decl ((funct_state)data, op, true);
 389   else
 390     check_op ((funct_state)data, op, true);
 391   return false;
 392 }
 393
 394 /* Look into pointer pointed to by GSIP and figure out what interesting side
 395    effects it has.  */
 396 static void
 397 check_stmt (gimple_stmt_iterator *gsip, funct_state local, bool ipa)
 398 {
 399   gimple stmt = gsi_stmt (*gsip);
 400   unsigned int i = 0;
 401
 402   if (dump_file)
 403     {
 404       fprintf (dump_file, "  scanning: ");
 405       print_gimple_stmt (dump_file, stmt, 0, 0);
 406     }
 407
 408   /* Look for loads and stores.  */
 409   walk_stmt_load_store_ops (stmt, local, check_load, check_store);
 410
 411   if (gimple_code (stmt) != GIMPLE_CALL
 412       && stmt_could_throw_p (stmt))
 413     {
 414       if (flag_non_call_exceptions)
 415         {
 416           if (dump_file)
 417             fprintf (dump_file, "    can throw; looping");
 418           local->looping = true;
 419         }
 420       if (stmt_can_throw_external (stmt))
 421         {
 422           if (dump_file)
 423             fprintf (dump_file, "    can throw externally");
 424           local->can_throw = true;
 425         }
 426     }
 427   switch (gimple_code (stmt))
 428     {
 429     case GIMPLE_CALL:
 430       check_call (local, stmt, ipa);
 431       break;
 432     case GIMPLE_LABEL:
 433       if (DECL_NONLOCAL (gimple_label_label (stmt)))
 434         /* Target of long jump. */
 435         {
 436           if (dump_file)
 437             fprintf (dump_file, "    nonlocal label is not const/pure");
 438           local->pure_const_state = IPA_NEITHER;
 439         }
 440       break;
 441     case GIMPLE_ASM:
 442       for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 443         {
 444           tree op = gimple_asm_clobber_op (stmt, i);
 445           if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1)
 446             {
 447               if (dump_file)
 448                 fprintf (dump_file, "    memory asm clobber is not const/pure");
 449               /* Abandon all hope, ye who enter here. */
 450               local->pure_const_state = IPA_NEITHER;
 451             }
 452         }
 453       if (gimple_asm_volatile_p (stmt))
 454         {
 455           if (dump_file)
 456             fprintf (dump_file, "    volatile is not const/pure");
 457           /* Abandon all hope, ye who enter here. */
 458           local->pure_const_state = IPA_NEITHER;
 459           local->looping = true;
 460         }
 461       return;
 462     default:
 463       break;
 464     }
 465 }
 466
 467
 468 /* This is the main routine for finding the reference patterns for
 469    global variables within a function FN.  */
 470
 471 static funct_state
 472 analyze_function (struct cgraph_node *fn, bool ipa)
 473 {
 474   tree decl = fn->decl;
 475   tree old_decl = current_function_decl;
 476   funct_state l;
 477   basic_block this_block;
 478
 479   if (cgraph_function_body_availability (fn) <= AVAIL_OVERWRITABLE)
 480     {
 481       if (dump_file)
 482         fprintf (dump_file, "Function is not available or overwrittable; not analyzing.\n");
 483       return NULL;
 484     }
 485
 486   l = XCNEW (struct funct_state_d);
 487   l->pure_const_state = IPA_CONST;
 488   l->state_set_in_source = IPA_NEITHER;
 489   l->looping = false;
 490   l->can_throw = false;
 491
 492   if (dump_file)
 493     {
 494       fprintf (dump_file, "\n\n local analysis of %s\n ",
 495                cgraph_node_name (fn));
 496     }
 497
 498   push_cfun (DECL_STRUCT_FUNCTION (decl));
 499   current_function_decl = decl;
 500
 501   FOR_EACH_BB (this_block)
 502     {
 503       gimple_stmt_iterator gsi;
 504       struct walk_stmt_info wi;
 505
 506       memset (&wi, 0, sizeof(wi));
 507       for (gsi = gsi_start_bb (this_block);
 508            !gsi_end_p (gsi);
 509            gsi_next (&gsi))
 510         {
 511           check_stmt (&gsi, l, ipa);
 512           if (l->pure_const_state == IPA_NEITHER && l->looping && l->can_throw)
 513             goto end;
 514         }
 515     }
 516
 517 end:
 518   if (l->pure_const_state != IPA_NEITHER)
 519     {
 520       /* Const functions cannot have back edges (an
 521          indication of possible infinite loop side
 522          effect.  */
 523       if (mark_dfs_back_edges ())
 524         l->looping = true;
 525
 526     }
 527
 528   if (TREE_READONLY (decl))
 529     {
 530       l->pure_const_state = IPA_CONST;
 531       l->state_set_in_source = IPA_CONST;
 532       if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
 533         l->looping = false;
 534     }
 535   if (DECL_PURE_P (decl))
 536     {
 537       if (l->pure_const_state != IPA_CONST)
 538         l->pure_const_state = IPA_PURE;
 539       l->state_set_in_source = IPA_PURE;
 540       if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
 541         l->looping = false;
 542     }
 543   if (TREE_NOTHROW (decl))
 544     l->can_throw = false;
 545
 546   pop_cfun ();
 547   current_function_decl = old_decl;
 548   if (dump_file)
 549     {
 550       if (l->looping)
 551         fprintf (dump_file, "Function is locally looping.\n");
 552       if (l->can_throw)
 553         fprintf (dump_file, "Function is locally throwing.\n");
 554       if (l->pure_const_state == IPA_CONST)
 555         fprintf (dump_file, "Function is locally const.\n");
 556       if (l->pure_const_state == IPA_PURE)
 557         fprintf (dump_file, "Function is locally pure.\n");
 558     }
 559   return l;
 560 }
 561
 562 /* Called when new function is inserted to callgraph late.  */
 563 static void
 564 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 565 {
 566  if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 567    return;
 568   /* There are some shared nodes, in particular the initializers on
 569      static declarations.  We do not need to scan them more than once
 570      since all we would be interested in are the addressof
 571      operations.  */
 572   visited_nodes = pointer_set_create ();
 573   set_function_state (node, analyze_function (node, true));
 574   pointer_set_destroy (visited_nodes);
 575   visited_nodes = NULL;
 576 }
 577
 578 /* Called when new clone is inserted to callgraph late.  */
 579
 580 static void
 581 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 582                      void *data ATTRIBUTE_UNUSED)
 583 {
 584   if (get_function_state (src))
 585     {
 586       funct_state l = XNEW (struct funct_state_d);
 587       gcc_assert (!get_function_state (dst));
 588       memcpy (l, get_function_state (src), sizeof (*l));
 589       set_function_state (dst, l);
 590     }
 591 }
 592
 593 /* Called when new clone is inserted to callgraph late.  */
 594
 595 static void
 596 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 597 {
 598   if (get_function_state (node))
 599     {
 600       free (get_function_state (node));
 601       set_function_state (node, NULL);
 602     }
 603 }
 604
 605 \f
 606 /* Analyze each function in the cgraph to see if it is locally PURE or
 607    CONST.  */
 608
 609 static void
 610 generate_summary (void)
 611 {
 612   struct cgraph_node *node;
 613
 614   node_removal_hook_holder =
 615       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 616   node_duplication_hook_holder =
 617       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 618   function_insertion_hook_holder =
 619       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 620   /* There are some shared nodes, in particular the initializers on
 621      static declarations.  We do not need to scan them more than once
 622      since all we would be interested in are the addressof
 623      operations.  */
 624   visited_nodes = pointer_set_create ();
 625
 626   /* Process all of the functions.
 627
 628      We do NOT process any AVAIL_OVERWRITABLE functions, we cannot
 629      guarantee that what we learn about the one we see will be true
 630      for the one that overrides it.
 631   */
 632   for (node = cgraph_nodes; node; node = node->next)
 633     if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 634       set_function_state (node, analyze_function (node, true));
 635
 636   pointer_set_destroy (visited_nodes);
 637   visited_nodes = NULL;
 638 }
 639
 640 /* Produce the global information by preforming a transitive closure
 641    on the local information that was produced by generate_summary.
 642    Note that there is no function_transform pass since this only
 643    updates the function_decl.  */
 644
 645 static unsigned int
 646 propagate (void)
 647 {
 648   struct cgraph_node *node;
 649   struct cgraph_node *w;
 650   struct cgraph_node **order =
 651     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 652   int order_pos;
 653   int i;
 654   struct ipa_dfs_info * w_info;
 655
 656   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
 657   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
 658   cgraph_remove_node_removal_hook (node_removal_hook_holder);
 659   order_pos = ipa_utils_reduced_inorder (order, true, false);
 660   if (dump_file)
 661     {
 662       dump_cgraph (dump_file);
 663       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 664     }
 665
 666   /* Propagate the local information thru the call graph to produce
 667      the global information.  All the nodes within a cycle will have
 668      the same info so we collapse cycles first.  Then we can do the
 669      propagation in one pass from the leaves to the roots.  */
 670   for (i = 0; i < order_pos; i++ )
 671     {
 672       enum pure_const_state_e pure_const_state = IPA_CONST;
 673       bool looping = false;
 674       bool can_throw = false;
 675       int count = 0;
 676       node = order[i];
 677
 678       /* Find the worst state for any node in the cycle.  */
 679       w = node;
 680       while (w)
 681         {
 682           struct cgraph_edge *e;
 683           funct_state w_l = get_function_state (w);
 684           if (pure_const_state < w_l->pure_const_state)
 685             pure_const_state = w_l->pure_const_state;
 686
 687           if (w_l->can_throw)
 688             can_throw = true;
 689           if (w_l->looping)
 690             looping = true;
 691
 692           if (pure_const_state == IPA_NEITHER
 693               && can_throw)
 694             break;
 695
 696           count++;
 697
 698           if (count > 1)
 699             looping = true;
 700
 701           for (e = w->callees; e; e = e->next_callee)
 702             {
 703               struct cgraph_node *y = e->callee;
 704
 705               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 706                 {
 707                   funct_state y_l = get_function_state (y);
 708                   if (pure_const_state < y_l->pure_const_state)
 709                     pure_const_state = y_l->pure_const_state;
 710                   if (pure_const_state == IPA_NEITHER
 711                       && can_throw)
 712                     break;
 713                   if (y_l->looping)
 714                     looping = true;
 715                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
 716                       /* FIXME: We should check that the throw can get external.
 717                          We also should handle only loops formed by can throw external
 718                          edges.  */)
 719                     can_throw = true;
 720                 }
 721             }
 722           w_info = (struct ipa_dfs_info *) w->aux;
 723           w = w_info->next_cycle;
 724         }
 725
 726       /* Copy back the region's pure_const_state which is shared by
 727          all nodes in the region.  */
 728       w = node;
 729       while (w)
 730         {
 731           funct_state w_l = get_function_state (w);
 732           enum pure_const_state_e this_state = pure_const_state;
 733           bool this_looping = looping;
 734
 735           if (w_l->state_set_in_source != IPA_NEITHER)
 736             {
 737               if (this_state > w_l->state_set_in_source)
 738                 this_state = w_l->state_set_in_source;
 739               this_looping = false;
 740             }
 741
 742           /* All nodes within a cycle share the same info.  */
 743           w_l->pure_const_state = this_state;
 744           w_l->looping = this_looping;
 745
 746           switch (this_state)
 747             {
 748             case IPA_CONST:
 749               if (!TREE_READONLY (w->decl) && dump_file)
 750                 fprintf (dump_file, "Function found to be %sconst: %s\n",
 751                          this_looping ? "looping " : "",
 752                          cgraph_node_name (w));
 753               TREE_READONLY (w->decl) = 1;
 754               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 755               break;
 756
 757             case IPA_PURE:
 758               if (!DECL_PURE_P (w->decl) && dump_file)
 759                 fprintf (dump_file, "Function found to be %spure: %s\n",
 760                          this_looping ? "looping " : "",
 761                          cgraph_node_name (w));
 762               DECL_PURE_P (w->decl) = 1;
 763               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 764               break;
 765
 766             default:
 767               break;
 768             }
 769           if (!can_throw && !TREE_NOTHROW (w->decl))
 770             {
 771               /* FIXME: TREE_NOTHROW is not set because passmanager will execute
 772                  verify_ssa and verify_cfg on every function.  Before fixup_cfg is done,
 773                  those functions are going to have NOTHROW calls in EH regions reulting
 774                  in ICE.  */
 775               if (dump_file)
 776                 fprintf (dump_file, "Function found to be nothrow: %s\n",
 777                          cgraph_node_name (w));
 778             }
 779           w_info = (struct ipa_dfs_info *) w->aux;
 780           w = w_info->next_cycle;
 781         }
 782     }
 783
 784   /* Cleanup. */
 785   for (node = cgraph_nodes; node; node = node->next)
 786     {
 787       /* Get rid of the aux information.  */
 788       if (node->aux)
 789         {
 790           w_info = (struct ipa_dfs_info *) node->aux;
 791           free (node->aux);
 792           node->aux = NULL;
 793         }
 794       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 795         free (get_function_state (node));
 796     }
 797
 798   free (order);
 799   VEC_free (funct_state, heap, funct_state_vec);
 800   finish_state ();
 801   return 0;
 802 }
 803
 804 static bool
 805 gate_pure_const (void)
 806 {
 807   return (flag_ipa_pure_const
 808           /* Don't bother doing anything if the program has errors.  */
 809           && !(errorcount || sorrycount));
 810 }
 811
 812 struct ipa_opt_pass pass_ipa_pure_const =
 813 {
 814  {
 815   IPA_PASS,
 816   "pure-const",                         /* name */
 817   gate_pure_const,                      /* gate */
 818   propagate,                            /* execute */
 819   NULL,                                 /* sub */
 820   NULL,                                 /* next */
 821   0,                                    /* static_pass_number */
 822   TV_IPA_PURE_CONST,                    /* tv_id */
 823   0,                                    /* properties_required */
 824   0,                                    /* properties_provided */
 825   0,                                    /* properties_destroyed */
 826   0,                                    /* todo_flags_start */
 827   0                                     /* todo_flags_finish */
 828  },
 829  generate_summary,                      /* generate_summary */
 830  NULL,                                  /* write_summary */
 831  NULL,                                  /* read_summary */
 832  NULL,                                  /* function_read_summary */
 833  0,                                     /* TODOs */
 834  NULL,                                  /* function_transform */
 835  NULL                                   /* variable_transform */
 836 };
 837
 838 /* Simple local pass for pure const discovery reusing the analysis from
 839    ipa_pure_const.   This pass is effective when executed together with
 840    other optimization passes in early optimization pass queue.  */
 841
 842 static unsigned int
 843 local_pure_const (void)
 844 {
 845   bool changed = false;
 846   funct_state l;
 847
 848   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
 849      we must not promote functions that are called by already processed functions.  */
 850
 851   if (function_called_by_processed_nodes_p ())
 852     {
 853       if (dump_file)
 854         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
 855       return 0;
 856     }
 857
 858   l = analyze_function (cgraph_node (current_function_decl), false);
 859   if (!l)
 860     {
 861       if (dump_file)
 862         fprintf (dump_file, "Function has wrong visibility; ignoring\n");
 863       return 0;
 864     }
 865
 866   switch (l->pure_const_state)
 867     {
 868     case IPA_CONST:
 869       if (!TREE_READONLY (current_function_decl))
 870         {
 871           TREE_READONLY (current_function_decl) = 1;
 872           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
 873           changed = true;
 874           if (dump_file)
 875             fprintf (dump_file, "Function found to be %sconst: %s\n",
 876                      l->looping ? "looping " : "",
 877                      lang_hooks.decl_printable_name (current_function_decl,
 878                                                      2));
 879         }
 880       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
 881                && !l->looping)
 882         {
 883           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
 884           changed = true;
 885           if (dump_file)
 886             fprintf (dump_file, "Function found to be non-looping: %s\n",
 887                      lang_hooks.decl_printable_name (current_function_decl,
 888                                                      2));
 889         }
 890       break;
 891
 892     case IPA_PURE:
 893       if (!TREE_READONLY (current_function_decl))
 894         {
 895           DECL_PURE_P (current_function_decl) = 1;
 896           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
 897           changed = true;
 898           if (dump_file)
 899             fprintf (dump_file, "Function found to be %spure: %s\n",
 900                      l->looping ? "looping " : "",
 901                      lang_hooks.decl_printable_name (current_function_decl,
 902                                                      2));
 903         }
 904       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
 905                && !l->looping)
 906         {
 907           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
 908           changed = true;
 909           if (dump_file)
 910             fprintf (dump_file, "Function found to be non-looping: %s\n",
 911                      lang_hooks.decl_printable_name (current_function_decl,
 912                                                      2));
 913         }
 914       break;
 915
 916     default:
 917       break;
 918     }
 919   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
 920     {
 921       TREE_NOTHROW (current_function_decl) = 1;
 922       changed = true;
 923       if (dump_file)
 924         fprintf (dump_file, "Function found to be nothrow: %s\n",
 925                  lang_hooks.decl_printable_name (current_function_decl,
 926                                                  2));
 927     }
 928   if (l)
 929     free (l);
 930   if (changed)
 931     return execute_fixup_cfg ();
 932   else
 933     return 0;
 934 }
 935
 936 struct gimple_opt_pass pass_local_pure_const =
 937 {
 938  {
 939   GIMPLE_PASS,
 940   "local-pure-const",                   /* name */
 941   gate_pure_const,                      /* gate */
 942   local_pure_const,                     /* execute */
 943   NULL,                                 /* sub */
 944   NULL,                                 /* next */
 945   0,                                    /* static_pass_number */
 946   TV_IPA_PURE_CONST,                    /* tv_id */
 947   0,                                    /* properties_required */
 948   0,                                    /* properties_provided */
 949   0,                                    /* properties_destroyed */
 950   0,                                    /* todo_flags_start */
 951   0                                     /* todo_flags_finish */
 952  }
 953 };