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