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