gcc/ipa-pure-const.c

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