gcc/ipa-pure-const.c

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