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