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
 735   if (dump_file)
 736     {
 737       fprintf (dump_file, "\n\n local analysis of %s\n ",
 738                cgraph_node_name (fn));
 739     }
 740
 741   push_cfun (DECL_STRUCT_FUNCTION (decl));
 742   current_function_decl = decl;
 743
 744   FOR_EACH_BB (this_block)
 745     {
 746       gimple_stmt_iterator gsi;
 747       struct walk_stmt_info wi;
 748
 749       memset (&wi, 0, sizeof(wi));
 750       for (gsi = gsi_start_bb (this_block);
 751            !gsi_end_p (gsi);
 752            gsi_next (&gsi))
 753         {
 754           check_stmt (&gsi, l, ipa);
 755           if (l->pure_const_state == IPA_NEITHER && l->looping && l->can_throw)
 756             goto end;
 757         }
 758     }
 759
 760 end:
 761   if (l->pure_const_state != IPA_NEITHER)
 762     {
 763       /* Const functions cannot have back edges (an
 764          indication of possible infinite loop side
 765          effect.  */
 766       if (mark_dfs_back_edges ())
 767         {
 768           /* Preheaders are needed for SCEV to work.
 769              Simple latches and recorded exits improve chances that loop will
 770              proved to be finite in testcases such as in loop-15.c and loop-24.c  */
 771           loop_optimizer_init (LOOPS_NORMAL
 772                                | LOOPS_HAVE_RECORDED_EXITS);
 773           if (dump_file && (dump_flags & TDF_DETAILS))
 774             flow_loops_dump (dump_file, NULL, 0);
 775           if (mark_irreducible_loops ())
 776             {
 777               if (dump_file)
 778                 fprintf (dump_file, "    has irreducible loops\n");
 779               l->looping = true;
 780             }
 781           else
 782             {
 783               loop_iterator li;
 784               struct loop *loop;
 785               scev_initialize ();
 786               FOR_EACH_LOOP (li, loop, 0)
 787                 if (!finite_loop_p (loop))
 788                   {
 789                     if (dump_file)
 790                       fprintf (dump_file, "    can not prove finiteness of loop %i\n", loop->num);
 791                     l->looping =true;
 792                     break;
 793                   }
 794               scev_finalize ();
 795             }
 796           loop_optimizer_finalize ();
 797         }
 798     }
 799
 800   if (dump_file && (dump_flags & TDF_DETAILS))
 801     fprintf (dump_file, "    checking previously known:");
 802   state_from_flags (&l->state_previously_known, &l->looping_previously_known,
 803                     flags_from_decl_or_type (fn->decl),
 804                     cgraph_node_cannot_return (fn));
 805
 806   better_state (&l->pure_const_state, &l->looping,
 807                 l->state_previously_known,
 808                 l->looping_previously_known);
 809   if (TREE_NOTHROW (decl))
 810     l->can_throw = false;
 811
 812   pop_cfun ();
 813   current_function_decl = old_decl;
 814   if (dump_file)
 815     {
 816       if (l->looping)
 817         fprintf (dump_file, "Function is locally looping.\n");
 818       if (l->can_throw)
 819         fprintf (dump_file, "Function is locally throwing.\n");
 820       if (l->pure_const_state == IPA_CONST)
 821         fprintf (dump_file, "Function is locally const.\n");
 822       if (l->pure_const_state == IPA_PURE)
 823         fprintf (dump_file, "Function is locally pure.\n");
 824     }
 825   return l;
 826 }
 827
 828 /* Called when new function is inserted to callgraph late.  */
 829 static void
 830 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 831 {
 832  if (cgraph_function_body_availability (node) < AVAIL_OVERWRITABLE)
 833    return;
 834   /* There are some shared nodes, in particular the initializers on
 835      static declarations.  We do not need to scan them more than once
 836      since all we would be interested in are the addressof
 837      operations.  */
 838   visited_nodes = pointer_set_create ();
 839   if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 840     set_function_state (node, analyze_function (node, true));
 841   pointer_set_destroy (visited_nodes);
 842   visited_nodes = NULL;
 843 }
 844
 845 /* Called when new clone is inserted to callgraph late.  */
 846
 847 static void
 848 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 849                      void *data ATTRIBUTE_UNUSED)
 850 {
 851   if (has_function_state (src))
 852     {
 853       funct_state l = XNEW (struct funct_state_d);
 854       gcc_assert (!has_function_state (dst));
 855       memcpy (l, get_function_state (src), sizeof (*l));
 856       set_function_state (dst, l);
 857     }
 858 }
 859
 860 /* Called when new clone is inserted to callgraph late.  */
 861
 862 static void
 863 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 864 {
 865   if (has_function_state (node))
 866     {
 867       funct_state l = get_function_state (node);
 868       if (l != &varying_state)
 869         free (l);
 870       set_function_state (node, NULL);
 871     }
 872 }
 873
 874 \f
 875 static void
 876 register_hooks (void)
 877 {
 878   static bool init_p = false;
 879
 880   if (init_p)
 881     return;
 882
 883   init_p = true;
 884
 885   node_removal_hook_holder =
 886       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 887   node_duplication_hook_holder =
 888       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 889   function_insertion_hook_holder =
 890       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 891 }
 892
 893
 894 /* Analyze each function in the cgraph to see if it is locally PURE or
 895    CONST.  */
 896
 897 static void
 898 generate_summary (void)
 899 {
 900   struct cgraph_node *node;
 901
 902   register_hooks ();
 903
 904   /* There are some shared nodes, in particular the initializers on
 905      static declarations.  We do not need to scan them more than once
 906      since all we would be interested in are the addressof
 907      operations.  */
 908   visited_nodes = pointer_set_create ();
 909
 910   /* Process all of the functions.
 911
 912      We process AVAIL_OVERWRITABLE functions.  We can not use the results
 913      by default, but the info can be used at LTO with -fwhole-program or
 914      when function got cloned and the clone is AVAILABLE.  */
 915
 916   for (node = cgraph_nodes; node; node = node->next)
 917     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 918       set_function_state (node, analyze_function (node, true));
 919
 920   pointer_set_destroy (visited_nodes);
 921   visited_nodes = NULL;
 922 }
 923
 924
 925 /* Serialize the ipa info for lto.  */
 926
 927 static void
 928 pure_const_write_summary (cgraph_node_set set,
 929                           varpool_node_set vset ATTRIBUTE_UNUSED)
 930 {
 931   struct cgraph_node *node;
 932   struct lto_simple_output_block *ob
 933     = lto_create_simple_output_block (LTO_section_ipa_pure_const);
 934   unsigned int count = 0;
 935   cgraph_node_set_iterator csi;
 936
 937   for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
 938     {
 939       node = csi_node (csi);
 940       if (node->analyzed && has_function_state (node))
 941         count++;
 942     }
 943
 944   lto_output_uleb128_stream (ob->main_stream, count);
 945
 946   /* Process all of the functions.  */
 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         {
 952           struct bitpack_d bp;
 953           funct_state fs;
 954           int node_ref;
 955           lto_cgraph_encoder_t encoder;
 956
 957           fs = get_function_state (node);
 958
 959           encoder = ob->decl_state->cgraph_node_encoder;
 960           node_ref = lto_cgraph_encoder_encode (encoder, node);
 961           lto_output_uleb128_stream (ob->main_stream, node_ref);
 962
 963           /* Note that flags will need to be read in the opposite
 964              order as we are pushing the bitflags into FLAGS.  */
 965           bp = bitpack_create (ob->main_stream);
 966           bp_pack_value (&bp, fs->pure_const_state, 2);
 967           bp_pack_value (&bp, fs->state_previously_known, 2);
 968           bp_pack_value (&bp, fs->looping_previously_known, 1);
 969           bp_pack_value (&bp, fs->looping, 1);
 970           bp_pack_value (&bp, fs->can_throw, 1);
 971           lto_output_bitpack (&bp);
 972         }
 973     }
 974
 975   lto_destroy_simple_output_block (ob);
 976 }
 977
 978
 979 /* Deserialize the ipa info for lto.  */
 980
 981 static void
 982 pure_const_read_summary (void)
 983 {
 984   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
 985   struct lto_file_decl_data *file_data;
 986   unsigned int j = 0;
 987
 988   register_hooks ();
 989   while ((file_data = file_data_vec[j++]))
 990     {
 991       const char *data;
 992       size_t len;
 993       struct lto_input_block *ib
 994         = lto_create_simple_input_block (file_data,
 995                                          LTO_section_ipa_pure_const,
 996                                          &data, &len);
 997       if (ib)
 998         {
 999           unsigned int i;
1000           unsigned int count = lto_input_uleb128 (ib);
1001
1002           for (i = 0; i < count; i++)
1003             {
1004               unsigned int index;
1005               struct cgraph_node *node;
1006               struct bitpack_d bp;
1007               funct_state fs;
1008               lto_cgraph_encoder_t encoder;
1009
1010               fs = XCNEW (struct funct_state_d);
1011               index = lto_input_uleb128 (ib);
1012               encoder = file_data->cgraph_node_encoder;
1013               node = lto_cgraph_encoder_deref (encoder, index);
1014               set_function_state (node, fs);
1015
1016               /* Note that the flags must be read in the opposite
1017                  order in which they were written (the bitflags were
1018                  pushed into FLAGS).  */
1019               bp = lto_input_bitpack (ib);
1020               fs->pure_const_state
1021                         = (enum pure_const_state_e) bp_unpack_value (&bp, 2);
1022               fs->state_previously_known
1023                         = (enum pure_const_state_e) bp_unpack_value (&bp, 2);
1024               fs->looping_previously_known = bp_unpack_value (&bp, 1);
1025               fs->looping = bp_unpack_value (&bp, 1);
1026               fs->can_throw = bp_unpack_value (&bp, 1);
1027               if (dump_file)
1028                 {
1029                   int flags = flags_from_decl_or_type (node->decl);
1030                   fprintf (dump_file, "Read info for %s/%i ",
1031                            cgraph_node_name (node),
1032                            node->uid);
1033                   if (flags & ECF_CONST)
1034                     fprintf (dump_file, " const");
1035                   if (flags & ECF_PURE)
1036                     fprintf (dump_file, " pure");
1037                   if (flags & ECF_NOTHROW)
1038                     fprintf (dump_file, " nothrow");
1039                   fprintf (dump_file, "\n  pure const state: %s\n",
1040                            pure_const_names[fs->pure_const_state]);
1041                   fprintf (dump_file, "  previously known state: %s\n",
1042                            pure_const_names[fs->looping_previously_known]);
1043                   if (fs->looping)
1044                     fprintf (dump_file,"  function is locally looping\n");
1045                   if (fs->looping_previously_known)
1046                     fprintf (dump_file,"  function is previously known looping\n");
1047                   if (fs->can_throw)
1048                     fprintf (dump_file,"  function is locally throwing\n");
1049                 }
1050             }
1051
1052           lto_destroy_simple_input_block (file_data,
1053                                           LTO_section_ipa_pure_const,
1054                                           ib, data, len);
1055         }
1056     }
1057 }
1058
1059
1060 static bool
1061 ignore_edge (struct cgraph_edge *e)
1062 {
1063   return (!e->can_throw_external);
1064 }
1065
1066 /* Return true if NODE is self recursive function.  */
1067
1068 static bool
1069 self_recursive_p (struct cgraph_node *node)
1070 {
1071   struct cgraph_edge *e;
1072   for (e = node->callees; e; e = e->next_callee)
1073     if (e->callee == node)
1074       return true;
1075   return false;
1076 }
1077
1078 /* Produce transitive closure over the callgraph and compute pure/const
1079    attributes.  */
1080
1081 static void
1082 propagate_pure_const (void)
1083 {
1084   struct cgraph_node *node;
1085   struct cgraph_node *w;
1086   struct cgraph_node **order =
1087     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1088   int order_pos;
1089   int i;
1090   struct ipa_dfs_info * w_info;
1091
1092   order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
1093   if (dump_file)
1094     {
1095       dump_cgraph (dump_file);
1096       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1097     }
1098
1099   /* Propagate the local information thru the call graph to produce
1100      the global information.  All the nodes within a cycle will have
1101      the same info so we collapse cycles first.  Then we can do the
1102      propagation in one pass from the leaves to the roots.  */
1103   for (i = 0; i < order_pos; i++ )
1104     {
1105       enum pure_const_state_e pure_const_state = IPA_CONST;
1106       bool looping = false;
1107       int count = 0;
1108       node = order[i];
1109
1110       if (dump_file && (dump_flags & TDF_DETAILS))
1111         fprintf (dump_file, "Starting cycle\n");
1112
1113       /* Find the worst state for any node in the cycle.  */
1114       w = node;
1115       while (w && pure_const_state != IPA_NEITHER)
1116         {
1117           struct cgraph_edge *e;
1118           struct cgraph_edge *ie;
1119           int i;
1120           struct ipa_ref *ref;
1121
1122           funct_state w_l = get_function_state (w);
1123           if (dump_file && (dump_flags & TDF_DETAILS))
1124             fprintf (dump_file, "  Visiting %s/%i state:%s looping %i\n",
1125                      cgraph_node_name (w),
1126                      w->uid,
1127                      pure_const_names[w_l->pure_const_state],
1128                      w_l->looping);
1129
1130           /* First merge in function body properties.  */
1131           worse_state (&pure_const_state, &looping,
1132                        w_l->pure_const_state, w_l->looping);
1133           if (pure_const_state == IPA_NEITHER)
1134             break;
1135
1136           /* For overwritable nodes we can not assume anything.  */
1137           if (cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
1138             {
1139               worse_state (&pure_const_state, &looping,
1140                            w_l->state_previously_known,
1141                            w_l->looping_previously_known);
1142               if (dump_file && (dump_flags & TDF_DETAILS))
1143                 {
1144                   fprintf (dump_file,
1145                            "    Overwritable. state %s looping %i\n",
1146                            pure_const_names[w_l->state_previously_known],
1147                            w_l->looping_previously_known);
1148                 }
1149               break;
1150             }
1151
1152           count++;
1153
1154           /* We consider recursive cycles as possibly infinite.
1155              This might be relaxed since infinite recursion leads to stack
1156              overflow.  */
1157           if (count > 1)
1158             looping = true;
1159
1160           /* Now walk the edges and merge in callee properties.  */
1161           for (e = w->callees; e; e = e->next_callee)
1162             {
1163               struct cgraph_node *y = e->callee;
1164               enum pure_const_state_e edge_state = IPA_CONST;
1165               bool edge_looping = false;
1166
1167               if (dump_file && (dump_flags & TDF_DETAILS))
1168                 {
1169                   fprintf (dump_file,
1170                            "    Call to %s/%i",
1171                            cgraph_node_name (e->callee),
1172                            e->callee->uid);
1173                 }
1174               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1175                 {
1176                   funct_state y_l = get_function_state (y);
1177                   if (dump_file && (dump_flags & TDF_DETAILS))
1178                     {
1179                       fprintf (dump_file,
1180                                " state:%s looping:%i\n",
1181                                pure_const_names[y_l->pure_const_state],
1182                                y_l->looping);
1183                     }
1184                   if (y_l->pure_const_state > IPA_PURE
1185                       && cgraph_edge_cannot_lead_to_return (e))
1186                     {
1187                       if (dump_file && (dump_flags & TDF_DETAILS))
1188                         fprintf (dump_file,
1189                                  "        Ignoring side effects"
1190                                  " -> pure, looping\n");
1191                       edge_state = IPA_PURE;
1192                       edge_looping = true;
1193                     }
1194                   else
1195                     {
1196                       edge_state = y_l->pure_const_state;
1197                       edge_looping = y_l->looping;
1198                     }
1199                 }
1200               else if (special_builtin_state (&edge_state, &edge_looping,
1201                                                y->decl))
1202                 ;
1203               else
1204                 state_from_flags (&edge_state, &edge_looping,
1205                                   flags_from_decl_or_type (y->decl),
1206                                   cgraph_edge_cannot_lead_to_return (e));
1207
1208               /* Merge the results with what we already know.  */
1209               better_state (&edge_state, &edge_looping,
1210                             w_l->state_previously_known,
1211                             w_l->looping_previously_known);
1212               worse_state (&pure_const_state, &looping,
1213                            edge_state, edge_looping);
1214               if (pure_const_state == IPA_NEITHER)
1215                 break;
1216             }
1217           if (pure_const_state == IPA_NEITHER)
1218             break;
1219
1220           /* Now process the indirect call.  */
1221           for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1222             {
1223               enum pure_const_state_e edge_state = IPA_CONST;
1224               bool edge_looping = false;
1225
1226               if (dump_file && (dump_flags & TDF_DETAILS))
1227                 fprintf (dump_file, "    Indirect call");
1228               state_from_flags (&edge_state, &edge_looping,
1229                                 ie->indirect_info->ecf_flags,
1230                                 cgraph_edge_cannot_lead_to_return (ie));
1231               /* Merge the results with what we already know.  */
1232               better_state (&edge_state, &edge_looping,
1233                             w_l->state_previously_known,
1234                             w_l->looping_previously_known);
1235               worse_state (&pure_const_state, &looping,
1236                            edge_state, edge_looping);
1237               if (pure_const_state == IPA_NEITHER)
1238                 break;
1239             }
1240           if (pure_const_state == IPA_NEITHER)
1241             break;
1242
1243           /* And finally all loads and stores.  */
1244           for (i = 0; ipa_ref_list_reference_iterate (&node->ref_list, i, ref); i++)
1245             {
1246               enum pure_const_state_e ref_state = IPA_CONST;
1247               bool ref_looping = false;
1248               switch (ref->use)
1249                 {
1250                 case IPA_REF_LOAD:
1251                   /* readonly reads are safe.  */
1252                   if (TREE_READONLY (ipa_ref_varpool_node (ref)->decl))
1253                     break;
1254                   if (dump_file && (dump_flags & TDF_DETAILS))
1255                     fprintf (dump_file, "    nonreadonly global var read\n");
1256                   ref_state = IPA_PURE;
1257                   break;
1258                 case IPA_REF_STORE:
1259                   if (ipa_ref_cannot_lead_to_return (ref))
1260                     break;
1261                   ref_state = IPA_NEITHER;
1262                   if (dump_file && (dump_flags & TDF_DETAILS))
1263                     fprintf (dump_file, "    global var write\n");
1264                   break;
1265                 case IPA_REF_ADDR:
1266                   break;
1267                 }
1268               better_state (&ref_state, &ref_looping,
1269                             w_l->state_previously_known,
1270                             w_l->looping_previously_known);
1271               worse_state (&pure_const_state, &looping,
1272                            ref_state, ref_looping);
1273               if (pure_const_state == IPA_NEITHER)
1274                 break;
1275             }
1276           w_info = (struct ipa_dfs_info *) w->aux;
1277           w = w_info->next_cycle;
1278         }
1279       if (dump_file && (dump_flags & TDF_DETAILS))
1280         fprintf (dump_file, "Result %s looping %i\n",
1281                  pure_const_names [pure_const_state],
1282                  looping);
1283
1284       /* Copy back the region's pure_const_state which is shared by
1285          all nodes in the region.  */
1286       w = node;
1287       while (w)
1288         {
1289           funct_state w_l = get_function_state (w);
1290           enum pure_const_state_e this_state = pure_const_state;
1291           bool this_looping = looping;
1292
1293           if (w_l->state_previously_known != IPA_NEITHER
1294               && this_state > w_l->state_previously_known)
1295             {
1296               this_state = w_l->state_previously_known;
1297               this_looping |= w_l->looping_previously_known;
1298             }
1299           if (!this_looping && self_recursive_p (w))
1300             this_looping = true;
1301           if (!w_l->looping_previously_known)
1302             this_looping = false;
1303
1304           /* All nodes within a cycle share the same info.  */
1305           w_l->pure_const_state = this_state;
1306           w_l->looping = this_looping;
1307
1308           switch (this_state)
1309             {
1310             case IPA_CONST:
1311               if (!TREE_READONLY (w->decl))
1312                 {
1313                   warn_function_const (w->decl, !this_looping);
1314                   if (dump_file)
1315                     fprintf (dump_file, "Function found to be %sconst: %s\n",
1316                              this_looping ? "looping " : "",
1317                              cgraph_node_name (w));
1318                 }
1319               cgraph_set_const_flag (w, true, this_looping);
1320               break;
1321
1322             case IPA_PURE:
1323               if (!DECL_PURE_P (w->decl))
1324                 {
1325                   warn_function_pure (w->decl, !this_looping);
1326                   if (dump_file)
1327                     fprintf (dump_file, "Function found to be %spure: %s\n",
1328                              this_looping ? "looping " : "",
1329                              cgraph_node_name (w));
1330                 }
1331               cgraph_set_pure_flag (w, true, this_looping);
1332               break;
1333
1334             default:
1335               break;
1336             }
1337           w_info = (struct ipa_dfs_info *) w->aux;
1338           w = w_info->next_cycle;
1339         }
1340     }
1341
1342   /* Cleanup. */
1343   for (node = cgraph_nodes; node; node = node->next)
1344     {
1345       /* Get rid of the aux information.  */
1346       if (node->aux)
1347         {
1348           w_info = (struct ipa_dfs_info *) node->aux;
1349           free (node->aux);
1350           node->aux = NULL;
1351         }
1352     }
1353
1354   free (order);
1355 }
1356
1357 /* Produce transitive closure over the callgraph and compute nothrow
1358    attributes.  */
1359
1360 static void
1361 propagate_nothrow (void)
1362 {
1363   struct cgraph_node *node;
1364   struct cgraph_node *w;
1365   struct cgraph_node **order =
1366     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1367   int order_pos;
1368   int i;
1369   struct ipa_dfs_info * w_info;
1370
1371   order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
1372   if (dump_file)
1373     {
1374       dump_cgraph (dump_file);
1375       ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
1376     }
1377
1378   /* Propagate the local information thru the call graph to produce
1379      the global information.  All the nodes within a cycle will have
1380      the same info so we collapse cycles first.  Then we can do the
1381      propagation in one pass from the leaves to the roots.  */
1382   for (i = 0; i < order_pos; i++ )
1383     {
1384       bool can_throw = false;
1385       node = order[i];
1386
1387       /* Find the worst state for any node in the cycle.  */
1388       w = node;
1389       while (w)
1390         {
1391           struct cgraph_edge *e, *ie;
1392           funct_state w_l = get_function_state (w);
1393
1394           if (w_l->can_throw
1395               || cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
1396             can_throw = true;
1397
1398           if (can_throw)
1399             break;
1400
1401           for (e = w->callees; e; e = e->next_callee)
1402             {
1403               struct cgraph_node *y = e->callee;
1404
1405               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1406                 {
1407                   funct_state y_l = get_function_state (y);
1408
1409                   if (can_throw)
1410                     break;
1411                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
1412                       && e->can_throw_external)
1413                     can_throw = true;
1414                 }
1415               else if (e->can_throw_external && !TREE_NOTHROW (y->decl))
1416                 can_throw = true;
1417             }
1418           for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1419             if (ie->can_throw_external)
1420               can_throw = true;
1421           w_info = (struct ipa_dfs_info *) w->aux;
1422           w = w_info->next_cycle;
1423         }
1424
1425       /* Copy back the region's pure_const_state which is shared by
1426          all nodes in the region.  */
1427       w = node;
1428       while (w)
1429         {
1430           funct_state w_l = get_function_state (w);
1431           if (!can_throw && !TREE_NOTHROW (w->decl))
1432             {
1433               struct cgraph_edge *e;
1434               cgraph_set_nothrow_flag (w, true);
1435               for (e = w->callers; e; e = e->next_caller)
1436                 e->can_throw_external = false;
1437               if (dump_file)
1438                 fprintf (dump_file, "Function found to be nothrow: %s\n",
1439                          cgraph_node_name (w));
1440             }
1441           else if (can_throw && !TREE_NOTHROW (w->decl))
1442             w_l->can_throw = true;
1443           w_info = (struct ipa_dfs_info *) w->aux;
1444           w = w_info->next_cycle;
1445         }
1446     }
1447
1448   /* Cleanup. */
1449   for (node = cgraph_nodes; node; node = node->next)
1450     {
1451       /* Get rid of the aux information.  */
1452       if (node->aux)
1453         {
1454           w_info = (struct ipa_dfs_info *) node->aux;
1455           free (node->aux);
1456           node->aux = NULL;
1457         }
1458     }
1459
1460   free (order);
1461 }
1462
1463
1464 /* Produce the global information by preforming a transitive closure
1465    on the local information that was produced by generate_summary.  */
1466
1467 static unsigned int
1468 propagate (void)
1469 {
1470   struct cgraph_node *node;
1471
1472   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1473   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
1474   cgraph_remove_node_removal_hook (node_removal_hook_holder);
1475
1476   /* Nothrow makes more function to not lead to return and improve
1477      later analysis.  */
1478   propagate_nothrow ();
1479   propagate_pure_const ();
1480
1481   /* Cleanup. */
1482   for (node = cgraph_nodes; node; node = node->next)
1483     if (has_function_state (node))
1484       free (get_function_state (node));
1485   VEC_free (funct_state, heap, funct_state_vec);
1486   finish_state ();
1487   return 0;
1488 }
1489
1490 static bool
1491 gate_pure_const (void)
1492 {
1493   return (flag_ipa_pure_const
1494           /* Don't bother doing anything if the program has errors.  */
1495           && !seen_error ());
1496 }
1497
1498 struct ipa_opt_pass_d pass_ipa_pure_const =
1499 {
1500  {
1501   IPA_PASS,
1502   "pure-const",                         /* name */
1503   gate_pure_const,                      /* gate */
1504   propagate,                            /* execute */
1505   NULL,                                 /* sub */
1506   NULL,                                 /* next */
1507   0,                                    /* static_pass_number */
1508   TV_IPA_PURE_CONST,                    /* tv_id */
1509   0,                                    /* properties_required */
1510   0,                                    /* properties_provided */
1511   0,                                    /* properties_destroyed */
1512   0,                                    /* todo_flags_start */
1513   0                                     /* todo_flags_finish */
1514  },
1515  generate_summary,                      /* generate_summary */
1516  pure_const_write_summary,              /* write_summary */
1517  pure_const_read_summary,               /* read_summary */
1518  NULL,                                  /* write_optimization_summary */
1519  NULL,                                  /* read_optimization_summary */
1520  NULL,                                  /* stmt_fixup */
1521  0,                                     /* TODOs */
1522  NULL,                                  /* function_transform */
1523  NULL                                   /* variable_transform */
1524 };
1525
1526 /* Return true if function should be skipped for local pure const analysis.  */
1527
1528 static bool
1529 skip_function_for_local_pure_const (struct cgraph_node *node)
1530 {
1531   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1532      we must not promote functions that are called by already processed functions.  */
1533
1534   if (function_called_by_processed_nodes_p ())
1535     {
1536       if (dump_file)
1537         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
1538       return true;
1539     }
1540   if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
1541     {
1542       if (dump_file)
1543         fprintf (dump_file, "Function is not available or overwritable; not analyzing.\n");
1544       return true;
1545     }
1546   return false;
1547 }
1548
1549 /* Simple local pass for pure const discovery reusing the analysis from
1550    ipa_pure_const.   This pass is effective when executed together with
1551    other optimization passes in early optimization pass queue.  */
1552
1553 static unsigned int
1554 local_pure_const (void)
1555 {
1556   bool changed = false;
1557   funct_state l;
1558   bool skip;
1559   struct cgraph_node *node;
1560
1561   node = cgraph_get_node (current_function_decl);
1562   skip = skip_function_for_local_pure_const (node);
1563   if (!warn_suggest_attribute_const
1564       && !warn_suggest_attribute_pure
1565       && skip)
1566     return 0;
1567
1568   l = analyze_function (node, false);
1569
1570   /* Do NORETURN discovery.  */
1571   if (!skip && !TREE_THIS_VOLATILE (current_function_decl)
1572       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
1573     {
1574       warn_function_noreturn (cfun->decl);
1575       if (dump_file)
1576         fprintf (dump_file, "Function found to be noreturn: %s\n",
1577                  lang_hooks.decl_printable_name (current_function_decl, 2));
1578
1579       /* Update declaration and reduce profile to executed once.  */
1580       TREE_THIS_VOLATILE (current_function_decl) = 1;
1581       if (node->frequency > NODE_FREQUENCY_EXECUTED_ONCE)
1582         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
1583
1584       changed = true;
1585     }
1586
1587   switch (l->pure_const_state)
1588     {
1589     case IPA_CONST:
1590       if (!TREE_READONLY (current_function_decl))
1591         {
1592           warn_function_const (current_function_decl, !l->looping);
1593           if (!skip)
1594             {
1595               cgraph_set_const_flag (node, true, l->looping);
1596               changed = true;
1597             }
1598           if (dump_file)
1599             fprintf (dump_file, "Function found to be %sconst: %s\n",
1600                      l->looping ? "looping " : "",
1601                      lang_hooks.decl_printable_name (current_function_decl,
1602                                                      2));
1603         }
1604       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1605                && !l->looping)
1606         {
1607           if (!skip)
1608             {
1609               cgraph_set_const_flag (node, true, false);
1610               changed = true;
1611             }
1612           if (dump_file)
1613             fprintf (dump_file, "Function found to be non-looping: %s\n",
1614                      lang_hooks.decl_printable_name (current_function_decl,
1615                                                      2));
1616         }
1617       break;
1618
1619     case IPA_PURE:
1620       if (!DECL_PURE_P (current_function_decl))
1621         {
1622           if (!skip)
1623             {
1624               cgraph_set_pure_flag (node, true, l->looping);
1625               changed = true;
1626             }
1627           warn_function_pure (current_function_decl, !l->looping);
1628           if (dump_file)
1629             fprintf (dump_file, "Function found to be %spure: %s\n",
1630                      l->looping ? "looping " : "",
1631                      lang_hooks.decl_printable_name (current_function_decl,
1632                                                      2));
1633         }
1634       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1635                && !l->looping)
1636         {
1637           if (!skip)
1638             {
1639               cgraph_set_pure_flag (node, true, false);
1640               changed = true;
1641             }
1642           if (dump_file)
1643             fprintf (dump_file, "Function found to be non-looping: %s\n",
1644                      lang_hooks.decl_printable_name (current_function_decl,
1645                                                      2));
1646         }
1647       break;
1648
1649     default:
1650       break;
1651     }
1652   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1653     {
1654       struct cgraph_edge *e;
1655
1656       cgraph_set_nothrow_flag (node, true);
1657       for (e = node->callers; e; e = e->next_caller)
1658         e->can_throw_external = false;
1659       changed = true;
1660       if (dump_file)
1661         fprintf (dump_file, "Function found to be nothrow: %s\n",
1662                  lang_hooks.decl_printable_name (current_function_decl,
1663                                                  2));
1664     }
1665   free (l);
1666   if (changed)
1667     return execute_fixup_cfg ();
1668   else
1669     return 0;
1670 }
1671
1672 struct gimple_opt_pass pass_local_pure_const =
1673 {
1674  {
1675   GIMPLE_PASS,
1676   "local-pure-const",                   /* name */
1677   gate_pure_const,                      /* gate */
1678   local_pure_const,                     /* execute */
1679   NULL,                                 /* sub */
1680   NULL,                                 /* next */
1681   0,                                    /* static_pass_number */
1682   TV_IPA_PURE_CONST,                    /* tv_id */
1683   0,                                    /* properties_required */
1684   0,                                    /* properties_provided */
1685   0,                                    /* properties_destroyed */
1686   0,                                    /* todo_flags_start */
1687   0                                     /* todo_flags_finish */
1688  }
1689 };