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