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