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 static bool
 641 ignore_edge (struct cgraph_edge *e)
 642 {
 643   return (!e->can_throw_external);
 644 }
 645
 646 /* Produce the global information by preforming a transitive closure
 647    on the local information that was produced by generate_summary.
 648    Note that there is no function_transform pass since this only
 649    updates the function_decl.  */
 650
 651 static unsigned int
 652 propagate (void)
 653 {
 654   struct cgraph_node *node;
 655   struct cgraph_node *w;
 656   struct cgraph_node **order =
 657     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 658   int order_pos;
 659   int i;
 660   struct ipa_dfs_info * w_info;
 661
 662   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
 663   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
 664   cgraph_remove_node_removal_hook (node_removal_hook_holder);
 665   order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
 666   if (dump_file)
 667     {
 668       dump_cgraph (dump_file);
 669       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 670     }
 671
 672   /* Propagate the local information thru the call graph to produce
 673      the global information.  All the nodes within a cycle will have
 674      the same info so we collapse cycles first.  Then we can do the
 675      propagation in one pass from the leaves to the roots.  */
 676   for (i = 0; i < order_pos; i++ )
 677     {
 678       enum pure_const_state_e pure_const_state = IPA_CONST;
 679       bool looping = false;
 680       int count = 0;
 681       node = order[i];
 682
 683       /* Find the worst state for any node in the cycle.  */
 684       w = node;
 685       while (w)
 686         {
 687           struct cgraph_edge *e;
 688           funct_state w_l = get_function_state (w);
 689           if (pure_const_state < w_l->pure_const_state)
 690             pure_const_state = w_l->pure_const_state;
 691
 692           if (w_l->looping)
 693             looping = true;
 694
 695           if (pure_const_state == IPA_NEITHER)
 696             break;
 697
 698           count++;
 699
 700           if (count > 1)
 701             looping = true;
 702
 703           for (e = w->callees; e; e = e->next_callee)
 704             {
 705               struct cgraph_node *y = e->callee;
 706
 707               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 708                 {
 709                   funct_state y_l = get_function_state (y);
 710                   if (pure_const_state < y_l->pure_const_state)
 711                     pure_const_state = y_l->pure_const_state;
 712                   if (pure_const_state == IPA_NEITHER)
 713                     break;
 714                   if (y_l->looping)
 715                     looping = true;
 716                 }
 717             }
 718           w_info = (struct ipa_dfs_info *) w->aux;
 719           w = w_info->next_cycle;
 720         }
 721
 722       /* Copy back the region's pure_const_state which is shared by
 723          all nodes in the region.  */
 724       w = node;
 725       while (w)
 726         {
 727           funct_state w_l = get_function_state (w);
 728           enum pure_const_state_e this_state = pure_const_state;
 729           bool this_looping = looping;
 730
 731           if (w_l->state_set_in_source != IPA_NEITHER)
 732             {
 733               if (this_state > w_l->state_set_in_source)
 734                 this_state = w_l->state_set_in_source;
 735               this_looping = false;
 736             }
 737
 738           /* All nodes within a cycle share the same info.  */
 739           w_l->pure_const_state = this_state;
 740           w_l->looping = this_looping;
 741
 742           switch (this_state)
 743             {
 744             case IPA_CONST:
 745               if (!TREE_READONLY (w->decl) && dump_file)
 746                 fprintf (dump_file, "Function found to be %sconst: %s\n",
 747                          this_looping ? "looping " : "",
 748                          cgraph_node_name (w));
 749               TREE_READONLY (w->decl) = 1;
 750               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 751               break;
 752
 753             case IPA_PURE:
 754               if (!DECL_PURE_P (w->decl) && dump_file)
 755                 fprintf (dump_file, "Function found to be %spure: %s\n",
 756                          this_looping ? "looping " : "",
 757                          cgraph_node_name (w));
 758               DECL_PURE_P (w->decl) = 1;
 759               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 760               break;
 761
 762             default:
 763               break;
 764             }
 765           w_info = (struct ipa_dfs_info *) w->aux;
 766           w = w_info->next_cycle;
 767         }
 768     }
 769
 770   /* Cleanup. */
 771   for (node = cgraph_nodes; node; node = node->next)
 772     {
 773       /* Get rid of the aux information.  */
 774       if (node->aux)
 775         {
 776           w_info = (struct ipa_dfs_info *) node->aux;
 777           free (node->aux);
 778           node->aux = NULL;
 779         }
 780     }
 781   order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
 782   if (dump_file)
 783     {
 784       dump_cgraph (dump_file);
 785       ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
 786     }
 787   /* Propagate the local information thru the call graph to produce
 788      the global information.  All the nodes within a cycle will have
 789      the same info so we collapse cycles first.  Then we can do the
 790      propagation in one pass from the leaves to the roots.  */
 791   for (i = 0; i < order_pos; i++ )
 792     {
 793       bool can_throw = false;
 794       node = order[i];
 795
 796       /* Find the worst state for any node in the cycle.  */
 797       w = node;
 798       while (w)
 799         {
 800           struct cgraph_edge *e;
 801           funct_state w_l = get_function_state (w);
 802
 803           if (w_l->can_throw)
 804             can_throw = true;
 805
 806           if (can_throw)
 807             break;
 808
 809           for (e = w->callees; e; e = e->next_callee)
 810             {
 811               struct cgraph_node *y = e->callee;
 812
 813               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 814                 {
 815                   funct_state y_l = get_function_state (y);
 816
 817                   if (can_throw)
 818                     break;
 819                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
 820                       && e->can_throw_external)
 821                     can_throw = true;
 822                 }
 823             }
 824           w_info = (struct ipa_dfs_info *) w->aux;
 825           w = w_info->next_cycle;
 826         }
 827
 828       /* Copy back the region's pure_const_state which is shared by
 829          all nodes in the region.  */
 830       w = node;
 831       while (w)
 832         {
 833           funct_state w_l = get_function_state (w);
 834           if (!can_throw && !TREE_NOTHROW (w->decl))
 835             {
 836               struct cgraph_edge *e;
 837               TREE_NOTHROW (w->decl) = true;
 838               for (e = w->callers; e; e = e->next_caller)
 839                 e->can_throw_external = false;
 840               if (dump_file)
 841                 fprintf (dump_file, "Function found to be nothrow: %s\n",
 842                          cgraph_node_name (w));
 843             }
 844           else if (can_throw && !TREE_NOTHROW (w->decl))
 845             w_l->can_throw = true;
 846           w_info = (struct ipa_dfs_info *) w->aux;
 847           w = w_info->next_cycle;
 848         }
 849     }
 850
 851   /* Cleanup. */
 852   for (node = cgraph_nodes; node; node = node->next)
 853     {
 854       /* Get rid of the aux information.  */
 855       if (node->aux)
 856         {
 857           w_info = (struct ipa_dfs_info *) node->aux;
 858           free (node->aux);
 859           node->aux = NULL;
 860         }
 861       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 862         free (get_function_state (node));
 863     }
 864
 865   free (order);
 866   VEC_free (funct_state, heap, funct_state_vec);
 867   finish_state ();
 868   return 0;
 869 }
 870
 871 static bool
 872 gate_pure_const (void)
 873 {
 874   return (flag_ipa_pure_const
 875           /* Don't bother doing anything if the program has errors.  */
 876           && !(errorcount || sorrycount));
 877 }
 878
 879 struct ipa_opt_pass pass_ipa_pure_const =
 880 {
 881  {
 882   IPA_PASS,
 883   "pure-const",                         /* name */
 884   gate_pure_const,                      /* gate */
 885   propagate,                            /* execute */
 886   NULL,                                 /* sub */
 887   NULL,                                 /* next */
 888   0,                                    /* static_pass_number */
 889   TV_IPA_PURE_CONST,                    /* tv_id */
 890   0,                                    /* properties_required */
 891   0,                                    /* properties_provided */
 892   0,                                    /* properties_destroyed */
 893   0,                                    /* todo_flags_start */
 894   0                                     /* todo_flags_finish */
 895  },
 896  generate_summary,                      /* generate_summary */
 897  NULL,                                  /* write_summary */
 898  NULL,                                  /* read_summary */
 899  NULL,                                  /* function_read_summary */
 900  0,                                     /* TODOs */
 901  NULL,                                  /* function_transform */
 902  NULL                                   /* variable_transform */
 903 };
 904
 905 /* Simple local pass for pure const discovery reusing the analysis from
 906    ipa_pure_const.   This pass is effective when executed together with
 907    other optimization passes in early optimization pass queue.  */
 908
 909 static unsigned int
 910 local_pure_const (void)
 911 {
 912   bool changed = false;
 913   funct_state l;
 914
 915   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
 916      we must not promote functions that are called by already processed functions.  */
 917
 918   if (function_called_by_processed_nodes_p ())
 919     {
 920       if (dump_file)
 921         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
 922       return 0;
 923     }
 924
 925   l = analyze_function (cgraph_node (current_function_decl), false);
 926   if (!l)
 927     {
 928       if (dump_file)
 929         fprintf (dump_file, "Function has wrong visibility; ignoring\n");
 930       return 0;
 931     }
 932
 933   switch (l->pure_const_state)
 934     {
 935     case IPA_CONST:
 936       if (!TREE_READONLY (current_function_decl))
 937         {
 938           TREE_READONLY (current_function_decl) = 1;
 939           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
 940           changed = true;
 941           if (dump_file)
 942             fprintf (dump_file, "Function found to be %sconst: %s\n",
 943                      l->looping ? "looping " : "",
 944                      lang_hooks.decl_printable_name (current_function_decl,
 945                                                      2));
 946         }
 947       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
 948                && !l->looping)
 949         {
 950           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
 951           changed = true;
 952           if (dump_file)
 953             fprintf (dump_file, "Function found to be non-looping: %s\n",
 954                      lang_hooks.decl_printable_name (current_function_decl,
 955                                                      2));
 956         }
 957       break;
 958
 959     case IPA_PURE:
 960       if (!TREE_READONLY (current_function_decl))
 961         {
 962           DECL_PURE_P (current_function_decl) = 1;
 963           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
 964           changed = true;
 965           if (dump_file)
 966             fprintf (dump_file, "Function found to be %spure: %s\n",
 967                      l->looping ? "looping " : "",
 968                      lang_hooks.decl_printable_name (current_function_decl,
 969                                                      2));
 970         }
 971       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
 972                && !l->looping)
 973         {
 974           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
 975           changed = true;
 976           if (dump_file)
 977             fprintf (dump_file, "Function found to be non-looping: %s\n",
 978                      lang_hooks.decl_printable_name (current_function_decl,
 979                                                      2));
 980         }
 981       break;
 982
 983     default:
 984       break;
 985     }
 986   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
 987     {
 988       struct cgraph_edge *e;
 989
 990       TREE_NOTHROW (current_function_decl) = true;
 991       for (e = cgraph_node (current_function_decl)->callers;
 992            e; e = e->next_caller)
 993         e->can_throw_external = false;
 994       changed = true;
 995       if (dump_file)
 996         fprintf (dump_file, "Function found to be nothrow: %s\n",
 997                  lang_hooks.decl_printable_name (current_function_decl,
 998                                                  2));
 999     }
1000   if (l)
1001     free (l);
1002   if (changed)
1003     return execute_fixup_cfg ();
1004   else
1005     return 0;
1006 }
1007
1008 struct gimple_opt_pass pass_local_pure_const =
1009 {
1010  {
1011   GIMPLE_PASS,
1012   "local-pure-const",                   /* name */
1013   gate_pure_const,                      /* gate */
1014   local_pure_const,                     /* execute */
1015   NULL,                                 /* sub */
1016   NULL,                                 /* next */
1017   0,                                    /* static_pass_number */
1018   TV_IPA_PURE_CONST,                    /* tv_id */
1019   0,                                    /* properties_required */
1020   0,                                    /* properties_provided */
1021   0,                                    /* properties_destroyed */
1022   0,                                    /* todo_flags_start */
1023   0                                     /* todo_flags_finish */
1024  }
1025 };