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