gcc/ipa-pure-const.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004-2016 Free Software Foundation, Inc.
   3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file marks functions as being either const (TREE_READONLY) or
  22    pure (DECL_PURE_P).  It can also set a variant of these that
  23    are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
  24
  25    This must be run after inlining decisions have been made since
  26    otherwise, the local sets will not contain information that is
  27    consistent with post inlined state.  The global sets are not prone
  28    to this problem since they are by definition transitive.  */
  29
  30 /* The code in this module is called by the ipa pass manager. It
  31    should be one of the later passes since it's information is used by
  32    the rest of the compilation. */
  33
  34 #include "config.h"
  35 #include "system.h"
  36 #include "coretypes.h"
  37 #include "backend.h"
  38 #include "target.h"
  39 #include "tree.h"
  40 #include "gimple.h"
  41 #include "tree-pass.h"
  42 #include "tree-streamer.h"
  43 #include "cgraph.h"
  44 #include "diagnostic.h"
  45 #include "calls.h"
  46 #include "cfganal.h"
  47 #include "tree-eh.h"
  48 #include "gimple-iterator.h"
  49 #include "gimple-walk.h"
  50 #include "tree-cfg.h"
  51 #include "tree-ssa-loop-niter.h"
  52 #include "langhooks.h"
  53 #include "ipa-utils.h"
  54 #include "gimple-pretty-print.h"
  55 #include "cfgloop.h"
  56 #include "tree-scalar-evolution.h"
  57 #include "intl.h"
  58 #include "opts.h"
  59
  60 /* Lattice values for const and pure functions.  Everything starts out
  61    being const, then may drop to pure and then neither depending on
  62    what is found.  */
  63 enum pure_const_state_e
  64 {
  65   IPA_CONST,
  66   IPA_PURE,
  67   IPA_NEITHER
  68 };
  69
  70 const char *pure_const_names[3] = {"const", "pure", "neither"};
  71
  72 /* Holder for the const_state.  There is one of these per function
  73    decl.  */
  74 struct funct_state_d
  75 {
  76   /* See above.  */
  77   enum pure_const_state_e pure_const_state;
  78   /* What user set here; we can be always sure about this.  */
  79   enum pure_const_state_e state_previously_known;
  80   bool looping_previously_known;
  81
  82   /* True if the function could possibly infinite loop.  There are a
  83      lot of ways that this could be determined.  We are pretty
  84      conservative here.  While it is possible to cse pure and const
  85      calls, it is not legal to have dce get rid of the call if there
  86      is a possibility that the call could infinite loop since this is
  87      a behavioral change.  */
  88   bool looping;
  89
  90   bool can_throw;
  91
  92   /* If function can call free, munmap or otherwise make previously
  93      non-trapping memory accesses trapping.  */
  94   bool can_free;
  95 };
  96
  97 /* State used when we know nothing about function.  */
  98 static struct funct_state_d varying_state
  99    = { IPA_NEITHER, IPA_NEITHER, true, true, true, true };
 100
 101
 102 typedef struct funct_state_d * funct_state;
 103
 104 /* The storage of the funct_state is abstracted because there is the
 105    possibility that it may be desirable to move this to the cgraph
 106    local info.  */
 107
 108 /* Array, indexed by cgraph node uid, of function states.  */
 109
 110 static vec<funct_state> funct_state_vec;
 111
 112 static bool gate_pure_const (void);
 113
 114 namespace {
 115
 116 const pass_data pass_data_ipa_pure_const =
 117 {
 118   IPA_PASS, /* type */
 119   "pure-const", /* name */
 120   OPTGROUP_NONE, /* optinfo_flags */
 121   TV_IPA_PURE_CONST, /* tv_id */
 122   0, /* properties_required */
 123   0, /* properties_provided */
 124   0, /* properties_destroyed */
 125   0, /* todo_flags_start */
 126   0, /* todo_flags_finish */
 127 };
 128
 129 class pass_ipa_pure_const : public ipa_opt_pass_d
 130 {
 131 public:
 132   pass_ipa_pure_const(gcc::context *ctxt);
 133
 134   /* opt_pass methods: */
 135   bool gate (function *) { return gate_pure_const (); }
 136   unsigned int execute (function *fun);
 137
 138   void register_hooks (void);
 139
 140 private:
 141   bool init_p;
 142
 143   /* Holders of ipa cgraph hooks: */
 144   struct cgraph_node_hook_list *function_insertion_hook_holder;
 145   struct cgraph_2node_hook_list *node_duplication_hook_holder;
 146   struct cgraph_node_hook_list *node_removal_hook_holder;
 147
 148 }; // class pass_ipa_pure_const
 149
 150 } // anon namespace
 151
 152 /* Try to guess if function body will always be visible to compiler
 153    when compiling the call and whether compiler will be able
 154    to propagate the information by itself.  */
 155
 156 static bool
 157 function_always_visible_to_compiler_p (tree decl)
 158 {
 159   return (!TREE_PUBLIC (decl) || DECL_DECLARED_INLINE_P (decl));
 160 }
 161
 162 /* Emit suggestion about attribute ATTRIB_NAME for DECL.  KNOWN_FINITE
 163    is true if the function is known to be finite.  The diagnostic is
 164    controlled by OPTION.  WARNED_ABOUT is a hash_set<tree> unique for
 165    OPTION, this function may initialize it and it is always returned
 166    by the function.  */
 167
 168 static hash_set<tree> *
 169 suggest_attribute (int option, tree decl, bool known_finite,
 170                    hash_set<tree> *warned_about,
 171                    const char * attrib_name)
 172 {
 173   if (!option_enabled (option, &global_options))
 174     return warned_about;
 175   if (TREE_THIS_VOLATILE (decl)
 176       || (known_finite && function_always_visible_to_compiler_p (decl)))
 177     return warned_about;
 178
 179   if (!warned_about)
 180     warned_about = new hash_set<tree>;
 181   if (warned_about->contains (decl))
 182     return warned_about;
 183   warned_about->add (decl);
 184   warning_at (DECL_SOURCE_LOCATION (decl),
 185               option,
 186               known_finite
 187               ? _("function might be candidate for attribute %<%s%>")
 188               : _("function might be candidate for attribute %<%s%>"
 189                   " if it is known to return normally"), attrib_name);
 190   return warned_about;
 191 }
 192
 193 /* Emit suggestion about __attribute_((pure)) for DECL.  KNOWN_FINITE
 194    is true if the function is known to be finite.  */
 195
 196 static void
 197 warn_function_pure (tree decl, bool known_finite)
 198 {
 199   static hash_set<tree> *warned_about;
 200
 201   warned_about
 202     = suggest_attribute (OPT_Wsuggest_attribute_pure, decl,
 203                          known_finite, warned_about, "pure");
 204 }
 205
 206 /* Emit suggestion about __attribute_((const)) for DECL.  KNOWN_FINITE
 207    is true if the function is known to be finite.  */
 208
 209 static void
 210 warn_function_const (tree decl, bool known_finite)
 211 {
 212   static hash_set<tree> *warned_about;
 213   warned_about
 214     = suggest_attribute (OPT_Wsuggest_attribute_const, decl,
 215                          known_finite, warned_about, "const");
 216 }
 217
 218 static void
 219 warn_function_noreturn (tree decl)
 220 {
 221   static hash_set<tree> *warned_about;
 222   if (!lang_hooks.missing_noreturn_ok_p (decl)
 223       && targetm.warn_func_return (decl))
 224     warned_about
 225       = suggest_attribute (OPT_Wsuggest_attribute_noreturn, decl,
 226                            true, warned_about, "noreturn");
 227 }
 228
 229 /* Return true if we have a function state for NODE.  */
 230
 231 static inline bool
 232 has_function_state (struct cgraph_node *node)
 233 {
 234   if (!funct_state_vec.exists ()
 235       || funct_state_vec.length () <= (unsigned int)node->uid)
 236     return false;
 237   return funct_state_vec[node->uid] != NULL;
 238 }
 239
 240 /* Return the function state from NODE.  */
 241
 242 static inline funct_state
 243 get_function_state (struct cgraph_node *node)
 244 {
 245   if (!funct_state_vec.exists ()
 246       || funct_state_vec.length () <= (unsigned int)node->uid
 247       || !funct_state_vec[node->uid])
 248     /* We might want to put correct previously_known state into varying.  */
 249     return &varying_state;
 250  return funct_state_vec[node->uid];
 251 }
 252
 253 /* Set the function state S for NODE.  */
 254
 255 static inline void
 256 set_function_state (struct cgraph_node *node, funct_state s)
 257 {
 258   if (!funct_state_vec.exists ()
 259       || funct_state_vec.length () <= (unsigned int)node->uid)
 260      funct_state_vec.safe_grow_cleared (node->uid + 1);
 261   funct_state_vec[node->uid] = s;
 262 }
 263
 264 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 265    variable T is legal in a function that is either pure or const.  */
 266
 267 static inline void
 268 check_decl (funct_state local,
 269             tree t, bool checking_write, bool ipa)
 270 {
 271   /* Do not want to do anything with volatile except mark any
 272      function that uses one to be not const or pure.  */
 273   if (TREE_THIS_VOLATILE (t))
 274     {
 275       local->pure_const_state = IPA_NEITHER;
 276       if (dump_file)
 277         fprintf (dump_file, "    Volatile operand is not const/pure");
 278       return;
 279     }
 280
 281   /* Do not care about a local automatic that is not static.  */
 282   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 283     return;
 284
 285   /* If the variable has the "used" attribute, treat it as if it had a
 286      been touched by the devil.  */
 287   if (DECL_PRESERVE_P (t))
 288     {
 289       local->pure_const_state = IPA_NEITHER;
 290       if (dump_file)
 291         fprintf (dump_file, "    Used static/global variable is not const/pure\n");
 292       return;
 293     }
 294
 295   /* In IPA mode we are not interested in checking actual loads and stores;
 296      they will be processed at propagation time using ipa_ref.  */
 297   if (ipa)
 298     return;
 299
 300   /* Since we have dealt with the locals and params cases above, if we
 301      are CHECKING_WRITE, this cannot be a pure or constant
 302      function.  */
 303   if (checking_write)
 304     {
 305       local->pure_const_state = IPA_NEITHER;
 306       if (dump_file)
 307         fprintf (dump_file, "    static/global memory write is not const/pure\n");
 308       return;
 309     }
 310
 311   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 312     {
 313       /* Readonly reads are safe.  */
 314       if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
 315         return; /* Read of a constant, do not change the function state.  */
 316       else
 317         {
 318           if (dump_file)
 319             fprintf (dump_file, "    global memory read is not const\n");
 320           /* Just a regular read.  */
 321           if (local->pure_const_state == IPA_CONST)
 322             local->pure_const_state = IPA_PURE;
 323         }
 324     }
 325   else
 326     {
 327       /* Compilation level statics can be read if they are readonly
 328          variables.  */
 329       if (TREE_READONLY (t))
 330         return;
 331
 332       if (dump_file)
 333         fprintf (dump_file, "    static memory read is not const\n");
 334       /* Just a regular read.  */
 335       if (local->pure_const_state == IPA_CONST)
 336         local->pure_const_state = IPA_PURE;
 337     }
 338 }
 339
 340
 341 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 342    variable T is legal in a function that is either pure or const.  */
 343
 344 static inline void
 345 check_op (funct_state local, tree t, bool checking_write)
 346 {
 347   t = get_base_address (t);
 348   if (t && TREE_THIS_VOLATILE (t))
 349     {
 350       local->pure_const_state = IPA_NEITHER;
 351       if (dump_file)
 352         fprintf (dump_file, "    Volatile indirect ref is not const/pure\n");
 353       return;
 354     }
 355   else if (t
 356            && (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF)
 357            && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 358            && !ptr_deref_may_alias_global_p (TREE_OPERAND (t, 0)))
 359     {
 360       if (dump_file)
 361         fprintf (dump_file, "    Indirect ref to local memory is OK\n");
 362       return;
 363     }
 364   else if (checking_write)
 365     {
 366       local->pure_const_state = IPA_NEITHER;
 367       if (dump_file)
 368         fprintf (dump_file, "    Indirect ref write is not const/pure\n");
 369       return;
 370     }
 371   else
 372     {
 373       if (dump_file)
 374         fprintf (dump_file, "    Indirect ref read is not const\n");
 375       if (local->pure_const_state == IPA_CONST)
 376         local->pure_const_state = IPA_PURE;
 377     }
 378 }
 379
 380 /* compute state based on ECF FLAGS and store to STATE and LOOPING.  */
 381
 382 static void
 383 state_from_flags (enum pure_const_state_e *state, bool *looping,
 384                   int flags, bool cannot_lead_to_return)
 385 {
 386   *looping = false;
 387   if (flags & ECF_LOOPING_CONST_OR_PURE)
 388     {
 389       *looping = true;
 390       if (dump_file && (dump_flags & TDF_DETAILS))
 391         fprintf (dump_file, " looping");
 392     }
 393   if (flags & ECF_CONST)
 394     {
 395       *state = IPA_CONST;
 396       if (dump_file && (dump_flags & TDF_DETAILS))
 397         fprintf (dump_file, " const\n");
 398     }
 399   else if (flags & ECF_PURE)
 400     {
 401       *state = IPA_PURE;
 402       if (dump_file && (dump_flags & TDF_DETAILS))
 403         fprintf (dump_file, " pure\n");
 404     }
 405   else if (cannot_lead_to_return)
 406     {
 407       *state = IPA_PURE;
 408       *looping = true;
 409       if (dump_file && (dump_flags & TDF_DETAILS))
 410         fprintf (dump_file, " ignoring side effects->pure looping\n");
 411     }
 412   else
 413     {
 414       if (dump_file && (dump_flags & TDF_DETAILS))
 415         fprintf (dump_file, " neither\n");
 416       *state = IPA_NEITHER;
 417       *looping = true;
 418     }
 419 }
 420
 421 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
 422    into STATE and LOOPING better of the two variants.
 423    Be sure to merge looping correctly.  IPA_NEITHER functions
 424    have looping 0 even if they don't have to return.  */
 425
 426 static inline void
 427 better_state (enum pure_const_state_e *state, bool *looping,
 428               enum pure_const_state_e state2, bool looping2)
 429 {
 430   if (state2 < *state)
 431     {
 432       if (*state == IPA_NEITHER)
 433         *looping = looping2;
 434       else
 435         *looping = MIN (*looping, looping2);
 436       *state = state2;
 437     }
 438   else if (state2 != IPA_NEITHER)
 439     *looping = MIN (*looping, looping2);
 440 }
 441
 442 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
 443    into STATE and LOOPING worse of the two variants.  */
 444
 445 static inline void
 446 worse_state (enum pure_const_state_e *state, bool *looping,
 447              enum pure_const_state_e state2, bool looping2)
 448 {
 449   *state = MAX (*state, state2);
 450   *looping = MAX (*looping, looping2);
 451 }
 452
 453 /* Recognize special cases of builtins that are by themselves not pure or const
 454    but function using them is.  */
 455 static bool
 456 special_builtin_state (enum pure_const_state_e *state, bool *looping,
 457                         tree callee)
 458 {
 459   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
 460     switch (DECL_FUNCTION_CODE (callee))
 461       {
 462         case BUILT_IN_RETURN:
 463         case BUILT_IN_UNREACHABLE:
 464         case BUILT_IN_ALLOCA:
 465         case BUILT_IN_ALLOCA_WITH_ALIGN:
 466         case BUILT_IN_STACK_SAVE:
 467         case BUILT_IN_STACK_RESTORE:
 468         case BUILT_IN_EH_POINTER:
 469         case BUILT_IN_EH_FILTER:
 470         case BUILT_IN_UNWIND_RESUME:
 471         case BUILT_IN_CXA_END_CLEANUP:
 472         case BUILT_IN_EH_COPY_VALUES:
 473         case BUILT_IN_FRAME_ADDRESS:
 474         case BUILT_IN_APPLY:
 475         case BUILT_IN_APPLY_ARGS:
 476           *looping = false;
 477           *state = IPA_CONST;
 478           return true;
 479         case BUILT_IN_PREFETCH:
 480           *looping = true;
 481           *state = IPA_CONST;
 482           return true;
 483         default:
 484           break;
 485       }
 486   return false;
 487 }
 488
 489 /* Check the parameters of a function call to CALL_EXPR to see if
 490    there are any references in the parameters that are not allowed for
 491    pure or const functions.  Also check to see if this is either an
 492    indirect call, a call outside the compilation unit, or has special
 493    attributes that may also effect the purity.  The CALL_EXPR node for
 494    the entire call expression.  */
 495
 496 static void
 497 check_call (funct_state local, gcall *call, bool ipa)
 498 {
 499   int flags = gimple_call_flags (call);
 500   tree callee_t = gimple_call_fndecl (call);
 501   bool possibly_throws = stmt_could_throw_p (call);
 502   bool possibly_throws_externally = (possibly_throws
 503                                      && stmt_can_throw_external (call));
 504
 505   if (possibly_throws)
 506     {
 507       unsigned int i;
 508       for (i = 0; i < gimple_num_ops (call); i++)
 509         if (gimple_op (call, i)
 510             && tree_could_throw_p (gimple_op (call, i)))
 511           {
 512             if (possibly_throws && cfun->can_throw_non_call_exceptions)
 513               {
 514                 if (dump_file)
 515                   fprintf (dump_file, "    operand can throw; looping\n");
 516                 local->looping = true;
 517               }
 518             if (possibly_throws_externally)
 519               {
 520                 if (dump_file)
 521                   fprintf (dump_file, "    operand can throw externally\n");
 522                 local->can_throw = true;
 523               }
 524           }
 525     }
 526
 527   /* The const and pure flags are set by a variety of places in the
 528      compiler (including here).  If someone has already set the flags
 529      for the callee, (such as for some of the builtins) we will use
 530      them, otherwise we will compute our own information.
 531
 532      Const and pure functions have less clobber effects than other
 533      functions so we process these first.  Otherwise if it is a call
 534      outside the compilation unit or an indirect call we punt.  This
 535      leaves local calls which will be processed by following the call
 536      graph.  */
 537   if (callee_t)
 538     {
 539       enum pure_const_state_e call_state;
 540       bool call_looping;
 541
 542       if (gimple_call_builtin_p (call, BUILT_IN_NORMAL)
 543           && !nonfreeing_call_p (call))
 544         local->can_free = true;
 545
 546       if (special_builtin_state (&call_state, &call_looping, callee_t))
 547         {
 548           worse_state (&local->pure_const_state, &local->looping,
 549                        call_state, call_looping);
 550           return;
 551         }
 552       /* When bad things happen to bad functions, they cannot be const
 553          or pure.  */
 554       if (setjmp_call_p (callee_t))
 555         {
 556           if (dump_file)
 557             fprintf (dump_file, "    setjmp is not const/pure\n");
 558           local->looping = true;
 559           local->pure_const_state = IPA_NEITHER;
 560         }
 561
 562       if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
 563         switch (DECL_FUNCTION_CODE (callee_t))
 564           {
 565           case BUILT_IN_LONGJMP:
 566           case BUILT_IN_NONLOCAL_GOTO:
 567             if (dump_file)
 568               fprintf (dump_file, "    longjmp and nonlocal goto is not const/pure\n");
 569             local->pure_const_state = IPA_NEITHER;
 570             local->looping = true;
 571             break;
 572           default:
 573             break;
 574           }
 575     }
 576   else if (gimple_call_internal_p (call) && !nonfreeing_call_p (call))
 577     local->can_free = true;
 578
 579   /* When not in IPA mode, we can still handle self recursion.  */
 580   if (!ipa && callee_t
 581       && recursive_call_p (current_function_decl, callee_t))
 582     {
 583       if (dump_file)
 584         fprintf (dump_file, "    Recursive call can loop.\n");
 585       local->looping = true;
 586     }
 587   /* Either callee is unknown or we are doing local analysis.
 588      Look to see if there are any bits available for the callee (such as by
 589      declaration or because it is builtin) and process solely on the basis of
 590      those bits. */
 591   else if (!ipa)
 592     {
 593       enum pure_const_state_e call_state;
 594       bool call_looping;
 595       if (possibly_throws && cfun->can_throw_non_call_exceptions)
 596         {
 597           if (dump_file)
 598             fprintf (dump_file, "    can throw; looping\n");
 599           local->looping = true;
 600         }
 601       if (possibly_throws_externally)
 602         {
 603           if (dump_file)
 604             {
 605               fprintf (dump_file, "    can throw externally to lp %i\n",
 606                        lookup_stmt_eh_lp (call));
 607               if (callee_t)
 608                 fprintf (dump_file, "     callee:%s\n",
 609                          IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t)));
 610             }
 611           local->can_throw = true;
 612         }
 613       if (dump_file && (dump_flags & TDF_DETAILS))
 614         fprintf (dump_file, "    checking flags for call:");
 615       state_from_flags (&call_state, &call_looping, flags,
 616                         ((flags & (ECF_NORETURN | ECF_NOTHROW))
 617                          == (ECF_NORETURN | ECF_NOTHROW))
 618                         || (!flag_exceptions && (flags & ECF_NORETURN)));
 619       worse_state (&local->pure_const_state, &local->looping,
 620                    call_state, call_looping);
 621     }
 622   /* Direct functions calls are handled by IPA propagation.  */
 623 }
 624
 625 /* Wrapper around check_decl for loads in local more.  */
 626
 627 static bool
 628 check_load (gimple *, tree op, tree, void *data)
 629 {
 630   if (DECL_P (op))
 631     check_decl ((funct_state)data, op, false, false);
 632   else
 633     check_op ((funct_state)data, op, false);
 634   return false;
 635 }
 636
 637 /* Wrapper around check_decl for stores in local more.  */
 638
 639 static bool
 640 check_store (gimple *, tree op, tree, void *data)
 641 {
 642   if (DECL_P (op))
 643     check_decl ((funct_state)data, op, true, false);
 644   else
 645     check_op ((funct_state)data, op, true);
 646   return false;
 647 }
 648
 649 /* Wrapper around check_decl for loads in ipa mode.  */
 650
 651 static bool
 652 check_ipa_load (gimple *, tree op, tree, void *data)
 653 {
 654   if (DECL_P (op))
 655     check_decl ((funct_state)data, op, false, true);
 656   else
 657     check_op ((funct_state)data, op, false);
 658   return false;
 659 }
 660
 661 /* Wrapper around check_decl for stores in ipa mode.  */
 662
 663 static bool
 664 check_ipa_store (gimple *, tree op, tree, void *data)
 665 {
 666   if (DECL_P (op))
 667     check_decl ((funct_state)data, op, true, true);
 668   else
 669     check_op ((funct_state)data, op, true);
 670   return false;
 671 }
 672
 673 /* Look into pointer pointed to by GSIP and figure out what interesting side
 674    effects it has.  */
 675 static void
 676 check_stmt (gimple_stmt_iterator *gsip, funct_state local, bool ipa)
 677 {
 678   gimple *stmt = gsi_stmt (*gsip);
 679
 680   if (is_gimple_debug (stmt))
 681     return;
 682
 683   /* Do consider clobber as side effects before IPA, so we rather inline
 684      C++ destructors and keep clobber semantics than eliminate them.
 685
 686      TODO: We may get smarter during early optimizations on these and let
 687      functions containing only clobbers to be optimized more.  This is a common
 688      case of C++ destructors.  */
 689
 690   if ((ipa || cfun->after_inlining) && gimple_clobber_p (stmt))
 691     return;
 692
 693   if (dump_file)
 694     {
 695       fprintf (dump_file, "  scanning: ");
 696       print_gimple_stmt (dump_file, stmt, 0, 0);
 697     }
 698
 699   if (gimple_has_volatile_ops (stmt)
 700       && !gimple_clobber_p (stmt))
 701     {
 702       local->pure_const_state = IPA_NEITHER;
 703       if (dump_file)
 704         fprintf (dump_file, "    Volatile stmt is not const/pure\n");
 705     }
 706
 707   /* Look for loads and stores.  */
 708   walk_stmt_load_store_ops (stmt, local,
 709                             ipa ? check_ipa_load : check_load,
 710                             ipa ? check_ipa_store :  check_store);
 711
 712   if (gimple_code (stmt) != GIMPLE_CALL
 713       && stmt_could_throw_p (stmt))
 714     {
 715       if (cfun->can_throw_non_call_exceptions)
 716         {
 717           if (dump_file)
 718             fprintf (dump_file, "    can throw; looping\n");
 719           local->looping = true;
 720         }
 721       if (stmt_can_throw_external (stmt))
 722         {
 723           if (dump_file)
 724             fprintf (dump_file, "    can throw externally\n");
 725           local->can_throw = true;
 726         }
 727       else
 728         if (dump_file)
 729           fprintf (dump_file, "    can throw\n");
 730     }
 731   switch (gimple_code (stmt))
 732     {
 733     case GIMPLE_CALL:
 734       check_call (local, as_a <gcall *> (stmt), ipa);
 735       break;
 736     case GIMPLE_LABEL:
 737       if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt))))
 738         /* Target of long jump. */
 739         {
 740           if (dump_file)
 741             fprintf (dump_file, "    nonlocal label is not const/pure\n");
 742           local->pure_const_state = IPA_NEITHER;
 743         }
 744       break;
 745     case GIMPLE_ASM:
 746       if (gimple_asm_clobbers_memory_p (as_a <gasm *> (stmt)))
 747         {
 748           if (dump_file)
 749             fprintf (dump_file, "    memory asm clobber is not const/pure\n");
 750           /* Abandon all hope, ye who enter here. */
 751           local->pure_const_state = IPA_NEITHER;
 752           local->can_free = true;
 753         }
 754       if (gimple_asm_volatile_p (as_a <gasm *> (stmt)))
 755         {
 756           if (dump_file)
 757             fprintf (dump_file, "    volatile is not const/pure\n");
 758           /* Abandon all hope, ye who enter here. */
 759           local->pure_const_state = IPA_NEITHER;
 760           local->looping = true;
 761           local->can_free = true;
 762         }
 763       return;
 764     default:
 765       break;
 766     }
 767 }
 768
 769
 770 /* This is the main routine for finding the reference patterns for
 771    global variables within a function FN.  */
 772
 773 static funct_state
 774 analyze_function (struct cgraph_node *fn, bool ipa)
 775 {
 776   tree decl = fn->decl;
 777   funct_state l;
 778   basic_block this_block;
 779
 780   l = XCNEW (struct funct_state_d);
 781   l->pure_const_state = IPA_CONST;
 782   l->state_previously_known = IPA_NEITHER;
 783   l->looping_previously_known = true;
 784   l->looping = false;
 785   l->can_throw = false;
 786   l->can_free = false;
 787   state_from_flags (&l->state_previously_known, &l->looping_previously_known,
 788                     flags_from_decl_or_type (fn->decl),
 789                     fn->cannot_return_p ());
 790
 791   if (fn->thunk.thunk_p || fn->alias)
 792     {
 793       /* Thunk gets propagated through, so nothing interesting happens.  */
 794       gcc_assert (ipa);
 795       if (fn->thunk.thunk_p && fn->thunk.virtual_offset_p)
 796         l->pure_const_state = IPA_NEITHER;
 797       return l;
 798     }
 799
 800   if (dump_file)
 801     {
 802       fprintf (dump_file, "\n\n local analysis of %s\n ",
 803                fn->name ());
 804     }
 805
 806   push_cfun (DECL_STRUCT_FUNCTION (decl));
 807
 808   FOR_EACH_BB_FN (this_block, cfun)
 809     {
 810       gimple_stmt_iterator gsi;
 811       struct walk_stmt_info wi;
 812
 813       memset (&wi, 0, sizeof (wi));
 814       for (gsi = gsi_start_bb (this_block);
 815            !gsi_end_p (gsi);
 816            gsi_next (&gsi))
 817         {
 818           check_stmt (&gsi, l, ipa);
 819           if (l->pure_const_state == IPA_NEITHER
 820               && l->looping
 821               && l->can_throw
 822               && l->can_free)
 823             goto end;
 824         }
 825     }
 826
 827 end:
 828   if (l->pure_const_state != IPA_NEITHER)
 829     {
 830       /* Const functions cannot have back edges (an
 831          indication of possible infinite loop side
 832          effect.  */
 833       if (mark_dfs_back_edges ())
 834         {
 835           /* Preheaders are needed for SCEV to work.
 836              Simple latches and recorded exits improve chances that loop will
 837              proved to be finite in testcases such as in loop-15.c
 838              and loop-24.c  */
 839           loop_optimizer_init (LOOPS_HAVE_PREHEADERS
 840                                | LOOPS_HAVE_SIMPLE_LATCHES
 841                                | LOOPS_HAVE_RECORDED_EXITS);
 842           if (dump_file && (dump_flags & TDF_DETAILS))
 843             flow_loops_dump (dump_file, NULL, 0);
 844           if (mark_irreducible_loops ())
 845             {
 846               if (dump_file)
 847                 fprintf (dump_file, "    has irreducible loops\n");
 848               l->looping = true;
 849             }
 850           else
 851             {
 852               struct loop *loop;
 853               scev_initialize ();
 854               FOR_EACH_LOOP (loop, 0)
 855                 if (!finite_loop_p (loop))
 856                   {
 857                     if (dump_file)
 858                       fprintf (dump_file, "    can not prove finiteness of "
 859                                "loop %i\n", loop->num);
 860                     l->looping =true;
 861                     break;
 862                   }
 863               scev_finalize ();
 864             }
 865           loop_optimizer_finalize ();
 866         }
 867     }
 868
 869   if (dump_file && (dump_flags & TDF_DETAILS))
 870     fprintf (dump_file, "    checking previously known:");
 871
 872   better_state (&l->pure_const_state, &l->looping,
 873                 l->state_previously_known,
 874                 l->looping_previously_known);
 875   if (TREE_NOTHROW (decl))
 876     l->can_throw = false;
 877
 878   pop_cfun ();
 879   if (dump_file)
 880     {
 881       if (l->looping)
 882         fprintf (dump_file, "Function is locally looping.\n");
 883       if (l->can_throw)
 884         fprintf (dump_file, "Function is locally throwing.\n");
 885       if (l->pure_const_state == IPA_CONST)
 886         fprintf (dump_file, "Function is locally const.\n");
 887       if (l->pure_const_state == IPA_PURE)
 888         fprintf (dump_file, "Function is locally pure.\n");
 889       if (l->can_free)
 890         fprintf (dump_file, "Function can locally free.\n");
 891     }
 892   return l;
 893 }
 894
 895 /* Called when new function is inserted to callgraph late.  */
 896 static void
 897 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 898 {
 899  if (node->get_availability () < AVAIL_INTERPOSABLE)
 900    return;
 901   /* There are some shared nodes, in particular the initializers on
 902      static declarations.  We do not need to scan them more than once
 903      since all we would be interested in are the addressof
 904      operations.  */
 905   if (node->get_availability () > AVAIL_INTERPOSABLE
 906       && opt_for_fn (node->decl, flag_ipa_pure_const))
 907     set_function_state (node, analyze_function (node, true));
 908 }
 909
 910 /* Called when new clone is inserted to callgraph late.  */
 911
 912 static void
 913 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 914                      void *data ATTRIBUTE_UNUSED)
 915 {
 916   if (has_function_state (src))
 917     {
 918       funct_state l = XNEW (struct funct_state_d);
 919       gcc_assert (!has_function_state (dst));
 920       memcpy (l, get_function_state (src), sizeof (*l));
 921       set_function_state (dst, l);
 922     }
 923 }
 924
 925 /* Called when new clone is inserted to callgraph late.  */
 926
 927 static void
 928 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 929 {
 930   if (has_function_state (node))
 931     {
 932       funct_state l = get_function_state (node);
 933       if (l != &varying_state)
 934         free (l);
 935       set_function_state (node, NULL);
 936     }
 937 }
 938
 939 \f
 940 void
 941 pass_ipa_pure_const::
 942 register_hooks (void)
 943 {
 944   if (init_p)
 945     return;
 946
 947   init_p = true;
 948
 949   node_removal_hook_holder =
 950       symtab->add_cgraph_removal_hook (&remove_node_data, NULL);
 951   node_duplication_hook_holder =
 952       symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL);
 953   function_insertion_hook_holder =
 954       symtab->add_cgraph_insertion_hook (&add_new_function, NULL);
 955 }
 956
 957
 958 /* Analyze each function in the cgraph to see if it is locally PURE or
 959    CONST.  */
 960
 961 static void
 962 pure_const_generate_summary (void)
 963 {
 964   struct cgraph_node *node;
 965
 966   pass_ipa_pure_const *pass = static_cast <pass_ipa_pure_const *> (current_pass);
 967   pass->register_hooks ();
 968
 969   /* Process all of the functions.
 970
 971      We process AVAIL_INTERPOSABLE functions.  We can not use the results
 972      by default, but the info can be used at LTO with -fwhole-program or
 973      when function got cloned and the clone is AVAILABLE.  */
 974
 975   FOR_EACH_DEFINED_FUNCTION (node)
 976     if (node->get_availability () >= AVAIL_INTERPOSABLE
 977         && opt_for_fn (node->decl, flag_ipa_pure_const))
 978       set_function_state (node, analyze_function (node, true));
 979 }
 980
 981
 982 /* Serialize the ipa info for lto.  */
 983
 984 static void
 985 pure_const_write_summary (void)
 986 {
 987   struct cgraph_node *node;
 988   struct lto_simple_output_block *ob
 989     = lto_create_simple_output_block (LTO_section_ipa_pure_const);
 990   unsigned int count = 0;
 991   lto_symtab_encoder_iterator lsei;
 992   lto_symtab_encoder_t encoder;
 993
 994   encoder = lto_get_out_decl_state ()->symtab_node_encoder;
 995
 996   for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
 997        lsei_next_function_in_partition (&lsei))
 998     {
 999       node = lsei_cgraph_node (lsei);
1000       if (node->definition && has_function_state (node))
1001         count++;
1002     }
1003
1004   streamer_write_uhwi_stream (ob->main_stream, count);
1005
1006   /* Process all of the functions.  */
1007   for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
1008        lsei_next_function_in_partition (&lsei))
1009     {
1010       node = lsei_cgraph_node (lsei);
1011       if (node->definition && has_function_state (node))
1012         {
1013           struct bitpack_d bp;
1014           funct_state fs;
1015           int node_ref;
1016           lto_symtab_encoder_t encoder;
1017
1018           fs = get_function_state (node);
1019
1020           encoder = ob->decl_state->symtab_node_encoder;
1021           node_ref = lto_symtab_encoder_encode (encoder, node);
1022           streamer_write_uhwi_stream (ob->main_stream, node_ref);
1023
1024           /* Note that flags will need to be read in the opposite
1025              order as we are pushing the bitflags into FLAGS.  */
1026           bp = bitpack_create (ob->main_stream);
1027           bp_pack_value (&bp, fs->pure_const_state, 2);
1028           bp_pack_value (&bp, fs->state_previously_known, 2);
1029           bp_pack_value (&bp, fs->looping_previously_known, 1);
1030           bp_pack_value (&bp, fs->looping, 1);
1031           bp_pack_value (&bp, fs->can_throw, 1);
1032           bp_pack_value (&bp, fs->can_free, 1);
1033           streamer_write_bitpack (&bp);
1034         }
1035     }
1036
1037   lto_destroy_simple_output_block (ob);
1038 }
1039
1040
1041 /* Deserialize the ipa info for lto.  */
1042
1043 static void
1044 pure_const_read_summary (void)
1045 {
1046   struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
1047   struct lto_file_decl_data *file_data;
1048   unsigned int j = 0;
1049
1050   pass_ipa_pure_const *pass = static_cast <pass_ipa_pure_const *> (current_pass);
1051   pass->register_hooks ();
1052
1053   while ((file_data = file_data_vec[j++]))
1054     {
1055       const char *data;
1056       size_t len;
1057       struct lto_input_block *ib
1058         = lto_create_simple_input_block (file_data,
1059                                          LTO_section_ipa_pure_const,
1060                                          &data, &len);
1061       if (ib)
1062         {
1063           unsigned int i;
1064           unsigned int count = streamer_read_uhwi (ib);
1065
1066           for (i = 0; i < count; i++)
1067             {
1068               unsigned int index;
1069               struct cgraph_node *node;
1070               struct bitpack_d bp;
1071               funct_state fs;
1072               lto_symtab_encoder_t encoder;
1073
1074               fs = XCNEW (struct funct_state_d);
1075               index = streamer_read_uhwi (ib);
1076               encoder = file_data->symtab_node_encoder;
1077               node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref (encoder,
1078                                                                         index));
1079               set_function_state (node, fs);
1080
1081               /* Note that the flags must be read in the opposite
1082                  order in which they were written (the bitflags were
1083                  pushed into FLAGS).  */
1084               bp = streamer_read_bitpack (ib);
1085               fs->pure_const_state
1086                         = (enum pure_const_state_e) bp_unpack_value (&bp, 2);
1087               fs->state_previously_known
1088                         = (enum pure_const_state_e) bp_unpack_value (&bp, 2);
1089               fs->looping_previously_known = bp_unpack_value (&bp, 1);
1090               fs->looping = bp_unpack_value (&bp, 1);
1091               fs->can_throw = bp_unpack_value (&bp, 1);
1092               fs->can_free = bp_unpack_value (&bp, 1);
1093               if (dump_file)
1094                 {
1095                   int flags = flags_from_decl_or_type (node->decl);
1096                   fprintf (dump_file, "Read info for %s/%i ",
1097                            node->name (),
1098                            node->order);
1099                   if (flags & ECF_CONST)
1100                     fprintf (dump_file, " const");
1101                   if (flags & ECF_PURE)
1102                     fprintf (dump_file, " pure");
1103                   if (flags & ECF_NOTHROW)
1104                     fprintf (dump_file, " nothrow");
1105                   fprintf (dump_file, "\n  pure const state: %s\n",
1106                            pure_const_names[fs->pure_const_state]);
1107                   fprintf (dump_file, "  previously known state: %s\n",
1108                            pure_const_names[fs->looping_previously_known]);
1109                   if (fs->looping)
1110                     fprintf (dump_file,"  function is locally looping\n");
1111                   if (fs->looping_previously_known)
1112                     fprintf (dump_file,"  function is previously known looping\n");
1113                   if (fs->can_throw)
1114                     fprintf (dump_file,"  function is locally throwing\n");
1115                   if (fs->can_free)
1116                     fprintf (dump_file,"  function can locally free\n");
1117                 }
1118             }
1119
1120           lto_destroy_simple_input_block (file_data,
1121                                           LTO_section_ipa_pure_const,
1122                                           ib, data, len);
1123         }
1124     }
1125 }
1126
1127 /* We only propagate across edges that can throw externally and their callee
1128    is not interposable.  */
1129
1130 static bool
1131 ignore_edge_for_nothrow (struct cgraph_edge *e)
1132 {
1133   if (!e->can_throw_external || TREE_NOTHROW (e->callee->decl))
1134     return true;
1135
1136   enum availability avail;
1137   cgraph_node *n = e->callee->function_or_virtual_thunk_symbol (&avail);
1138   return (avail <= AVAIL_INTERPOSABLE || TREE_NOTHROW (n->decl));
1139 }
1140
1141 /* Return true if NODE is self recursive function.
1142    Indirectly recursive functions appears as non-trivial strongly
1143    connected components, so we need to care about self recursion
1144    only.  */
1145
1146 static bool
1147 self_recursive_p (struct cgraph_node *node)
1148 {
1149   struct cgraph_edge *e;
1150   for (e = node->callees; e; e = e->next_callee)
1151     if (e->callee->function_symbol () == node)
1152       return true;
1153   return false;
1154 }
1155
1156 /* Return true if N is cdtor that is not const or pure.  In this case we may
1157    need to remove unreachable function if it is marked const/pure.  */
1158
1159 static bool
1160 cdtor_p (cgraph_node *n, void *)
1161 {
1162   if (DECL_STATIC_CONSTRUCTOR (n->decl) || DECL_STATIC_DESTRUCTOR (n->decl))
1163     return ((!TREE_READONLY (n->decl) && !DECL_PURE_P (n->decl))
1164             || DECL_LOOPING_CONST_OR_PURE_P (n->decl));
1165   return false;
1166 }
1167
1168 /* We only propagate across edges with non-interposable callee.  */
1169
1170 static bool
1171 ignore_edge_for_pure_const (struct cgraph_edge *e)
1172 {
1173   enum availability avail;
1174   e->callee->function_or_virtual_thunk_symbol (&avail);
1175   return (avail <= AVAIL_INTERPOSABLE);
1176 }
1177
1178
1179 /* Produce transitive closure over the callgraph and compute pure/const
1180    attributes.  */
1181
1182 static bool
1183 propagate_pure_const (void)
1184 {
1185   struct cgraph_node *node;
1186   struct cgraph_node *w;
1187   struct cgraph_node **order =
1188     XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
1189   int order_pos;
1190   int i;
1191   struct ipa_dfs_info * w_info;
1192   bool remove_p = false;
1193
1194   order_pos = ipa_reduced_postorder (order, true, false,
1195                                      ignore_edge_for_pure_const);
1196   if (dump_file)
1197     {
1198       cgraph_node::dump_cgraph (dump_file);
1199       ipa_print_order (dump_file, "reduced", order, order_pos);
1200     }
1201
1202   /* Propagate the local information through the call graph to produce
1203      the global information.  All the nodes within a cycle will have
1204      the same info so we collapse cycles first.  Then we can do the
1205      propagation in one pass from the leaves to the roots.  */
1206   for (i = 0; i < order_pos; i++ )
1207     {
1208       enum pure_const_state_e pure_const_state = IPA_CONST;
1209       bool looping = false;
1210       int count = 0;
1211       node = order[i];
1212
1213       if (node->alias)
1214         continue;
1215
1216       if (dump_file && (dump_flags & TDF_DETAILS))
1217         fprintf (dump_file, "Starting cycle\n");
1218
1219       /* Find the worst state for any node in the cycle.  */
1220       w = node;
1221       while (w && pure_const_state != IPA_NEITHER)
1222         {
1223           struct cgraph_edge *e;
1224           struct cgraph_edge *ie;
1225           int i;
1226           struct ipa_ref *ref = NULL;
1227
1228           funct_state w_l = get_function_state (w);
1229           if (dump_file && (dump_flags & TDF_DETAILS))
1230             fprintf (dump_file, "  Visiting %s/%i state:%s looping %i\n",
1231                      w->name (),
1232                      w->order,
1233                      pure_const_names[w_l->pure_const_state],
1234                      w_l->looping);
1235
1236           /* First merge in function body properties.  */
1237           worse_state (&pure_const_state, &looping,
1238                        w_l->pure_const_state, w_l->looping);
1239           if (pure_const_state == IPA_NEITHER)
1240             break;
1241
1242           /* For interposable nodes we can not assume anything.  */
1243           if (w->get_availability () == AVAIL_INTERPOSABLE)
1244             {
1245               worse_state (&pure_const_state, &looping,
1246                            w_l->state_previously_known,
1247                            w_l->looping_previously_known);
1248               if (dump_file && (dump_flags & TDF_DETAILS))
1249                 {
1250                   fprintf (dump_file,
1251                            "    Interposable. state %s looping %i\n",
1252                            pure_const_names[w_l->state_previously_known],
1253                            w_l->looping_previously_known);
1254                 }
1255               break;
1256             }
1257
1258           count++;
1259
1260           /* We consider recursive cycles as possibly infinite.
1261              This might be relaxed since infinite recursion leads to stack
1262              overflow.  */
1263           if (count > 1)
1264             looping = true;
1265
1266           /* Now walk the edges and merge in callee properties.  */
1267           for (e = w->callees; e && pure_const_state != IPA_NEITHER;
1268                e = e->next_callee)
1269             {
1270               enum availability avail;
1271               struct cgraph_node *y = e->callee->
1272                                 function_or_virtual_thunk_symbol (&avail);
1273               enum pure_const_state_e edge_state = IPA_CONST;
1274               bool edge_looping = false;
1275
1276               if (dump_file && (dump_flags & TDF_DETAILS))
1277                 {
1278                   fprintf (dump_file,
1279                            "    Call to %s/%i",
1280                            e->callee->name (),
1281                            e->callee->order);
1282                 }
1283               if (avail > AVAIL_INTERPOSABLE)
1284                 {
1285                   funct_state y_l = get_function_state (y);
1286                   if (dump_file && (dump_flags & TDF_DETAILS))
1287                     {
1288                       fprintf (dump_file,
1289                                " state:%s looping:%i\n",
1290                                pure_const_names[y_l->pure_const_state],
1291                                y_l->looping);
1292                     }
1293                   if (y_l->pure_const_state > IPA_PURE
1294                       && e->cannot_lead_to_return_p ())
1295                     {
1296                       if (dump_file && (dump_flags & TDF_DETAILS))
1297                         fprintf (dump_file,
1298                                  "        Ignoring side effects"
1299                                  " -> pure, looping\n");
1300                       edge_state = IPA_PURE;
1301                       edge_looping = true;
1302                     }
1303                   else
1304                     {
1305                       edge_state = y_l->pure_const_state;
1306                       edge_looping = y_l->looping;
1307                     }
1308                 }
1309               else if (special_builtin_state (&edge_state, &edge_looping,
1310                                                y->decl))
1311                 ;
1312               else
1313                 state_from_flags (&edge_state, &edge_looping,
1314                                   flags_from_decl_or_type (y->decl),
1315                                   e->cannot_lead_to_return_p ());
1316
1317               /* Merge the results with what we already know.  */
1318               better_state (&edge_state, &edge_looping,
1319                             w_l->state_previously_known,
1320                             w_l->looping_previously_known);
1321               worse_state (&pure_const_state, &looping,
1322                            edge_state, edge_looping);
1323               if (pure_const_state == IPA_NEITHER)
1324                 break;
1325             }
1326
1327           /* Now process the indirect call.  */
1328           for (ie = w->indirect_calls;
1329                ie && pure_const_state != IPA_NEITHER; ie = ie->next_callee)
1330             {
1331               enum pure_const_state_e edge_state = IPA_CONST;
1332               bool edge_looping = false;
1333
1334               if (dump_file && (dump_flags & TDF_DETAILS))
1335                 fprintf (dump_file, "    Indirect call");
1336               state_from_flags (&edge_state, &edge_looping,
1337                                 ie->indirect_info->ecf_flags,
1338                                 ie->cannot_lead_to_return_p ());
1339               /* Merge the results with what we already know.  */
1340               better_state (&edge_state, &edge_looping,
1341                             w_l->state_previously_known,
1342                             w_l->looping_previously_known);
1343               worse_state (&pure_const_state, &looping,
1344                            edge_state, edge_looping);
1345               if (pure_const_state == IPA_NEITHER)
1346                 break;
1347             }
1348
1349           /* And finally all loads and stores.  */
1350           for (i = 0; w->iterate_reference (i, ref)
1351                && pure_const_state != IPA_NEITHER; i++)
1352             {
1353               enum pure_const_state_e ref_state = IPA_CONST;
1354               bool ref_looping = false;
1355               switch (ref->use)
1356                 {
1357                 case IPA_REF_LOAD:
1358                   /* readonly reads are safe.  */
1359                   if (TREE_READONLY (ref->referred->decl))
1360                     break;
1361                   if (dump_file && (dump_flags & TDF_DETAILS))
1362                     fprintf (dump_file, "    nonreadonly global var read\n");
1363                   ref_state = IPA_PURE;
1364                   break;
1365                 case IPA_REF_STORE:
1366                   if (ref->cannot_lead_to_return ())
1367                     break;
1368                   ref_state = IPA_NEITHER;
1369                   if (dump_file && (dump_flags & TDF_DETAILS))
1370                     fprintf (dump_file, "    global var write\n");
1371                   break;
1372                 case IPA_REF_ADDR:
1373                 case IPA_REF_CHKP:
1374                   break;
1375                 default:
1376                   gcc_unreachable ();
1377                 }
1378               better_state (&ref_state, &ref_looping,
1379                             w_l->state_previously_known,
1380                             w_l->looping_previously_known);
1381               worse_state (&pure_const_state, &looping,
1382                            ref_state, ref_looping);
1383               if (pure_const_state == IPA_NEITHER)
1384                 break;
1385             }
1386           w_info = (struct ipa_dfs_info *) w->aux;
1387           w = w_info->next_cycle;
1388         }
1389       if (dump_file && (dump_flags & TDF_DETAILS))
1390         fprintf (dump_file, "Result %s looping %i\n",
1391                  pure_const_names [pure_const_state],
1392                  looping);
1393
1394       /* Find the worst state of can_free for any node in the cycle.  */
1395       bool can_free = false;
1396       w = node;
1397       while (w && !can_free)
1398         {
1399           struct cgraph_edge *e;
1400           funct_state w_l = get_function_state (w);
1401
1402           if (w_l->can_free
1403               || w->get_availability () == AVAIL_INTERPOSABLE
1404               || w->indirect_calls)
1405             can_free = true;
1406
1407           for (e = w->callees; e && !can_free; e = e->next_callee)
1408             {
1409               enum availability avail;
1410               struct cgraph_node *y = e->callee->
1411                                 function_or_virtual_thunk_symbol (&avail);
1412
1413               if (avail > AVAIL_INTERPOSABLE)
1414                 can_free = get_function_state (y)->can_free;
1415               else
1416                 can_free = true;
1417             }
1418           w_info = (struct ipa_dfs_info *) w->aux;
1419           w = w_info->next_cycle;
1420         }
1421
1422       /* Copy back the region's pure_const_state which is shared by
1423          all nodes in the region.  */
1424       w = node;
1425       while (w)
1426         {
1427           funct_state w_l = get_function_state (w);
1428           enum pure_const_state_e this_state = pure_const_state;
1429           bool this_looping = looping;
1430
1431           w_l->can_free = can_free;
1432           w->nonfreeing_fn = !can_free;
1433           if (!can_free && dump_file)
1434             fprintf (dump_file, "Function found not to call free: %s\n",
1435                      w->name ());
1436
1437           if (w_l->state_previously_known != IPA_NEITHER
1438               && this_state > w_l->state_previously_known)
1439             {
1440               this_state = w_l->state_previously_known;
1441               if (this_state == IPA_NEITHER)
1442                 this_looping = w_l->looping_previously_known;
1443             }
1444           if (!this_looping && self_recursive_p (w))
1445             this_looping = true;
1446           if (!w_l->looping_previously_known)
1447             this_looping = false;
1448
1449           /* All nodes within a cycle share the same info.  */
1450           w_l->pure_const_state = this_state;
1451           w_l->looping = this_looping;
1452
1453           /* Inline clones share declaration with their offline copies;
1454              do not modify their declarations since the offline copy may
1455              be different.  */
1456           if (!w->global.inlined_to)
1457             switch (this_state)
1458               {
1459               case IPA_CONST:
1460                 if (!TREE_READONLY (w->decl))
1461                   {
1462                     warn_function_const (w->decl, !this_looping);
1463                     if (dump_file)
1464                       fprintf (dump_file, "Function found to be %sconst: %s\n",
1465                                this_looping ? "looping " : "",
1466                                w->name ());
1467                   }
1468                 remove_p |= w->call_for_symbol_and_aliases (cdtor_p,
1469                                                             NULL, true);
1470                 w->set_const_flag (true, this_looping);
1471                 break;
1472
1473               case IPA_PURE:
1474                 if (!DECL_PURE_P (w->decl))
1475                   {
1476                     warn_function_pure (w->decl, !this_looping);
1477                     if (dump_file)
1478                       fprintf (dump_file, "Function found to be %spure: %s\n",
1479                                this_looping ? "looping " : "",
1480                                w->name ());
1481                   }
1482                 remove_p |= w->call_for_symbol_and_aliases (cdtor_p,
1483                                                             NULL, true);
1484                 w->set_pure_flag (true, this_looping);
1485                 break;
1486
1487               default:
1488                 break;
1489               }
1490           w_info = (struct ipa_dfs_info *) w->aux;
1491           w = w_info->next_cycle;
1492         }
1493     }
1494
1495   ipa_free_postorder_info ();
1496   free (order);
1497   return remove_p;
1498 }
1499
1500 /* Produce transitive closure over the callgraph and compute nothrow
1501    attributes.  */
1502
1503 static void
1504 propagate_nothrow (void)
1505 {
1506   struct cgraph_node *node;
1507   struct cgraph_node *w;
1508   struct cgraph_node **order =
1509     XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
1510   int order_pos;
1511   int i;
1512   struct ipa_dfs_info * w_info;
1513
1514   order_pos = ipa_reduced_postorder (order, true, false,
1515                                      ignore_edge_for_nothrow);
1516   if (dump_file)
1517     {
1518       cgraph_node::dump_cgraph (dump_file);
1519       ipa_print_order (dump_file, "reduced for nothrow", order, order_pos);
1520     }
1521
1522   /* Propagate the local information through the call graph to produce
1523      the global information.  All the nodes within a cycle will have
1524      the same info so we collapse cycles first.  Then we can do the
1525      propagation in one pass from the leaves to the roots.  */
1526   for (i = 0; i < order_pos; i++ )
1527     {
1528       bool can_throw = false;
1529       node = order[i];
1530
1531       if (node->alias)
1532         continue;
1533
1534       /* Find the worst state for any node in the cycle.  */
1535       w = node;
1536       while (w && !can_throw)
1537         {
1538           struct cgraph_edge *e, *ie;
1539
1540           if (!TREE_NOTHROW (w->decl))
1541             {
1542               funct_state w_l = get_function_state (w);
1543
1544               if (w_l->can_throw
1545                   || w->get_availability () == AVAIL_INTERPOSABLE)
1546                 can_throw = true;
1547
1548               for (e = w->callees; e && !can_throw; e = e->next_callee)
1549                 {
1550                   enum availability avail;
1551
1552                   if (!e->can_throw_external || TREE_NOTHROW (e->callee->decl))
1553                     continue;
1554
1555                   struct cgraph_node *y = e->callee->
1556                                     function_or_virtual_thunk_symbol (&avail);
1557
1558                   /* We can use info about the callee only if we know it can
1559                      not be interposed.  */
1560                   if (avail <= AVAIL_INTERPOSABLE
1561                       || (!TREE_NOTHROW (y->decl)
1562                           && get_function_state (y)->can_throw))
1563                     can_throw = true;
1564                 }
1565               for (ie = w->indirect_calls; ie && !can_throw;
1566                    ie = ie->next_callee)
1567                 if (ie->can_throw_external
1568                     && !(ie->indirect_info->ecf_flags & ECF_NOTHROW))
1569                   can_throw = true;
1570             }
1571           w_info = (struct ipa_dfs_info *) w->aux;
1572           w = w_info->next_cycle;
1573         }
1574
1575       /* Copy back the region's pure_const_state which is shared by
1576          all nodes in the region.  */
1577       w = node;
1578       while (w)
1579         {
1580           funct_state w_l = get_function_state (w);
1581           if (!can_throw && !TREE_NOTHROW (w->decl))
1582             {
1583               /* Inline clones share declaration with their offline copies;
1584                  do not modify their declarations since the offline copy may
1585                  be different.  */
1586               if (!w->global.inlined_to)
1587                 {
1588                   w->set_nothrow_flag (true);
1589                   if (dump_file)
1590                     fprintf (dump_file, "Function found to be nothrow: %s\n",
1591                              w->name ());
1592                 }
1593             }
1594           else if (can_throw && !TREE_NOTHROW (w->decl))
1595             w_l->can_throw = true;
1596           w_info = (struct ipa_dfs_info *) w->aux;
1597           w = w_info->next_cycle;
1598         }
1599     }
1600
1601   ipa_free_postorder_info ();
1602   free (order);
1603 }
1604
1605
1606 /* Produce the global information by preforming a transitive closure
1607    on the local information that was produced by generate_summary.  */
1608
1609 unsigned int
1610 pass_ipa_pure_const::
1611 execute (function *)
1612 {
1613   struct cgraph_node *node;
1614   bool remove_p;
1615
1616   symtab->remove_cgraph_insertion_hook (function_insertion_hook_holder);
1617   symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
1618   symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
1619
1620   /* Nothrow makes more function to not lead to return and improve
1621      later analysis.  */
1622   propagate_nothrow ();
1623   remove_p = propagate_pure_const ();
1624
1625   /* Cleanup. */
1626   FOR_EACH_FUNCTION (node)
1627     if (has_function_state (node))
1628       free (get_function_state (node));
1629   funct_state_vec.release ();
1630   return remove_p ? TODO_remove_functions : 0;
1631 }
1632
1633 static bool
1634 gate_pure_const (void)
1635 {
1636   return flag_ipa_pure_const || in_lto_p;
1637 }
1638
1639 pass_ipa_pure_const::pass_ipa_pure_const(gcc::context *ctxt)
1640     : ipa_opt_pass_d(pass_data_ipa_pure_const, ctxt,
1641                      pure_const_generate_summary, /* generate_summary */
1642                      pure_const_write_summary, /* write_summary */
1643                      pure_const_read_summary, /* read_summary */
1644                      NULL, /* write_optimization_summary */
1645                      NULL, /* read_optimization_summary */
1646                      NULL, /* stmt_fixup */
1647                      0, /* function_transform_todo_flags_start */
1648                      NULL, /* function_transform */
1649                      NULL), /* variable_transform */
1650   init_p(false),
1651   function_insertion_hook_holder(NULL),
1652   node_duplication_hook_holder(NULL),
1653   node_removal_hook_holder(NULL)
1654 {
1655 }
1656
1657 ipa_opt_pass_d *
1658 make_pass_ipa_pure_const (gcc::context *ctxt)
1659 {
1660   return new pass_ipa_pure_const (ctxt);
1661 }
1662
1663 /* Return true if function should be skipped for local pure const analysis.  */
1664
1665 static bool
1666 skip_function_for_local_pure_const (struct cgraph_node *node)
1667 {
1668   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1669      we must not promote functions that are called by already processed functions.  */
1670
1671   if (function_called_by_processed_nodes_p ())
1672     {
1673       if (dump_file)
1674         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
1675       return true;
1676     }
1677   if (node->get_availability () <= AVAIL_INTERPOSABLE)
1678     {
1679       if (dump_file)
1680         fprintf (dump_file, "Function is not available or interposable; not analyzing.\n");
1681       return true;
1682     }
1683   return false;
1684 }
1685
1686 /* Simple local pass for pure const discovery reusing the analysis from
1687    ipa_pure_const.   This pass is effective when executed together with
1688    other optimization passes in early optimization pass queue.  */
1689
1690 namespace {
1691
1692 const pass_data pass_data_local_pure_const =
1693 {
1694   GIMPLE_PASS, /* type */
1695   "local-pure-const", /* name */
1696   OPTGROUP_NONE, /* optinfo_flags */
1697   TV_IPA_PURE_CONST, /* tv_id */
1698   0, /* properties_required */
1699   0, /* properties_provided */
1700   0, /* properties_destroyed */
1701   0, /* todo_flags_start */
1702   0, /* todo_flags_finish */
1703 };
1704
1705 class pass_local_pure_const : public gimple_opt_pass
1706 {
1707 public:
1708   pass_local_pure_const (gcc::context *ctxt)
1709     : gimple_opt_pass (pass_data_local_pure_const, ctxt)
1710   {}
1711
1712   /* opt_pass methods: */
1713   opt_pass * clone () { return new pass_local_pure_const (m_ctxt); }
1714   virtual bool gate (function *) { return gate_pure_const (); }
1715   virtual unsigned int execute (function *);
1716
1717 }; // class pass_local_pure_const
1718
1719 unsigned int
1720 pass_local_pure_const::execute (function *fun)
1721 {
1722   bool changed = false;
1723   funct_state l;
1724   bool skip;
1725   struct cgraph_node *node;
1726
1727   node = cgraph_node::get (current_function_decl);
1728   skip = skip_function_for_local_pure_const (node);
1729   if (!warn_suggest_attribute_const
1730       && !warn_suggest_attribute_pure
1731       && skip)
1732     return 0;
1733
1734   l = analyze_function (node, false);
1735
1736   /* Do NORETURN discovery.  */
1737   if (!skip && !TREE_THIS_VOLATILE (current_function_decl)
1738       && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) == 0)
1739     {
1740       warn_function_noreturn (fun->decl);
1741       if (dump_file)
1742         fprintf (dump_file, "Function found to be noreturn: %s\n",
1743                  current_function_name ());
1744
1745       /* Update declaration and reduce profile to executed once.  */
1746       TREE_THIS_VOLATILE (current_function_decl) = 1;
1747       if (node->frequency > NODE_FREQUENCY_EXECUTED_ONCE)
1748         node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
1749
1750       changed = true;
1751     }
1752
1753   switch (l->pure_const_state)
1754     {
1755     case IPA_CONST:
1756       if (!TREE_READONLY (current_function_decl))
1757         {
1758           warn_function_const (current_function_decl, !l->looping);
1759           if (!skip)
1760             {
1761               node->set_const_flag (true, l->looping);
1762               changed = true;
1763             }
1764           if (dump_file)
1765             fprintf (dump_file, "Function found to be %sconst: %s\n",
1766                      l->looping ? "looping " : "",
1767                      current_function_name ());
1768         }
1769       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1770                && !l->looping)
1771         {
1772           if (!skip)
1773             {
1774               node->set_const_flag (true, false);
1775               changed = true;
1776             }
1777           if (dump_file)
1778             fprintf (dump_file, "Function found to be non-looping: %s\n",
1779                      current_function_name ());
1780         }
1781       break;
1782
1783     case IPA_PURE:
1784       if (!DECL_PURE_P (current_function_decl))
1785         {
1786           if (!skip)
1787             {
1788               node->set_pure_flag (true, l->looping);
1789               changed = true;
1790             }
1791           warn_function_pure (current_function_decl, !l->looping);
1792           if (dump_file)
1793             fprintf (dump_file, "Function found to be %spure: %s\n",
1794                      l->looping ? "looping " : "",
1795                      current_function_name ());
1796         }
1797       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1798                && !l->looping)
1799         {
1800           if (!skip)
1801             {
1802               node->set_pure_flag (true, false);
1803               changed = true;
1804             }
1805           if (dump_file)
1806             fprintf (dump_file, "Function found to be non-looping: %s\n",
1807                      current_function_name ());
1808         }
1809       break;
1810
1811     default:
1812       break;
1813     }
1814   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1815     {
1816       node->set_nothrow_flag (true);
1817       changed = true;
1818       if (dump_file)
1819         fprintf (dump_file, "Function found to be nothrow: %s\n",
1820                  current_function_name ());
1821     }
1822   free (l);
1823   if (changed)
1824     return execute_fixup_cfg ();
1825   else
1826     return 0;
1827 }
1828
1829 } // anon namespace
1830
1831 gimple_opt_pass *
1832 make_pass_local_pure_const (gcc::context *ctxt)
1833 {
1834   return new pass_local_pure_const (ctxt);
1835 }
1836
1837 /* Emit noreturn warnings.  */
1838
1839 namespace {
1840
1841 const pass_data pass_data_warn_function_noreturn =
1842 {
1843   GIMPLE_PASS, /* type */
1844   "*warn_function_noreturn", /* name */
1845   OPTGROUP_NONE, /* optinfo_flags */
1846   TV_NONE, /* tv_id */
1847   PROP_cfg, /* properties_required */
1848   0, /* properties_provided */
1849   0, /* properties_destroyed */
1850   0, /* todo_flags_start */
1851   0, /* todo_flags_finish */
1852 };
1853
1854 class pass_warn_function_noreturn : public gimple_opt_pass
1855 {
1856 public:
1857   pass_warn_function_noreturn (gcc::context *ctxt)
1858     : gimple_opt_pass (pass_data_warn_function_noreturn, ctxt)
1859   {}
1860
1861   /* opt_pass methods: */
1862   virtual bool gate (function *) { return warn_suggest_attribute_noreturn; }
1863   virtual unsigned int execute (function *fun)
1864     {
1865       if (!TREE_THIS_VOLATILE (current_function_decl)
1866           && EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) == 0)
1867         warn_function_noreturn (current_function_decl);
1868       return 0;
1869     }
1870
1871 }; // class pass_warn_function_noreturn
1872
1873 } // anon namespace
1874
1875 gimple_opt_pass *
1876 make_pass_warn_function_noreturn (gcc::context *ctxt)
1877 {
1878   return new pass_warn_function_noreturn (ctxt);
1879 }
1880
1881 /* Simple local pass for pure const discovery reusing the analysis from
1882    ipa_pure_const.   This pass is effective when executed together with
1883    other optimization passes in early optimization pass queue.  */
1884
1885 namespace {
1886
1887 const pass_data pass_data_nothrow =
1888 {
1889   GIMPLE_PASS, /* type */
1890   "nothrow", /* name */
1891   OPTGROUP_NONE, /* optinfo_flags */
1892   TV_IPA_PURE_CONST, /* tv_id */
1893   0, /* properties_required */
1894   0, /* properties_provided */
1895   0, /* properties_destroyed */
1896   0, /* todo_flags_start */
1897   0, /* todo_flags_finish */
1898 };
1899
1900 class pass_nothrow : public gimple_opt_pass
1901 {
1902 public:
1903   pass_nothrow (gcc::context *ctxt)
1904     : gimple_opt_pass (pass_data_nothrow, ctxt)
1905   {}
1906
1907   /* opt_pass methods: */
1908   opt_pass * clone () { return new pass_nothrow (m_ctxt); }
1909   virtual bool gate (function *) { return optimize; }
1910   virtual unsigned int execute (function *);
1911
1912 }; // class pass_nothrow
1913
1914 unsigned int
1915 pass_nothrow::execute (function *)
1916 {
1917   struct cgraph_node *node;
1918   basic_block this_block;
1919
1920   if (TREE_NOTHROW (current_function_decl))
1921     return 0;
1922
1923   node = cgraph_node::get (current_function_decl);
1924
1925   /* We run during lowering, we can not really use availability yet.  */
1926   if (cgraph_node::get (current_function_decl)->get_availability ()
1927       <= AVAIL_INTERPOSABLE)
1928     {
1929       if (dump_file)
1930         fprintf (dump_file, "Function is interposable;"
1931                  " not analyzing.\n");
1932       return true;
1933     }
1934
1935   FOR_EACH_BB_FN (this_block, cfun)
1936     {
1937       for (gimple_stmt_iterator gsi = gsi_start_bb (this_block);
1938            !gsi_end_p (gsi);
1939            gsi_next (&gsi))
1940         if (stmt_can_throw_external (gsi_stmt (gsi)))
1941           {
1942             if (is_gimple_call (gsi_stmt (gsi)))
1943               {
1944                 tree callee_t = gimple_call_fndecl (gsi_stmt (gsi));
1945                 if (callee_t && recursive_call_p (current_function_decl,
1946                                                   callee_t))
1947                   continue;
1948               }
1949
1950             if (dump_file)
1951               {
1952                 fprintf (dump_file, "Statement can throw: ");
1953                 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
1954               }
1955             return 0;
1956           }
1957     }
1958
1959   node->set_nothrow_flag (true);
1960
1961   bool cfg_changed = false;
1962   if (self_recursive_p (node))
1963     FOR_EACH_BB_FN (this_block, cfun)
1964       if (gimple *g = last_stmt (this_block))
1965         if (is_gimple_call (g))
1966           {
1967             tree callee_t = gimple_call_fndecl (g);
1968             if (callee_t
1969                 && recursive_call_p (current_function_decl, callee_t)
1970                 && maybe_clean_eh_stmt (g)
1971                 && gimple_purge_dead_eh_edges (this_block))
1972               cfg_changed = true;
1973           }
1974
1975   if (dump_file)
1976     fprintf (dump_file, "Function found to be nothrow: %s\n",
1977              current_function_name ());
1978   return cfg_changed ? TODO_cleanup_cfg : 0;
1979 }
1980
1981 } // anon namespace
1982
1983 gimple_opt_pass *
1984 make_pass_nothrow (gcc::context *ctxt)
1985 {
1986   return new pass_nothrow (ctxt);
1987 }