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