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