gcc/ipa-pure-const.c

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