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