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 (is_gimple_debug (stmt))
 415     return;
 416
 417   if (dump_file)
 418     {
 419       fprintf (dump_file, "  scanning: ");
 420       print_gimple_stmt (dump_file, stmt, 0, 0);
 421     }
 422
 423   /* Look for loads and stores.  */
 424   walk_stmt_load_store_ops (stmt, local, check_load, check_store);
 425
 426   if (gimple_code (stmt) != GIMPLE_CALL
 427       && stmt_could_throw_p (stmt))
 428     {
 429       if (flag_non_call_exceptions)
 430         {
 431           if (dump_file)
 432             fprintf (dump_file, "    can throw; looping");
 433           local->looping = true;
 434         }
 435       if (stmt_can_throw_external (stmt))
 436         {
 437           if (dump_file)
 438             fprintf (dump_file, "    can throw externally");
 439           local->can_throw = true;
 440         }
 441     }
 442   switch (gimple_code (stmt))
 443     {
 444     case GIMPLE_CALL:
 445       check_call (local, stmt, ipa);
 446       break;
 447     case GIMPLE_LABEL:
 448       if (DECL_NONLOCAL (gimple_label_label (stmt)))
 449         /* Target of long jump. */
 450         {
 451           if (dump_file)
 452             fprintf (dump_file, "    nonlocal label is not const/pure");
 453           local->pure_const_state = IPA_NEITHER;
 454         }
 455       break;
 456     case GIMPLE_ASM:
 457       for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 458         {
 459           tree op = gimple_asm_clobber_op (stmt, i);
 460           if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1)
 461             {
 462               if (dump_file)
 463                 fprintf (dump_file, "    memory asm clobber is not const/pure");
 464               /* Abandon all hope, ye who enter here. */
 465               local->pure_const_state = IPA_NEITHER;
 466             }
 467         }
 468       if (gimple_asm_volatile_p (stmt))
 469         {
 470           if (dump_file)
 471             fprintf (dump_file, "    volatile is not const/pure");
 472           /* Abandon all hope, ye who enter here. */
 473           local->pure_const_state = IPA_NEITHER;
 474           local->looping = true;
 475         }
 476       return;
 477     default:
 478       break;
 479     }
 480 }
 481
 482
 483 /* This is the main routine for finding the reference patterns for
 484    global variables within a function FN.  */
 485
 486 static funct_state
 487 analyze_function (struct cgraph_node *fn, bool ipa)
 488 {
 489   tree decl = fn->decl;
 490   tree old_decl = current_function_decl;
 491   funct_state l;
 492   basic_block this_block;
 493
 494   if (cgraph_function_body_availability (fn) <= AVAIL_OVERWRITABLE)
 495     {
 496       if (dump_file)
 497         fprintf (dump_file, "Function is not available or overwrittable; not analyzing.\n");
 498       return NULL;
 499     }
 500
 501   l = XCNEW (struct funct_state_d);
 502   l->pure_const_state = IPA_CONST;
 503   l->state_previously_known = IPA_NEITHER;
 504   l->looping_previously_known = true;
 505   l->looping = false;
 506   l->can_throw = false;
 507
 508   if (dump_file)
 509     {
 510       fprintf (dump_file, "\n\n local analysis of %s\n ",
 511                cgraph_node_name (fn));
 512     }
 513
 514   push_cfun (DECL_STRUCT_FUNCTION (decl));
 515   current_function_decl = decl;
 516
 517   FOR_EACH_BB (this_block)
 518     {
 519       gimple_stmt_iterator gsi;
 520       struct walk_stmt_info wi;
 521
 522       memset (&wi, 0, sizeof(wi));
 523       for (gsi = gsi_start_bb (this_block);
 524            !gsi_end_p (gsi);
 525            gsi_next (&gsi))
 526         {
 527           check_stmt (&gsi, l, ipa);
 528           if (l->pure_const_state == IPA_NEITHER && l->looping && l->can_throw)
 529             goto end;
 530         }
 531     }
 532
 533 end:
 534   if (l->pure_const_state != IPA_NEITHER)
 535     {
 536       /* Const functions cannot have back edges (an
 537          indication of possible infinite loop side
 538          effect.  */
 539       if (mark_dfs_back_edges ())
 540         {
 541           /* Preheaders are needed for SCEV to work.
 542              Simple lateches and recorded exits improve chances that loop will
 543              proved to be finite in testcases such as in loop-15.c and loop-24.c  */
 544           loop_optimizer_init (LOOPS_NORMAL
 545                                | LOOPS_HAVE_RECORDED_EXITS);
 546           if (dump_file && (dump_flags & TDF_DETAILS))
 547             flow_loops_dump (dump_file, NULL, 0);
 548           if (mark_irreducible_loops ())
 549             {
 550               if (dump_file)
 551                 fprintf (dump_file, "    has irreducible loops\n");
 552               l->looping = true;
 553             }
 554           else
 555             {
 556               loop_iterator li;
 557               struct loop *loop;
 558               scev_initialize ();
 559               FOR_EACH_LOOP (li, loop, 0)
 560                 if (!finite_loop_p (loop))
 561                   {
 562                     if (dump_file)
 563                       fprintf (dump_file, "    can not prove finiteness of loop %i\n", loop->num);
 564                     l->looping =true;
 565                     break;
 566                   }
 567               scev_finalize ();
 568             }
 569           loop_optimizer_finalize ();
 570         }
 571     }
 572
 573   if (TREE_READONLY (decl))
 574     {
 575       l->pure_const_state = IPA_CONST;
 576       l->state_previously_known = IPA_CONST;
 577       if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
 578         l->looping = false, l->looping_previously_known = false;
 579     }
 580   if (DECL_PURE_P (decl))
 581     {
 582       if (l->pure_const_state != IPA_CONST)
 583         l->pure_const_state = IPA_PURE;
 584       l->state_previously_known = IPA_PURE;
 585       if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
 586         l->looping = false, l->looping_previously_known = false;
 587     }
 588   if (TREE_NOTHROW (decl))
 589     l->can_throw = false;
 590
 591   pop_cfun ();
 592   current_function_decl = old_decl;
 593   if (dump_file)
 594     {
 595       if (l->looping)
 596         fprintf (dump_file, "Function is locally looping.\n");
 597       if (l->can_throw)
 598         fprintf (dump_file, "Function is locally throwing.\n");
 599       if (l->pure_const_state == IPA_CONST)
 600         fprintf (dump_file, "Function is locally const.\n");
 601       if (l->pure_const_state == IPA_PURE)
 602         fprintf (dump_file, "Function is locally pure.\n");
 603     }
 604   return l;
 605 }
 606
 607 /* Called when new function is inserted to callgraph late.  */
 608 static void
 609 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 610 {
 611  if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 612    return;
 613   /* There are some shared nodes, in particular the initializers on
 614      static declarations.  We do not need to scan them more than once
 615      since all we would be interested in are the addressof
 616      operations.  */
 617   visited_nodes = pointer_set_create ();
 618   set_function_state (node, analyze_function (node, true));
 619   pointer_set_destroy (visited_nodes);
 620   visited_nodes = NULL;
 621 }
 622
 623 /* Called when new clone is inserted to callgraph late.  */
 624
 625 static void
 626 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 627                      void *data ATTRIBUTE_UNUSED)
 628 {
 629   if (get_function_state (src))
 630     {
 631       funct_state l = XNEW (struct funct_state_d);
 632       gcc_assert (!get_function_state (dst));
 633       memcpy (l, get_function_state (src), sizeof (*l));
 634       set_function_state (dst, l);
 635     }
 636 }
 637
 638 /* Called when new clone is inserted to callgraph late.  */
 639
 640 static void
 641 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 642 {
 643   if (get_function_state (node))
 644     {
 645       free (get_function_state (node));
 646       set_function_state (node, NULL);
 647     }
 648 }
 649
 650 \f
 651 /* Analyze each function in the cgraph to see if it is locally PURE or
 652    CONST.  */
 653
 654 static void
 655 generate_summary (void)
 656 {
 657   struct cgraph_node *node;
 658
 659   node_removal_hook_holder =
 660       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 661   node_duplication_hook_holder =
 662       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 663   function_insertion_hook_holder =
 664       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 665   /* There are some shared nodes, in particular the initializers on
 666      static declarations.  We do not need to scan them more than once
 667      since all we would be interested in are the addressof
 668      operations.  */
 669   visited_nodes = pointer_set_create ();
 670
 671   /* Process all of the functions.
 672
 673      We do NOT process any AVAIL_OVERWRITABLE functions, we cannot
 674      guarantee that what we learn about the one we see will be true
 675      for the one that overrides it.
 676   */
 677   for (node = cgraph_nodes; node; node = node->next)
 678     if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 679       set_function_state (node, analyze_function (node, true));
 680
 681   pointer_set_destroy (visited_nodes);
 682   visited_nodes = NULL;
 683 }
 684
 685 static bool
 686 ignore_edge (struct cgraph_edge *e)
 687 {
 688   return (!e->can_throw_external);
 689 }
 690
 691 /* Produce the global information by preforming a transitive closure
 692    on the local information that was produced by generate_summary.
 693    Note that there is no function_transform pass since this only
 694    updates the function_decl.  */
 695
 696 static unsigned int
 697 propagate (void)
 698 {
 699   struct cgraph_node *node;
 700   struct cgraph_node *w;
 701   struct cgraph_node **order =
 702     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 703   int order_pos;
 704   int i;
 705   struct ipa_dfs_info * w_info;
 706
 707   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
 708   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
 709   cgraph_remove_node_removal_hook (node_removal_hook_holder);
 710   order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
 711   if (dump_file)
 712     {
 713       dump_cgraph (dump_file);
 714       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 715     }
 716
 717   /* Propagate the local information thru the call graph to produce
 718      the global information.  All the nodes within a cycle will have
 719      the same info so we collapse cycles first.  Then we can do the
 720      propagation in one pass from the leaves to the roots.  */
 721   for (i = 0; i < order_pos; i++ )
 722     {
 723       enum pure_const_state_e pure_const_state = IPA_CONST;
 724       bool looping = false;
 725       int count = 0;
 726       node = order[i];
 727
 728       /* Find the worst state for any node in the cycle.  */
 729       w = node;
 730       while (w)
 731         {
 732           struct cgraph_edge *e;
 733           funct_state w_l = get_function_state (w);
 734           if (pure_const_state < w_l->pure_const_state)
 735             pure_const_state = w_l->pure_const_state;
 736
 737           if (w_l->looping)
 738             looping = true;
 739
 740           if (pure_const_state == IPA_NEITHER)
 741             break;
 742
 743           count++;
 744
 745           if (count > 1)
 746             looping = true;
 747
 748           for (e = w->callees; e; e = e->next_callee)
 749             {
 750               struct cgraph_node *y = e->callee;
 751
 752               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 753                 {
 754                   funct_state y_l = get_function_state (y);
 755                   if (pure_const_state < y_l->pure_const_state)
 756                     pure_const_state = y_l->pure_const_state;
 757                   if (pure_const_state == IPA_NEITHER)
 758                     break;
 759                   if (y_l->looping)
 760                     looping = true;
 761                 }
 762             }
 763           w_info = (struct ipa_dfs_info *) w->aux;
 764           w = w_info->next_cycle;
 765         }
 766
 767       /* Copy back the region's pure_const_state which is shared by
 768          all nodes in the region.  */
 769       w = node;
 770       while (w)
 771         {
 772           funct_state w_l = get_function_state (w);
 773           enum pure_const_state_e this_state = pure_const_state;
 774           bool this_looping = looping;
 775
 776           if (w_l->state_previously_known != IPA_NEITHER
 777               && this_state > w_l->state_previously_known)
 778             this_state = w_l->state_previously_known;
 779           if (!w_l->looping_previously_known)
 780             this_looping = false;
 781
 782           /* All nodes within a cycle share the same info.  */
 783           w_l->pure_const_state = this_state;
 784           w_l->looping = this_looping;
 785
 786           switch (this_state)
 787             {
 788             case IPA_CONST:
 789               if (!TREE_READONLY (w->decl) && dump_file)
 790                 fprintf (dump_file, "Function found to be %sconst: %s\n",
 791                          this_looping ? "looping " : "",
 792                          cgraph_node_name (w));
 793               TREE_READONLY (w->decl) = 1;
 794               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 795               break;
 796
 797             case IPA_PURE:
 798               if (!DECL_PURE_P (w->decl) && dump_file)
 799                 fprintf (dump_file, "Function found to be %spure: %s\n",
 800                          this_looping ? "looping " : "",
 801                          cgraph_node_name (w));
 802               DECL_PURE_P (w->decl) = 1;
 803               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
 804               break;
 805
 806             default:
 807               break;
 808             }
 809           w_info = (struct ipa_dfs_info *) w->aux;
 810           w = w_info->next_cycle;
 811         }
 812     }
 813
 814   /* Cleanup. */
 815   for (node = cgraph_nodes; node; node = node->next)
 816     {
 817       /* Get rid of the aux information.  */
 818       if (node->aux)
 819         {
 820           w_info = (struct ipa_dfs_info *) node->aux;
 821           free (node->aux);
 822           node->aux = NULL;
 823         }
 824     }
 825   order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
 826   if (dump_file)
 827     {
 828       dump_cgraph (dump_file);
 829       ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
 830     }
 831   /* Propagate the local information thru the call graph to produce
 832      the global information.  All the nodes within a cycle will have
 833      the same info so we collapse cycles first.  Then we can do the
 834      propagation in one pass from the leaves to the roots.  */
 835   for (i = 0; i < order_pos; i++ )
 836     {
 837       bool can_throw = false;
 838       node = order[i];
 839
 840       /* Find the worst state for any node in the cycle.  */
 841       w = node;
 842       while (w)
 843         {
 844           struct cgraph_edge *e;
 845           funct_state w_l = get_function_state (w);
 846
 847           if (w_l->can_throw)
 848             can_throw = true;
 849
 850           if (can_throw)
 851             break;
 852
 853           for (e = w->callees; e; e = e->next_callee)
 854             {
 855               struct cgraph_node *y = e->callee;
 856
 857               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
 858                 {
 859                   funct_state y_l = get_function_state (y);
 860
 861                   if (can_throw)
 862                     break;
 863                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
 864                       && e->can_throw_external)
 865                     can_throw = true;
 866                 }
 867             }
 868           w_info = (struct ipa_dfs_info *) w->aux;
 869           w = w_info->next_cycle;
 870         }
 871
 872       /* Copy back the region's pure_const_state which is shared by
 873          all nodes in the region.  */
 874       w = node;
 875       while (w)
 876         {
 877           funct_state w_l = get_function_state (w);
 878           if (!can_throw && !TREE_NOTHROW (w->decl))
 879             {
 880               struct cgraph_edge *e;
 881               TREE_NOTHROW (w->decl) = true;
 882               for (e = w->callers; e; e = e->next_caller)
 883                 e->can_throw_external = false;
 884               if (dump_file)
 885                 fprintf (dump_file, "Function found to be nothrow: %s\n",
 886                          cgraph_node_name (w));
 887             }
 888           else if (can_throw && !TREE_NOTHROW (w->decl))
 889             w_l->can_throw = true;
 890           w_info = (struct ipa_dfs_info *) w->aux;
 891           w = w_info->next_cycle;
 892         }
 893     }
 894
 895   /* Cleanup. */
 896   for (node = cgraph_nodes; node; node = node->next)
 897     {
 898       /* Get rid of the aux information.  */
 899       if (node->aux)
 900         {
 901           w_info = (struct ipa_dfs_info *) node->aux;
 902           free (node->aux);
 903           node->aux = NULL;
 904         }
 905       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
 906         free (get_function_state (node));
 907     }
 908
 909   free (order);
 910   VEC_free (funct_state, heap, funct_state_vec);
 911   finish_state ();
 912   return 0;
 913 }
 914
 915 static bool
 916 gate_pure_const (void)
 917 {
 918   return (flag_ipa_pure_const
 919           /* Don't bother doing anything if the program has errors.  */
 920           && !(errorcount || sorrycount));
 921 }
 922
 923 struct ipa_opt_pass_d pass_ipa_pure_const =
 924 {
 925  {
 926   IPA_PASS,
 927   "pure-const",                         /* name */
 928   gate_pure_const,                      /* gate */
 929   propagate,                            /* execute */
 930   NULL,                                 /* sub */
 931   NULL,                                 /* next */
 932   0,                                    /* static_pass_number */
 933   TV_IPA_PURE_CONST,                    /* tv_id */
 934   0,                                    /* properties_required */
 935   0,                                    /* properties_provided */
 936   0,                                    /* properties_destroyed */
 937   0,                                    /* todo_flags_start */
 938   0                                     /* todo_flags_finish */
 939  },
 940  generate_summary,                      /* generate_summary */
 941  NULL,                                  /* write_summary */
 942  NULL,                                  /* read_summary */
 943  NULL,                                  /* function_read_summary */
 944  0,                                     /* TODOs */
 945  NULL,                                  /* function_transform */
 946  NULL                                   /* variable_transform */
 947 };
 948
 949 /* Simple local pass for pure const discovery reusing the analysis from
 950    ipa_pure_const.   This pass is effective when executed together with
 951    other optimization passes in early optimization pass queue.  */
 952
 953 static unsigned int
 954 local_pure_const (void)
 955 {
 956   bool changed = false;
 957   funct_state l;
 958
 959   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
 960      we must not promote functions that are called by already processed functions.  */
 961
 962   if (function_called_by_processed_nodes_p ())
 963     {
 964       if (dump_file)
 965         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
 966       return 0;
 967     }
 968
 969   l = analyze_function (cgraph_node (current_function_decl), false);
 970   if (!l)
 971     {
 972       if (dump_file)
 973         fprintf (dump_file, "Function has wrong visibility; ignoring\n");
 974       return 0;
 975     }
 976
 977   switch (l->pure_const_state)
 978     {
 979     case IPA_CONST:
 980       if (!TREE_READONLY (current_function_decl))
 981         {
 982           TREE_READONLY (current_function_decl) = 1;
 983           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
 984           changed = true;
 985           if (dump_file)
 986             fprintf (dump_file, "Function found to be %sconst: %s\n",
 987                      l->looping ? "looping " : "",
 988                      lang_hooks.decl_printable_name (current_function_decl,
 989                                                      2));
 990         }
 991       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
 992                && !l->looping)
 993         {
 994           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
 995           changed = true;
 996           if (dump_file)
 997             fprintf (dump_file, "Function found to be non-looping: %s\n",
 998                      lang_hooks.decl_printable_name (current_function_decl,
 999                                                      2));
1000         }
1001       break;
1002
1003     case IPA_PURE:
1004       if (!TREE_READONLY (current_function_decl))
1005         {
1006           DECL_PURE_P (current_function_decl) = 1;
1007           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
1008           changed = true;
1009           if (dump_file)
1010             fprintf (dump_file, "Function found to be %spure: %s\n",
1011                      l->looping ? "looping " : "",
1012                      lang_hooks.decl_printable_name (current_function_decl,
1013                                                      2));
1014         }
1015       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1016                && !l->looping)
1017         {
1018           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
1019           changed = true;
1020           if (dump_file)
1021             fprintf (dump_file, "Function found to be non-looping: %s\n",
1022                      lang_hooks.decl_printable_name (current_function_decl,
1023                                                      2));
1024         }
1025       break;
1026
1027     default:
1028       break;
1029     }
1030   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1031     {
1032       struct cgraph_edge *e;
1033
1034       TREE_NOTHROW (current_function_decl) = true;
1035       for (e = cgraph_node (current_function_decl)->callers;
1036            e; e = e->next_caller)
1037         e->can_throw_external = false;
1038       changed = true;
1039       if (dump_file)
1040         fprintf (dump_file, "Function found to be nothrow: %s\n",
1041                  lang_hooks.decl_printable_name (current_function_decl,
1042                                                  2));
1043     }
1044   if (l)
1045     free (l);
1046   if (changed)
1047     return execute_fixup_cfg ();
1048   else
1049     return 0;
1050 }
1051
1052 struct gimple_opt_pass pass_local_pure_const =
1053 {
1054  {
1055   GIMPLE_PASS,
1056   "local-pure-const",                   /* name */
1057   gate_pure_const,                      /* gate */
1058   local_pure_const,                     /* execute */
1059   NULL,                                 /* sub */
1060   NULL,                                 /* next */
1061   0,                                    /* static_pass_number */
1062   TV_IPA_PURE_CONST,                    /* tv_id */
1063   0,                                    /* properties_required */
1064   0,                                    /* properties_provided */
1065   0,                                    /* properties_destroyed */
1066   0,                                    /* todo_flags_start */
1067   0                                     /* todo_flags_finish */
1068  }
1069 };