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