gcc/ipa-pure-const.c

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