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