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