gcc/ipa-pure-const.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This file marks functions as being either const (TREE_READONLY) or
  23    pure (DECL_PURE_P).  It can also set a variant of these that
  24    are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
  25
  26    This must be run after inlining decisions have been made since
  27    otherwise, the local sets will not contain information that is
  28    consistent with post inlined state.  The global sets are not prone
  29    to this problem since they are by definition transitive.  */
  30
  31 /* The code in this module is called by the ipa pass manager. It
  32    should be one of the later passes since it's information is used by
  33    the rest of the compilation. */
  34
  35 #include "config.h"
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tm.h"
  39 #include "tree.h"
  40 #include "tree-flow.h"
  41 #include "tree-inline.h"
  42 #include "tree-pass.h"
  43 #include "langhooks.h"
  44 #include "pointer-set.h"
  45 #include "ggc.h"
  46 #include "ipa-utils.h"
  47 #include "gimple.h"
  48 #include "cgraph.h"
  49 #include "output.h"
  50 #include "flags.h"
  51 #include "timevar.h"
  52 #include "toplev.h"
  53 #include "diagnostic.h"
  54 #include "gimple-pretty-print.h"
  55 #include "langhooks.h"
  56 #include "target.h"
  57 #include "lto-streamer.h"
  58 #include "cfgloop.h"
  59 #include "tree-scalar-evolution.h"
  60 #include "intl.h"
  61 #include "opts.h"
  62
  63 static struct pointer_set_t *visited_nodes;
  64
  65 /* Lattice values for const and pure functions.  Everything starts out
  66    being const, then may drop to pure and then neither depending on
  67    what is found.  */
  68 enum pure_const_state_e
  69 {
  70   IPA_CONST,
  71   IPA_PURE,
  72   IPA_NEITHER
  73 };
  74
  75 const char *pure_const_names[3] = {"const", "pure", "neither"};
  76
  77 /* Holder for the const_state.  There is one of these per function
  78    decl.  */
  79 struct funct_state_d
  80 {
  81   /* See above.  */
  82   enum pure_const_state_e pure_const_state;
  83   /* What user set here; we can be always sure about this.  */
  84   enum pure_const_state_e state_previously_known;
  85   bool looping_previously_known;
  86
  87   /* True if the function could possibly infinite loop.  There are a
  88      lot of ways that this could be determined.  We are pretty
  89      conservative here.  While it is possible to cse pure and const
  90      calls, it is not legal to have dce get rid of the call if there
  91      is a possibility that the call could infinite loop since this is
  92      a behavioral change.  */
  93   bool looping;
  94
  95   bool can_throw;
  96 };
  97
  98 typedef struct funct_state_d * funct_state;
  99
 100 /* The storage of the funct_state is abstracted because there is the
 101    possibility that it may be desirable to move this to the cgraph
 102    local info.  */
 103
 104 /* Array, indexed by cgraph node uid, of function states.  */
 105
 106 DEF_VEC_P (funct_state);
 107 DEF_VEC_ALLOC_P (funct_state, heap);
 108 static VEC (funct_state, heap) *funct_state_vec;
 109
 110 /* Holders of ipa cgraph hooks: */
 111 static struct cgraph_node_hook_list *function_insertion_hook_holder;
 112 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 113 static struct cgraph_node_hook_list *node_removal_hook_holder;
 114
 115 /* Try to guess if function body will always be visible to compiler
 116    when compiling the call and whether compiler will be able
 117    to propagate the information by itself.  */
 118
 119 static bool
 120 function_always_visible_to_compiler_p (tree decl)
 121 {
 122   return (!TREE_PUBLIC (decl) || DECL_DECLARED_INLINE_P (decl));
 123 }
 124
 125 /* Emit suggestion about attribute ATTRIB_NAME for DECL.  KNOWN_FINITE
 126    is true if the function is known to be finite.  The diagnostic is
 127    controlled by OPTION.  WARNED_ABOUT is a pointer_set unique for
 128    OPTION, this function may initialize it and it is always returned
 129    by the function.  */
 130
 131 static struct pointer_set_t *
 132 suggest_attribute (int option, tree decl, bool known_finite,
 133                    struct pointer_set_t *warned_about,
 134                    const char * attrib_name)
 135 {
 136   if (!option_enabled (option))
 137     return warned_about;
 138   if (TREE_THIS_VOLATILE (decl)
 139       || (known_finite && function_always_visible_to_compiler_p (decl)))
 140     return warned_about;
 141
 142   if (!warned_about)
 143     warned_about = pointer_set_create ();
 144   if (pointer_set_contains (warned_about, decl))
 145     return warned_about;
 146   pointer_set_insert (warned_about, decl);
 147   warning_at (DECL_SOURCE_LOCATION (decl),
 148               option,
 149               known_finite
 150               ? _("function might be candidate for attribute %<%s%>")
 151               : _("function might be candidate for attribute %<%s%>"
 152                   " if it is known to return normally"), attrib_name);
 153   return warned_about;
 154 }
 155
 156 /* Emit suggestion about __attribute_((pure)) for DECL.  KNOWN_FINITE
 157    is true if the function is known to be finite.  */
 158
 159 static void
 160 warn_function_pure (tree decl, bool known_finite)
 161 {
 162   static struct pointer_set_t *warned_about;
 163
 164   warned_about
 165     = suggest_attribute (OPT_Wsuggest_attribute_pure, decl,
 166                          known_finite, warned_about, "pure");
 167 }
 168
 169 /* Emit suggestion about __attribute_((const)) for DECL.  KNOWN_FINITE
 170    is true if the function is known to be finite.  */
 171
 172 static void
 173 warn_function_const (tree decl, bool known_finite)
 174 {
 175   static struct pointer_set_t *warned_about;
 176   warned_about
 177     = suggest_attribute (OPT_Wsuggest_attribute_const, decl,
 178                          known_finite, warned_about, "const");
 179 }
 180
 181 void
 182 warn_function_noreturn (tree decl)
 183 {
 184   static struct pointer_set_t *warned_about;
 185   if (!lang_hooks.missing_noreturn_ok_p (decl))
 186     warned_about
 187       = suggest_attribute (OPT_Wsuggest_attribute_noreturn, decl,
 188                            true, warned_about, "noreturn");
 189 }
 190 /* Init the function state.  */
 191
 192 static void
 193 finish_state (void)
 194 {
 195   free (funct_state_vec);
 196 }
 197
 198
 199 /* Return true if we have a function state for NODE.  */
 200
 201 static inline bool
 202 has_function_state (struct cgraph_node *node)
 203 {
 204   if (!funct_state_vec
 205       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 206     return false;
 207   return VEC_index (funct_state, funct_state_vec, node->uid) != NULL;
 208 }
 209
 210 /* Return the function state from NODE.  */
 211
 212 static inline funct_state
 213 get_function_state (struct cgraph_node *node)
 214 {
 215   static struct funct_state_d varying
 216     = { IPA_NEITHER, IPA_NEITHER, true, true, true };
 217   if (!funct_state_vec
 218       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 219     /* We might want to put correct previously_known state into varying.  */
 220     return &varying;
 221   return VEC_index (funct_state, funct_state_vec, node->uid);
 222 }
 223
 224 /* Set the function state S for NODE.  */
 225
 226 static inline void
 227 set_function_state (struct cgraph_node *node, funct_state s)
 228 {
 229   if (!funct_state_vec
 230       || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
 231      VEC_safe_grow_cleared (funct_state, heap, funct_state_vec, node->uid + 1);
 232   VEC_replace (funct_state, funct_state_vec, node->uid, s);
 233 }
 234
 235 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 236    variable T is legal in a function that is either pure or const.  */
 237
 238 static inline void
 239 check_decl (funct_state local,
 240             tree t, bool checking_write, bool ipa)
 241 {
 242   /* Do not want to do anything with volatile except mark any
 243      function that uses one to be not const or pure.  */
 244   if (TREE_THIS_VOLATILE (t))
 245     {
 246       local->pure_const_state = IPA_NEITHER;
 247       if (dump_file)
 248         fprintf (dump_file, "    Volatile operand is not const/pure");
 249       return;
 250     }
 251
 252   /* Do not care about a local automatic that is not static.  */
 253   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 254     return;
 255
 256   /* If the variable has the "used" attribute, treat it as if it had a
 257      been touched by the devil.  */
 258   if (DECL_PRESERVE_P (t))
 259     {
 260       local->pure_const_state = IPA_NEITHER;
 261       if (dump_file)
 262         fprintf (dump_file, "    Used static/global variable is not const/pure\n");
 263       return;
 264     }
 265
 266   /* In IPA mode we are not interested in checking actual loads and stores;
 267      they will be processed at propagation time using ipa_ref.  */
 268   if (ipa)
 269     return;
 270
 271   /* Since we have dealt with the locals and params cases above, if we
 272      are CHECKING_WRITE, this cannot be a pure or constant
 273      function.  */
 274   if (checking_write)
 275     {
 276       local->pure_const_state = IPA_NEITHER;
 277       if (dump_file)
 278         fprintf (dump_file, "    static/global memory write is not const/pure\n");
 279       return;
 280     }
 281
 282   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 283     {
 284       /* Readonly reads are safe.  */
 285       if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
 286         return; /* Read of a constant, do not change the function state.  */
 287       else
 288         {
 289           if (dump_file)
 290             fprintf (dump_file, "    global memory read is not const\n");
 291           /* Just a regular read.  */
 292           if (local->pure_const_state == IPA_CONST)
 293             local->pure_const_state = IPA_PURE;
 294         }
 295     }
 296   else
 297     {
 298       /* Compilation level statics can be read if they are readonly
 299          variables.  */
 300       if (TREE_READONLY (t))
 301         return;
 302
 303       if (dump_file)
 304         fprintf (dump_file, "    static memory read is not const\n");
 305       /* Just a regular read.  */
 306       if (local->pure_const_state == IPA_CONST)
 307         local->pure_const_state = IPA_PURE;
 308     }
 309 }
 310
 311
 312 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 313    variable T is legal in a function that is either pure or const.  */
 314
 315 static inline void
 316 check_op (funct_state local, tree t, bool checking_write)
 317 {
 318   t = get_base_address (t);
 319   if (t && TREE_THIS_VOLATILE (t))
 320     {
 321       local->pure_const_state = IPA_NEITHER;
 322       if (dump_file)
 323         fprintf (dump_file, "    Volatile indirect ref is not const/pure\n");
 324       return;
 325     }
 326   else if (t
 327            && INDIRECT_REF_P (t)
 328            && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 329            && !ptr_deref_may_alias_global_p (TREE_OPERAND (t, 0)))
 330     {
 331       if (dump_file)
 332         fprintf (dump_file, "    Indirect ref to local memory is OK\n");
 333       return;
 334     }
 335   else if (checking_write)
 336     {
 337       local->pure_const_state = IPA_NEITHER;
 338       if (dump_file)
 339         fprintf (dump_file, "    Indirect ref write is not const/pure\n");
 340       return;
 341     }
 342   else
 343     {
 344       if (dump_file)
 345         fprintf (dump_file, "    Indirect ref read is not const\n");
 346       if (local->pure_const_state == IPA_CONST)
 347         local->pure_const_state = IPA_PURE;
 348     }
 349 }
 350
 351 /* compute state based on ECF FLAGS and store to STATE and LOOPING.  */
 352
 353 static void
 354 state_from_flags (enum pure_const_state_e *state, bool *looping,
 355                   int flags, bool cannot_lead_to_return)
 356 {
 357   *looping = false;
 358   if (flags & ECF_LOOPING_CONST_OR_PURE)
 359     {
 360       *looping = true;
 361       if (dump_file && (dump_flags & TDF_DETAILS))
 362         fprintf (dump_file, " looping");
 363     }
 364   if (flags & ECF_CONST)
 365     {
 366       *state = IPA_CONST;
 367       if (dump_file && (dump_flags & TDF_DETAILS))
 368         fprintf (dump_file, " const\n");
 369     }
 370   else if (flags & ECF_PURE)
 371     {
 372       *state = IPA_PURE;
 373       if (dump_file && (dump_flags & TDF_DETAILS))
 374         fprintf (dump_file, " pure\n");
 375     }
 376   else if (cannot_lead_to_return)
 377     {
 378       *state = IPA_PURE;
 379       *looping = true;
 380       if (dump_file && (dump_flags & TDF_DETAILS))
 381         fprintf (dump_file, " ignoring side effects->pure looping\n");
 382     }
 383   else
 384     {
 385       if (dump_file && (dump_flags & TDF_DETAILS))
 386         fprintf (dump_file, " neihter\n");
 387       *state = IPA_NEITHER;
 388       *looping = true;
 389     }
 390 }
 391
 392 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
 393    into STATE and LOOPING better of the two variants.
 394    Be sure to merge looping correctly.  IPA_NEITHER functions
 395    have looping 0 even if they don't have to return.  */
 396
 397 static inline void
 398 better_state (enum pure_const_state_e *state, bool *looping,
 399               enum pure_const_state_e state2, bool looping2)
 400 {
 401   if (state2 < *state)
 402     {
 403       if (*state == IPA_NEITHER)
 404         *looping = looping2;
 405       else
 406         *looping = MIN (*looping, looping2);
 407     }
 408   else if (state2 != IPA_NEITHER)
 409     *looping = MIN (*looping, looping2);
 410 }
 411
 412 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
 413    into STATE and LOOPING worse of the two variants.  */
 414
 415 static inline void
 416 worse_state (enum pure_const_state_e *state, bool *looping,
 417              enum pure_const_state_e state2, bool looping2)
 418 {
 419   *state = MAX (*state, state2);
 420   *looping = MAX (*looping, looping2);
 421 }
 422
 423 /* Recognize special cases of builtins that are by themself not pure or const
 424    but function using them is.  */
 425 static bool
 426 special_builtlin_state (enum pure_const_state_e *state, bool *looping,
 427                         tree callee)
 428 {
 429   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
 430     switch (DECL_FUNCTION_CODE (callee))
 431       {
 432         case BUILT_IN_RETURN:
 433         case BUILT_IN_UNREACHABLE:
 434         case BUILT_IN_ALLOCA:
 435         case BUILT_IN_STACK_SAVE:
 436         case BUILT_IN_STACK_RESTORE:
 437         case BUILT_IN_EH_POINTER:
 438         case BUILT_IN_EH_FILTER:
 439         case BUILT_IN_UNWIND_RESUME:
 440         case BUILT_IN_CXA_END_CLEANUP:
 441         case BUILT_IN_EH_COPY_VALUES:
 442         case BUILT_IN_FRAME_ADDRESS:
 443         case BUILT_IN_APPLY:
 444         case BUILT_IN_APPLY_ARGS:
 445         case BUILT_IN_ARGS_INFO:
 446           *looping = false;
 447           *state = IPA_CONST;
 448           return true;
 449         case BUILT_IN_PREFETCH:
 450           *looping = true;
 451           *state = IPA_CONST;
 452           return true;
 453       }
 454   return false;
 455 }
 456
 457 /* Check the parameters of a function call to CALL_EXPR to see if
 458    there are any references in the parameters that are not allowed for
 459    pure or const functions.  Also check to see if this is either an
 460    indirect call, a call outside the compilation unit, or has special
 461    attributes that may also effect the purity.  The CALL_EXPR node for
 462    the entire call expression.  */
 463
 464 static void
 465 check_call (funct_state local, gimple call, bool ipa)
 466 {
 467   int flags = gimple_call_flags (call);
 468   tree callee_t = gimple_call_fndecl (call);
 469   bool possibly_throws = stmt_could_throw_p (call);
 470   bool possibly_throws_externally = (possibly_throws
 471                                      && stmt_can_throw_external (call));
 472
 473   if (possibly_throws)
 474     {
 475       unsigned int i;
 476       for (i = 0; i < gimple_num_ops (call); i++)
 477         if (gimple_op (call, i)
 478             && tree_could_throw_p (gimple_op (call, i)))
 479           {
 480             if (possibly_throws && cfun->can_throw_non_call_exceptions)
 481               {
 482                 if (dump_file)
 483                   fprintf (dump_file, "    operand can throw; looping\n");
 484                 local->looping = true;
 485               }
 486             if (possibly_throws_externally)
 487               {
 488                 if (dump_file)
 489                   fprintf (dump_file, "    operand can throw externally\n");
 490                 local->can_throw = true;
 491               }
 492           }
 493     }
 494
 495   /* The const and pure flags are set by a variety of places in the
 496      compiler (including here).  If someone has already set the flags
 497      for the callee, (such as for some of the builtins) we will use
 498      them, otherwise we will compute our own information.
 499
 500      Const and pure functions have less clobber effects than other
 501      functions so we process these first.  Otherwise if it is a call
 502      outside the compilation unit or an indirect call we punt.  This
 503      leaves local calls which will be processed by following the call
 504      graph.  */
 505   if (callee_t)
 506     {
 507       enum pure_const_state_e call_state;
 508       bool call_looping;
 509
 510       if (special_builtlin_state (&call_state, &call_looping, callee_t))
 511         {
 512           worse_state (&local->pure_const_state, &local->looping,
 513                        call_state, call_looping);
 514           return;
 515         }
 516       /* When bad things happen to bad functions, they cannot be const
 517          or pure.  */
 518       if (setjmp_call_p (callee_t))
 519         {
 520           if (dump_file)
 521             fprintf (dump_file, "    setjmp is not const/pure\n");
 522           local->looping = true;
 523           local->pure_const_state = IPA_NEITHER;
 524         }
 525
 526       if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
 527         switch (DECL_FUNCTION_CODE (callee_t))
 528           {
 529           case BUILT_IN_LONGJMP:
 530           case BUILT_IN_NONLOCAL_GOTO:
 531             if (dump_file)
 532               fprintf (dump_file, "    longjmp and nonlocal goto is not const/pure\n");
 533             local->pure_const_state = IPA_NEITHER;
 534             local->looping = true;
 535             break;
 536           default:
 537             break;
 538           }
 539     }
 540
 541   /* When not in IPA mode, we can still handle self recursion.  */
 542   if (!ipa && callee_t == current_function_decl)
 543     {
 544       if (dump_file)
 545         fprintf (dump_file, "    Recursive call can loop.\n");
 546       local->looping = true;
 547     }
 548   /* Either calle is unknown or we are doing local analysis.
 549      Look to see if there are any bits available for the callee (such as by
 550      declaration or because it is builtin) and process solely on the basis of
 551      those bits. */
 552   else if (!ipa)
 553     {
 554       enum pure_const_state_e call_state;
 555       bool call_looping;
 556       if (possibly_throws && cfun->can_throw_non_call_exceptions)
 557         {
 558           if (dump_file)
 559             fprintf (dump_file, "    can throw; looping\n");
 560           local->looping = true;
 561         }
 562       if (possibly_throws_externally)
 563         {
 564           if (dump_file)
 565             {
 566               fprintf (dump_file, "    can throw externally to lp %i\n",
 567                        lookup_stmt_eh_lp (call));
 568               if (callee_t)
 569                 fprintf (dump_file, "     callee:%s\n",
 570                          IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t)));
 571             }
 572           local->can_throw = true;
 573         }
 574       if (dump_file && (dump_flags & TDF_DETAILS))
 575         fprintf (dump_file, "    checking flags for call:");
 576       state_from_flags (&call_state, &call_looping, flags,
 577                         ((flags & (ECF_NORETURN | ECF_NOTHROW))
 578                          == (ECF_NORETURN | ECF_NOTHROW))
 579                         || (!flag_exceptions && (flags & ECF_NORETURN)));
 580       worse_state (&local->pure_const_state, &local->looping,
 581                    call_state, call_looping);
 582     }
 583   /* Direct functions calls are handled by IPA propagation.  */
 584 }
 585
 586 /* Wrapper around check_decl for loads in local more.  */
 587
 588 static bool
 589 check_load (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 590 {
 591   if (DECL_P (op))
 592     check_decl ((funct_state)data, op, false, false);
 593   else
 594     check_op ((funct_state)data, op, false);
 595   return false;
 596 }
 597
 598 /* Wrapper around check_decl for stores in local more.  */
 599
 600 static bool
 601 check_store (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 602 {
 603   if (DECL_P (op))
 604     check_decl ((funct_state)data, op, true, false);
 605   else
 606     check_op ((funct_state)data, op, true);
 607   return false;
 608 }
 609
 610 /* Wrapper around check_decl for loads in ipa mode.  */
 611
 612 static bool
 613 check_ipa_load (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 614 {
 615   if (DECL_P (op))
 616     check_decl ((funct_state)data, op, false, true);
 617   else
 618     check_op ((funct_state)data, op, false);
 619   return false;
 620 }
 621
 622 /* Wrapper around check_decl for stores in ipa mode.  */
 623
 624 static bool
 625 check_ipa_store (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
 626 {
 627   if (DECL_P (op))
 628     check_decl ((funct_state)data, op, true, true);
 629   else
 630     check_op ((funct_state)data, op, true);
 631   return false;
 632 }
 633
 634 /* Look into pointer pointed to by GSIP and figure out what interesting side
 635    effects it has.  */
 636 static void
 637 check_stmt (gimple_stmt_iterator *gsip, funct_state local, bool ipa)
 638 {
 639   gimple stmt = gsi_stmt (*gsip);
 640   unsigned int i = 0;
 641
 642   if (is_gimple_debug (stmt))
 643     return;
 644
 645   if (dump_file)
 646     {
 647       fprintf (dump_file, "  scanning: ");
 648       print_gimple_stmt (dump_file, stmt, 0, 0);
 649     }
 650
 651   /* Look for loads and stores.  */
 652   walk_stmt_load_store_ops (stmt, local,
 653                             ipa ? check_ipa_load : check_load,
 654                             ipa ? check_ipa_store :  check_store);
 655
 656   if (gimple_code (stmt) != GIMPLE_CALL
 657       && stmt_could_throw_p (stmt))
 658     {
 659       if (cfun->can_throw_non_call_exceptions)
 660         {
 661           if (dump_file)
 662             fprintf (dump_file, "    can throw; looping");
 663           local->looping = true;
 664         }
 665       if (stmt_can_throw_external (stmt))
 666         {
 667           if (dump_file)
 668             fprintf (dump_file, "    can throw externally");
 669           local->can_throw = true;
 670         }
 671     }
 672   switch (gimple_code (stmt))
 673     {
 674     case GIMPLE_CALL:
 675       check_call (local, stmt, ipa);
 676       break;
 677     case GIMPLE_LABEL:
 678       if (DECL_NONLOCAL (gimple_label_label (stmt)))
 679         /* Target of long jump. */
 680         {
 681           if (dump_file)
 682             fprintf (dump_file, "    nonlocal label is not const/pure");
 683           local->pure_const_state = IPA_NEITHER;
 684         }
 685       break;
 686     case GIMPLE_ASM:
 687       for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 688         {
 689           tree op = gimple_asm_clobber_op (stmt, i);
 690           if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op)), "memory") == 0)
 691             {
 692               if (dump_file)
 693                 fprintf (dump_file, "    memory asm clobber is not const/pure");
 694               /* Abandon all hope, ye who enter here. */
 695               local->pure_const_state = IPA_NEITHER;
 696             }
 697         }
 698       if (gimple_asm_volatile_p (stmt))
 699         {
 700           if (dump_file)
 701             fprintf (dump_file, "    volatile is not const/pure");
 702           /* Abandon all hope, ye who enter here. */
 703           local->pure_const_state = IPA_NEITHER;
 704           local->looping = true;
 705         }
 706       return;
 707     default:
 708       break;
 709     }
 710 }
 711
 712
 713 /* This is the main routine for finding the reference patterns for
 714    global variables within a function FN.  */
 715
 716 static funct_state
 717 analyze_function (struct cgraph_node *fn, bool ipa)
 718 {
 719   tree decl = fn->decl;
 720   tree old_decl = current_function_decl;
 721   funct_state l;
 722   basic_block this_block;
 723
 724   l = XCNEW (struct funct_state_d);
 725   l->pure_const_state = IPA_CONST;
 726   l->state_previously_known = IPA_NEITHER;
 727   l->looping_previously_known = true;
 728   l->looping = false;
 729   l->can_throw = false;
 730
 731   if (dump_file)
 732     {
 733       fprintf (dump_file, "\n\n local analysis of %s\n ",
 734                cgraph_node_name (fn));
 735     }
 736
 737   push_cfun (DECL_STRUCT_FUNCTION (decl));
 738   current_function_decl = decl;
 739
 740   FOR_EACH_BB (this_block)
 741     {
 742       gimple_stmt_iterator gsi;
 743       struct walk_stmt_info wi;
 744
 745       memset (&wi, 0, sizeof(wi));
 746       for (gsi = gsi_start_bb (this_block);
 747            !gsi_end_p (gsi);
 748            gsi_next (&gsi))
 749         {
 750           check_stmt (&gsi, l, ipa);
 751           if (l->pure_const_state == IPA_NEITHER && l->looping && l->can_throw)
 752             goto end;
 753         }
 754     }
 755
 756 end:
 757   if (l->pure_const_state != IPA_NEITHER)
 758     {
 759       /* Const functions cannot have back edges (an
 760          indication of possible infinite loop side
 761          effect.  */
 762       if (mark_dfs_back_edges ())
 763         {
 764           /* Preheaders are needed for SCEV to work.
 765              Simple lateches and recorded exits improve chances that loop will
 766              proved to be finite in testcases such as in loop-15.c and loop-24.c  */
 767           loop_optimizer_init (LOOPS_NORMAL
 768                                | LOOPS_HAVE_RECORDED_EXITS);
 769           if (dump_file && (dump_flags & TDF_DETAILS))
 770             flow_loops_dump (dump_file, NULL, 0);
 771           if (mark_irreducible_loops ())
 772             {
 773               if (dump_file)
 774                 fprintf (dump_file, "    has irreducible loops\n");
 775               l->looping = true;
 776             }
 777           else
 778             {
 779               loop_iterator li;
 780               struct loop *loop;
 781               scev_initialize ();
 782               FOR_EACH_LOOP (li, loop, 0)
 783                 if (!finite_loop_p (loop))
 784                   {
 785                     if (dump_file)
 786                       fprintf (dump_file, "    can not prove finiteness of loop %i\n", loop->num);
 787                     l->looping =true;
 788                     break;
 789                   }
 790               scev_finalize ();
 791             }
 792           loop_optimizer_finalize ();
 793         }
 794     }
 795
 796   if (dump_file && (dump_flags & TDF_DETAILS))
 797     fprintf (dump_file, "    checking previously known:");
 798   state_from_flags (&l->state_previously_known, &l->looping_previously_known,
 799                     flags_from_decl_or_type (fn->decl),
 800                     cgraph_node_cannot_return (fn));
 801
 802   better_state (&l->pure_const_state, &l->looping,
 803                 l->state_previously_known,
 804                 l->looping_previously_known);
 805   if (TREE_NOTHROW (decl))
 806     l->can_throw = false;
 807
 808   pop_cfun ();
 809   current_function_decl = old_decl;
 810   if (dump_file)
 811     {
 812       if (l->looping)
 813         fprintf (dump_file, "Function is locally looping.\n");
 814       if (l->can_throw)
 815         fprintf (dump_file, "Function is locally throwing.\n");
 816       if (l->pure_const_state == IPA_CONST)
 817         fprintf (dump_file, "Function is locally const.\n");
 818       if (l->pure_const_state == IPA_PURE)
 819         fprintf (dump_file, "Function is locally pure.\n");
 820     }
 821   return l;
 822 }
 823
 824 /* Called when new function is inserted to callgraph late.  */
 825 static void
 826 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 827 {
 828  if (cgraph_function_body_availability (node) < AVAIL_OVERWRITABLE)
 829    return;
 830   /* There are some shared nodes, in particular the initializers on
 831      static declarations.  We do not need to scan them more than once
 832      since all we would be interested in are the addressof
 833      operations.  */
 834   visited_nodes = pointer_set_create ();
 835   if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 836     set_function_state (node, analyze_function (node, true));
 837   pointer_set_destroy (visited_nodes);
 838   visited_nodes = NULL;
 839 }
 840
 841 /* Called when new clone is inserted to callgraph late.  */
 842
 843 static void
 844 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 845                      void *data ATTRIBUTE_UNUSED)
 846 {
 847   if (has_function_state (src))
 848     {
 849       funct_state l = XNEW (struct funct_state_d);
 850       gcc_assert (!has_function_state (dst));
 851       memcpy (l, get_function_state (src), sizeof (*l));
 852       set_function_state (dst, l);
 853     }
 854 }
 855
 856 /* Called when new clone is inserted to callgraph late.  */
 857
 858 static void
 859 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 860 {
 861   if (has_function_state (node))
 862     {
 863       free (get_function_state (node));
 864       set_function_state (node, NULL);
 865     }
 866 }
 867
 868 \f
 869 static void
 870 register_hooks (void)
 871 {
 872   static bool init_p = false;
 873
 874   if (init_p)
 875     return;
 876
 877   init_p = true;
 878
 879   node_removal_hook_holder =
 880       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 881   node_duplication_hook_holder =
 882       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 883   function_insertion_hook_holder =
 884       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 885 }
 886
 887
 888 /* Analyze each function in the cgraph to see if it is locally PURE or
 889    CONST.  */
 890
 891 static void
 892 generate_summary (void)
 893 {
 894   struct cgraph_node *node;
 895
 896   register_hooks ();
 897
 898   /* There are some shared nodes, in particular the initializers on
 899      static declarations.  We do not need to scan them more than once
 900      since all we would be interested in are the addressof
 901      operations.  */
 902   visited_nodes = pointer_set_create ();
 903
 904   /* Process all of the functions.
 905
 906      We process AVAIL_OVERWRITABLE functions.  We can not use the results
 907      by default, but the info can be used at LTO with -fwhole-program or
 908      when function got clonned and the clone is AVAILABLE.  */
 909
 910   for (node = cgraph_nodes; node; node = node->next)
 911     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 912       set_function_state (node, analyze_function (node, true));
 913
 914   pointer_set_destroy (visited_nodes);
 915   visited_nodes = NULL;
 916 }
 917
 918
 919 /* Serialize the ipa info for lto.  */
 920
 921 static void
 922 pure_const_write_summary (cgraph_node_set set,
 923                           varpool_node_set vset ATTRIBUTE_UNUSED)
 924 {
 925   struct cgraph_node *node;
 926   struct lto_simple_output_block *ob
 927     = lto_create_simple_output_block (LTO_section_ipa_pure_const);
 928   unsigned int count = 0;
 929   cgraph_node_set_iterator csi;
 930
 931   for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
 932     {
 933       node = csi_node (csi);
 934       if (node->analyzed && has_function_state (node))
 935         count++;
 936     }
 937
 938   lto_output_uleb128_stream (ob->main_stream, count);
 939
 940   /* Process all of the functions.  */
 941   for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
 942     {
 943       node = csi_node (csi);
 944       if (node->analyzed && has_function_state (node))
 945         {
 946           struct bitpack_d *bp;
 947           funct_state fs;
 948           int node_ref;
 949           lto_cgraph_encoder_t encoder;
 950
 951           fs = get_function_state (node);
 952
 953           encoder = ob->decl_state->cgraph_node_encoder;
 954           node_ref = lto_cgraph_encoder_encode (encoder, node);
 955           lto_output_uleb128_stream (ob->main_stream, node_ref);
 956
 957           /* Note that flags will need to be read in the opposite
 958              order as we are pushing the bitflags into FLAGS.  */
 959           bp = bitpack_create ();
 960           bp_pack_value (bp, fs->pure_const_state, 2);
 961           bp_pack_value (bp, fs->state_previously_known, 2);
 962           bp_pack_value (bp, fs->looping_previously_known, 1);
 963           bp_pack_value (bp, fs->looping, 1);
 964           bp_pack_value (bp, fs->can_throw, 1);
 965           lto_output_bitpack (ob->main_stream, bp);
 966           bitpack_delete (bp);
 967         }
 968     }
 969
 970   lto_destroy_simple_output_block (ob);
 971 }
 972
 973
 974 /* Deserialize the ipa info for lto.  */
 975
 976 static void
 977 pure_const_read_summary (void)
 978 {
 979   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
 980   struct lto_file_decl_data *file_data;
 981   unsigned int j = 0;
 982
 983   register_hooks ();
 984   while ((file_data = file_data_vec[j++]))
 985     {
 986       const char *data;
 987       size_t len;
 988       struct lto_input_block *ib
 989         = lto_create_simple_input_block (file_data,
 990                                          LTO_section_ipa_pure_const,
 991                                          &data, &len);
 992       if (ib)
 993         {
 994           unsigned int i;
 995           unsigned int count = lto_input_uleb128 (ib);
 996
 997           for (i = 0; i < count; i++)
 998             {
 999               unsigned int index;
1000               struct cgraph_node *node;
1001               struct bitpack_d *bp;
1002               funct_state fs;
1003               lto_cgraph_encoder_t encoder;
1004
1005               fs = XCNEW (struct funct_state_d);
1006               index = lto_input_uleb128 (ib);
1007               encoder = file_data->cgraph_node_encoder;
1008               node = lto_cgraph_encoder_deref (encoder, index);
1009               set_function_state (node, fs);
1010
1011               /* Note that the flags must be read in the opposite
1012                  order in which they were written (the bitflags were
1013                  pushed into FLAGS).  */
1014               bp = lto_input_bitpack (ib);
1015               fs->pure_const_state
1016                         = (enum pure_const_state_e) bp_unpack_value (bp, 2);
1017               fs->state_previously_known
1018                         = (enum pure_const_state_e) bp_unpack_value (bp, 2);
1019               fs->looping_previously_known = bp_unpack_value (bp, 1);
1020               fs->looping = bp_unpack_value (bp, 1);
1021               fs->can_throw = bp_unpack_value (bp, 1);
1022               if (dump_file)
1023                 {
1024                   int flags = flags_from_decl_or_type (node->decl);
1025                   fprintf (dump_file, "Read info for %s/%i ",
1026                            cgraph_node_name (node),
1027                            node->uid);
1028                   if (flags & ECF_CONST)
1029                     fprintf (dump_file, " const");
1030                   if (flags & ECF_PURE)
1031                     fprintf (dump_file, " pure");
1032                   if (flags & ECF_NOTHROW)
1033                     fprintf (dump_file, " nothrow");
1034                   fprintf (dump_file, "\n  pure const state: %s\n",
1035                            pure_const_names[fs->pure_const_state]);
1036                   fprintf (dump_file, "  previously known state: %s\n",
1037                            pure_const_names[fs->looping_previously_known]);
1038                   if (fs->looping)
1039                     fprintf (dump_file,"  function is locally looping\n");
1040                   if (fs->looping_previously_known)
1041                     fprintf (dump_file,"  function is previously known looping\n");
1042                   if (fs->can_throw)
1043                     fprintf (dump_file,"  function is locally throwing\n");
1044                 }
1045               bitpack_delete (bp);
1046             }
1047
1048           lto_destroy_simple_input_block (file_data,
1049                                           LTO_section_ipa_pure_const,
1050                                           ib, data, len);
1051         }
1052     }
1053 }
1054
1055
1056 static bool
1057 ignore_edge (struct cgraph_edge *e)
1058 {
1059   return (!e->can_throw_external);
1060 }
1061
1062 /* Return true if NODE is self recursive function.  */
1063
1064 static bool
1065 self_recursive_p (struct cgraph_node *node)
1066 {
1067   struct cgraph_edge *e;
1068   for (e = node->callees; e; e = e->next_callee)
1069     if (e->callee == node)
1070       return true;
1071   return false;
1072 }
1073
1074 /* Produce transitive closure over the callgraph and compute pure/const
1075    attributes.  */
1076
1077 static void
1078 propagate_pure_const (void)
1079 {
1080   struct cgraph_node *node;
1081   struct cgraph_node *w;
1082   struct cgraph_node **order =
1083     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1084   int order_pos;
1085   int i;
1086   struct ipa_dfs_info * w_info;
1087
1088   order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
1089   if (dump_file)
1090     {
1091       dump_cgraph (dump_file);
1092       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1093     }
1094
1095   /* Propagate the local information thru the call graph to produce
1096      the global information.  All the nodes within a cycle will have
1097      the same info so we collapse cycles first.  Then we can do the
1098      propagation in one pass from the leaves to the roots.  */
1099   for (i = 0; i < order_pos; i++ )
1100     {
1101       enum pure_const_state_e pure_const_state = IPA_CONST;
1102       bool looping = false;
1103       int count = 0;
1104       node = order[i];
1105
1106       if (dump_file && (dump_flags & TDF_DETAILS))
1107         fprintf (dump_file, "Starting cycle\n");
1108
1109       /* Find the worst state for any node in the cycle.  */
1110       w = node;
1111       while (w && pure_const_state != IPA_NEITHER)
1112         {
1113           struct cgraph_edge *e;
1114           struct cgraph_edge *ie;
1115           int i;
1116           struct ipa_ref *ref;
1117
1118           funct_state w_l = get_function_state (w);
1119           if (dump_file && (dump_flags & TDF_DETAILS))
1120             fprintf (dump_file, "  Visiting %s/%i state:%s looping %i\n",
1121                      cgraph_node_name (w),
1122                      w->uid,
1123                      pure_const_names[w_l->pure_const_state],
1124                      w_l->looping);
1125
1126           /* First merge in function body properties.  */
1127           worse_state (&pure_const_state, &looping,
1128                        w_l->pure_const_state, w_l->looping);
1129           if (pure_const_state == IPA_NEITHER)
1130             break;
1131
1132           /* For overwritable nodes we can not assume anything.  */
1133           if (cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
1134             {
1135               worse_state (&pure_const_state, &looping,
1136                            w_l->state_previously_known,
1137                            w_l->looping_previously_known);
1138               if (dump_file && (dump_flags & TDF_DETAILS))
1139                 {
1140                   fprintf (dump_file,
1141                            "    Overwritable. state %s looping %i\n",
1142                            pure_const_names[w_l->state_previously_known],
1143                            w_l->looping_previously_known);
1144                 }
1145               break;
1146             }
1147
1148           count++;
1149
1150           /* We consider recursive cycles as possibly infinite.
1151              This might be relaxed since infinite recursion leads to stack
1152              overflow.  */
1153           if (count > 1)
1154             looping = true;
1155
1156           /* Now walk the edges and merge in callee properties.  */
1157           for (e = w->callees; e; e = e->next_callee)
1158             {
1159               struct cgraph_node *y = e->callee;
1160               enum pure_const_state_e edge_state = IPA_CONST;
1161               bool edge_looping = false;
1162
1163               if (dump_file && (dump_flags & TDF_DETAILS))
1164                 {
1165                   fprintf (dump_file,
1166                            "    Call to %s/%i",
1167                            cgraph_node_name (e->callee),
1168                            e->callee->uid);
1169                 }
1170               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1171                 {
1172                   funct_state y_l = get_function_state (y);
1173                   if (dump_file && (dump_flags & TDF_DETAILS))
1174                     {
1175                       fprintf (dump_file,
1176                                " state:%s looping:%i\n",
1177                                pure_const_names[y_l->pure_const_state],
1178                                y_l->looping);
1179                     }
1180                   if (y_l->pure_const_state > IPA_PURE
1181                       && cgraph_edge_cannot_lead_to_return (e))
1182                     {
1183                       if (dump_file && (dump_flags & TDF_DETAILS))
1184                         fprintf (dump_file,
1185                                  "        Ignoring side effects"
1186                                  " -> pure, looping\n");
1187                       edge_state = IPA_PURE;
1188                       edge_looping = true;
1189                     }
1190                   else
1191                     {
1192                       edge_state = y_l->pure_const_state;
1193                       edge_looping = y_l->looping;
1194                     }
1195                 }
1196               else if (special_builtlin_state (&edge_state, &edge_looping,
1197                                                y->decl))
1198                 ;
1199               else
1200                 state_from_flags (&edge_state, &edge_looping,
1201                                   flags_from_decl_or_type (y->decl),
1202                                   cgraph_edge_cannot_lead_to_return (e));
1203
1204               /* Merge the results with what we already know.  */
1205               better_state (&edge_state, &edge_looping,
1206                             w_l->state_previously_known,
1207                             w_l->looping_previously_known);
1208               worse_state (&pure_const_state, &looping,
1209                            edge_state, edge_looping);
1210               if (pure_const_state == IPA_NEITHER)
1211                 break;
1212             }
1213           if (pure_const_state == IPA_NEITHER)
1214             break;
1215
1216           /* Now process the indirect call.  */
1217           for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1218             {
1219               enum pure_const_state_e edge_state = IPA_CONST;
1220               bool edge_looping = false;
1221
1222               if (dump_file && (dump_flags & TDF_DETAILS))
1223                 fprintf (dump_file, "    Indirect call");
1224               state_from_flags (&edge_state, &edge_looping,
1225                                 ie->indirect_info->ecf_flags,
1226                                 cgraph_edge_cannot_lead_to_return (ie));
1227               /* Merge the results with what we already know.  */
1228               better_state (&edge_state, &edge_looping,
1229                             w_l->state_previously_known,
1230                             w_l->looping_previously_known);
1231               worse_state (&pure_const_state, &looping,
1232                            edge_state, edge_looping);
1233               if (pure_const_state == IPA_NEITHER)
1234                 break;
1235             }
1236           if (pure_const_state == IPA_NEITHER)
1237             break;
1238
1239           /* And finally all loads and stores.  */
1240           for (i = 0; ipa_ref_list_reference_iterate (&node->ref_list, i, ref); i++)
1241             {
1242               enum pure_const_state_e ref_state = IPA_CONST;
1243               bool ref_looping = false;
1244               switch (ref->use)
1245                 {
1246                 case IPA_REF_LOAD:
1247                   /* readonly reads are safe.  */
1248                   if (TREE_READONLY (ipa_ref_varpool_node (ref)->decl))
1249                     break;
1250                   if (dump_file && (dump_flags & TDF_DETAILS))
1251                     fprintf (dump_file, "    nonreadonly global var read\n");
1252                   ref_state = IPA_PURE;
1253                   break;
1254                 case IPA_REF_STORE:
1255                   if (ipa_ref_cannot_lead_to_return (ref))
1256                     break;
1257                   ref_state = IPA_NEITHER;
1258                   if (dump_file && (dump_flags & TDF_DETAILS))
1259                     fprintf (dump_file, "    global var write\n");
1260                   break;
1261                 case IPA_REF_ADDR:
1262                   break;
1263                 }
1264               better_state (&ref_state, &ref_looping,
1265                             w_l->state_previously_known,
1266                             w_l->looping_previously_known);
1267               worse_state (&pure_const_state, &looping,
1268                            ref_state, ref_looping);
1269               if (pure_const_state == IPA_NEITHER)
1270                 break;
1271             }
1272           w_info = (struct ipa_dfs_info *) w->aux;
1273           w = w_info->next_cycle;
1274         }
1275       if (dump_file && (dump_flags & TDF_DETAILS))
1276         fprintf (dump_file, "Result %s looping %i\n",
1277                  pure_const_names [pure_const_state],
1278                  looping);
1279
1280       /* Copy back the region's pure_const_state which is shared by
1281          all nodes in the region.  */
1282       w = node;
1283       while (w)
1284         {
1285           funct_state w_l = get_function_state (w);
1286           enum pure_const_state_e this_state = pure_const_state;
1287           bool this_looping = looping;
1288
1289           if (w_l->state_previously_known != IPA_NEITHER
1290               && this_state > w_l->state_previously_known)
1291             {
1292               this_state = w_l->state_previously_known;
1293               this_looping |= w_l->looping_previously_known;
1294             }
1295           if (!this_looping && self_recursive_p (w))
1296             this_looping = true;
1297           if (!w_l->looping_previously_known)
1298             this_looping = false;
1299
1300           /* All nodes within a cycle share the same info.  */
1301           w_l->pure_const_state = this_state;
1302           w_l->looping = this_looping;
1303
1304           switch (this_state)
1305             {
1306             case IPA_CONST:
1307               if (!TREE_READONLY (w->decl))
1308                 {
1309                   warn_function_const (w->decl, !this_looping);
1310                   if (dump_file)
1311                     fprintf (dump_file, "Function found to be %sconst: %s\n",
1312                              this_looping ? "looping " : "",
1313                              cgraph_node_name (w));
1314                 }
1315               cgraph_set_readonly_flag (w, true);
1316               cgraph_set_looping_const_or_pure_flag (w, this_looping);
1317               break;
1318
1319             case IPA_PURE:
1320               if (!DECL_PURE_P (w->decl))
1321                 {
1322                   warn_function_pure (w->decl, !this_looping);
1323                   if (dump_file)
1324                     fprintf (dump_file, "Function found to be %spure: %s\n",
1325                              this_looping ? "looping " : "",
1326                              cgraph_node_name (w));
1327                 }
1328               cgraph_set_pure_flag (w, true);
1329               cgraph_set_looping_const_or_pure_flag (w, this_looping);
1330               break;
1331
1332             default:
1333               break;
1334             }
1335           w_info = (struct ipa_dfs_info *) w->aux;
1336           w = w_info->next_cycle;
1337         }
1338     }
1339
1340   /* Cleanup. */
1341   for (node = cgraph_nodes; node; node = node->next)
1342     {
1343       /* Get rid of the aux information.  */
1344       if (node->aux)
1345         {
1346           w_info = (struct ipa_dfs_info *) node->aux;
1347           free (node->aux);
1348           node->aux = NULL;
1349         }
1350     }
1351
1352   free (order);
1353 }
1354
1355 /* Produce transitive closure over the callgraph and compute nothrow
1356    attributes.  */
1357
1358 static void
1359 propagate_nothrow (void)
1360 {
1361   struct cgraph_node *node;
1362   struct cgraph_node *w;
1363   struct cgraph_node **order =
1364     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1365   int order_pos;
1366   int i;
1367   struct ipa_dfs_info * w_info;
1368
1369   order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
1370   if (dump_file)
1371     {
1372       dump_cgraph (dump_file);
1373       ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
1374     }
1375
1376   /* Propagate the local information thru the call graph to produce
1377      the global information.  All the nodes within a cycle will have
1378      the same info so we collapse cycles first.  Then we can do the
1379      propagation in one pass from the leaves to the roots.  */
1380   for (i = 0; i < order_pos; i++ )
1381     {
1382       bool can_throw = false;
1383       node = order[i];
1384
1385       /* Find the worst state for any node in the cycle.  */
1386       w = node;
1387       while (w)
1388         {
1389           struct cgraph_edge *e, *ie;
1390           funct_state w_l = get_function_state (w);
1391
1392           if (w_l->can_throw
1393               || cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
1394             can_throw = true;
1395
1396           if (can_throw)
1397             break;
1398
1399           for (e = w->callees; e; e = e->next_callee)
1400             {
1401               struct cgraph_node *y = e->callee;
1402
1403               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1404                 {
1405                   funct_state y_l = get_function_state (y);
1406
1407                   if (can_throw)
1408                     break;
1409                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
1410                       && e->can_throw_external)
1411                     can_throw = true;
1412                 }
1413               else if (e->can_throw_external && !TREE_NOTHROW (y->decl))
1414                 can_throw = true;
1415             }
1416           for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1417             if (ie->can_throw_external)
1418               can_throw = true;
1419           w_info = (struct ipa_dfs_info *) w->aux;
1420           w = w_info->next_cycle;
1421         }
1422
1423       /* Copy back the region's pure_const_state which is shared by
1424          all nodes in the region.  */
1425       w = node;
1426       while (w)
1427         {
1428           funct_state w_l = get_function_state (w);
1429           if (!can_throw && !TREE_NOTHROW (w->decl))
1430             {
1431               struct cgraph_edge *e;
1432               cgraph_set_nothrow_flag (w, true);
1433               for (e = w->callers; e; e = e->next_caller)
1434                 e->can_throw_external = false;
1435               if (dump_file)
1436                 fprintf (dump_file, "Function found to be nothrow: %s\n",
1437                          cgraph_node_name (w));
1438             }
1439           else if (can_throw && !TREE_NOTHROW (w->decl))
1440             w_l->can_throw = true;
1441           w_info = (struct ipa_dfs_info *) w->aux;
1442           w = w_info->next_cycle;
1443         }
1444     }
1445
1446   /* Cleanup. */
1447   for (node = cgraph_nodes; node; node = node->next)
1448     {
1449       /* Get rid of the aux information.  */
1450       if (node->aux)
1451         {
1452           w_info = (struct ipa_dfs_info *) node->aux;
1453           free (node->aux);
1454           node->aux = NULL;
1455         }
1456     }
1457
1458   free (order);
1459 }
1460
1461
1462 /* Produce the global information by preforming a transitive closure
1463    on the local information that was produced by generate_summary.  */
1464
1465 static unsigned int
1466 propagate (void)
1467 {
1468   struct cgraph_node *node;
1469
1470   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1471   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1472   cgraph_remove_node_removal_hook (node_removal_hook_holder);
1473
1474   /* Nothrow makes more function to not lead to return and improve
1475      later analysis.  */
1476   propagate_nothrow ();
1477   propagate_pure_const ();
1478
1479   /* Cleanup. */
1480   for (node = cgraph_nodes; node; node = node->next)
1481     if (has_function_state (node))
1482       free (get_function_state (node));
1483   VEC_free (funct_state, heap, funct_state_vec);
1484   finish_state ();
1485   return 0;
1486 }
1487
1488 static bool
1489 gate_pure_const (void)
1490 {
1491   return (flag_ipa_pure_const
1492           /* Don't bother doing anything if the program has errors.  */
1493           && !seen_error ());
1494 }
1495
1496 struct ipa_opt_pass_d pass_ipa_pure_const =
1497 {
1498  {
1499   IPA_PASS,
1500   "pure-const",                         /* name */
1501   gate_pure_const,                      /* gate */
1502   propagate,                            /* execute */
1503   NULL,                                 /* sub */
1504   NULL,                                 /* next */
1505   0,                                    /* static_pass_number */
1506   TV_IPA_PURE_CONST,                    /* tv_id */
1507   0,                                    /* properties_required */
1508   0,                                    /* properties_provided */
1509   0,                                    /* properties_destroyed */
1510   0,                                    /* todo_flags_start */
1511   0                                     /* todo_flags_finish */
1512  },
1513  generate_summary,                      /* generate_summary */
1514  pure_const_write_summary,              /* write_summary */
1515  pure_const_read_summary,               /* read_summary */
1516  NULL,                                  /* write_optimization_summary */
1517  NULL,                                  /* read_optimization_summary */
1518  NULL,                                  /* stmt_fixup */
1519  0,                                     /* TODOs */
1520  NULL,                                  /* function_transform */
1521  NULL                                   /* variable_transform */
1522 };
1523
1524 /* Return true if function should be skipped for local pure const analysis.  */
1525
1526 static bool
1527 skip_function_for_local_pure_const (struct cgraph_node *node)
1528 {
1529   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1530      we must not promote functions that are called by already processed functions.  */
1531
1532   if (function_called_by_processed_nodes_p ())
1533     {
1534       if (dump_file)
1535         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
1536       return true;
1537     }
1538   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
1539     {
1540       if (dump_file)
1541         fprintf (dump_file, "Function is not available or overwrittable; not analyzing.\n");
1542       return true;
1543     }
1544   return false;
1545 }
1546
1547 /* Simple local pass for pure const discovery reusing the analysis from
1548    ipa_pure_const.   This pass is effective when executed together with
1549    other optimization passes in early optimization pass queue.  */
1550
1551 static unsigned int
1552 local_pure_const (void)
1553 {
1554   bool changed = false;
1555   funct_state l;
1556   bool skip;
1557   struct cgraph_node *node;
1558
1559   node = cgraph_node (current_function_decl);
1560   skip = skip_function_for_local_pure_const (node);
1561   if (!warn_suggest_attribute_const
1562       && !warn_suggest_attribute_pure
1563       && skip)
1564     return 0;
1565
1566   /* First do NORETURN discovery.  */
1567   if (!skip && !TREE_THIS_VOLATILE (current_function_decl)
1568       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
1569     {
1570       warn_function_noreturn (cfun->decl);
1571       if (dump_file)
1572         fprintf (dump_file, "Function found to be noreturn: %s\n",
1573                  lang_hooks.decl_printable_name (current_function_decl, 2));
1574
1575       /* Update declaration and reduce profile to executed once.  */
1576       TREE_THIS_VOLATILE (current_function_decl) = 1;
1577       if (node->frequency > NODE_FREQUENCY_EXECUTED_ONCE)
1578         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
1579
1580       changed = true;
1581     }
1582   l = analyze_function (node, false);
1583
1584   switch (l->pure_const_state)
1585     {
1586     case IPA_CONST:
1587       if (!TREE_READONLY (current_function_decl))
1588         {
1589           warn_function_const (current_function_decl, !l->looping);
1590           if (!skip)
1591             {
1592               cgraph_set_readonly_flag (node, true);
1593               cgraph_set_looping_const_or_pure_flag (node, l->looping);
1594               changed = true;
1595             }
1596           if (dump_file)
1597             fprintf (dump_file, "Function found to be %sconst: %s\n",
1598                      l->looping ? "looping " : "",
1599                      lang_hooks.decl_printable_name (current_function_decl,
1600                                                      2));
1601         }
1602       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1603                && !l->looping)
1604         {
1605           if (!skip)
1606             {
1607               cgraph_set_looping_const_or_pure_flag (node, false);
1608               changed = true;
1609             }
1610           if (dump_file)
1611             fprintf (dump_file, "Function found to be non-looping: %s\n",
1612                      lang_hooks.decl_printable_name (current_function_decl,
1613                                                      2));
1614         }
1615       break;
1616
1617     case IPA_PURE:
1618       if (!DECL_PURE_P (current_function_decl))
1619         {
1620           if (!skip)
1621             {
1622               cgraph_set_pure_flag (node, true);
1623               cgraph_set_looping_const_or_pure_flag (node, l->looping);
1624               changed = true;
1625             }
1626           warn_function_pure (current_function_decl, !l->looping);
1627           if (dump_file)
1628             fprintf (dump_file, "Function found to be %spure: %s\n",
1629                      l->looping ? "looping " : "",
1630                      lang_hooks.decl_printable_name (current_function_decl,
1631                                                      2));
1632         }
1633       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1634                && !l->looping)
1635         {
1636           if (!skip)
1637             {
1638               cgraph_set_looping_const_or_pure_flag (node, false);
1639               changed = true;
1640             }
1641           if (dump_file)
1642             fprintf (dump_file, "Function found to be non-looping: %s\n",
1643                      lang_hooks.decl_printable_name (current_function_decl,
1644                                                      2));
1645         }
1646       break;
1647
1648     default:
1649       break;
1650     }
1651   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1652     {
1653       struct cgraph_edge *e;
1654
1655       cgraph_set_nothrow_flag (node, true);
1656       for (e = node->callers; e; e = e->next_caller)
1657         e->can_throw_external = false;
1658       changed = true;
1659       if (dump_file)
1660         fprintf (dump_file, "Function found to be nothrow: %s\n",
1661                  lang_hooks.decl_printable_name (current_function_decl,
1662                                                  2));
1663     }
1664   if (l)
1665     free (l);
1666   if (changed)
1667     return execute_fixup_cfg ();
1668   else
1669     return 0;
1670 }
1671
1672 struct gimple_opt_pass pass_local_pure_const =
1673 {
1674  {
1675   GIMPLE_PASS,
1676   "local-pure-const",                   /* name */
1677   gate_pure_const,                      /* gate */
1678   local_pure_const,                     /* execute */
1679   NULL,                                 /* sub */
1680   NULL,                                 /* next */
1681   0,                                    /* static_pass_number */
1682   TV_IPA_PURE_CONST,                    /* tv_id */
1683   0,                                    /* properties_required */
1684   0,                                    /* properties_provided */
1685   0,                                    /* properties_destroyed */
1686   0,                                    /* todo_flags_start */
1687   0                                     /* todo_flags_finish */
1688  }
1689 };