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