gcc/ipa-pure-const.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004, 2005, 2007, 2008 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 "c-common.h"
  47 #include "gimple.h"
  48 #include "cgraph.h"
  49 #include "output.h"
  50 #include "flags.h"
  51 #include "timevar.h"
  52 #include "diagnostic.h"
  53 #include "langhooks.h"
  54 #include "target.h"
  55
  56 static struct pointer_set_t *visited_nodes;
  57
  58 /* Lattice values for const and pure functions.  Everything starts out
  59    being const, then may drop to pure and then neither depending on
  60    what is found.  */
  61 enum pure_const_state_e
  62 {
  63   IPA_CONST,
  64   IPA_PURE,
  65   IPA_NEITHER
  66 };
  67
  68 /* Holder for the const_state.  There is one of these per function
  69    decl.  */
  70 struct funct_state_d
  71 {
  72   /* See above.  */
  73   enum pure_const_state_e pure_const_state;
  74
  75   /* True if the function could possibly infinite loop.  There are a
  76      lot of ways that this could be determined.  We are pretty
  77      conservative here.  While it is possible to cse pure and const
  78      calls, it is not legal to have dce get rid of the call if there
  79      is a possibility that the call could infinite loop since this is
  80      a behavioral change.  */
  81   bool looping;
  82
  83   /* If the state of the function was set in the source, then assume
  84      that it was done properly even if the analysis we do would be
  85      more pessimestic.  */
  86   bool state_set_in_source;
  87 };
  88
  89 typedef struct funct_state_d * funct_state;
  90
  91 /* The storage of the funct_state is abstracted because there is the
  92    possibility that it may be desirable to move this to the cgraph
  93    local info.  */
  94
  95 /* Array, indexed by cgraph node uid, of function states.  */
  96
  97 static funct_state *funct_state_vec;
  98
  99
 100 /* Init the function state.  */
 101
 102 static void
 103 init_state (void)
 104 {
 105   funct_state_vec = XCNEWVEC (funct_state, cgraph_max_uid);
 106 }
 107
 108
 109 /* Init the function state.  */
 110
 111 static void
 112 finish_state (void)
 113 {
 114   free (funct_state_vec);
 115 }
 116
 117
 118 /* Return the function state from NODE.  */
 119
 120 static inline funct_state
 121 get_function_state (struct cgraph_node *node)
 122 {
 123   return funct_state_vec[node->uid];
 124 }
 125
 126 /* Set the function state S for NODE.  */
 127
 128 static inline void
 129 set_function_state (struct cgraph_node *node, funct_state s)
 130 {
 131   funct_state_vec[node->uid] = s;
 132 }
 133
 134 /* Check to see if the use (or definition when CHECKING_WRITE is true)
 135    variable T is legal in a function that is either pure or const.  */
 136
 137 static inline void
 138 check_decl (funct_state local,
 139             tree t, bool checking_write)
 140 {
 141   /* If the variable has the "used" attribute, treat it as if it had a
 142      been touched by the devil.  */
 143   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
 144     {
 145       local->pure_const_state = IPA_NEITHER;
 146       local->looping = false;
 147       return;
 148     }
 149
 150   /* Do not want to do anything with volatile except mark any
 151      function that uses one to be not const or pure.  */
 152   if (TREE_THIS_VOLATILE (t))
 153     {
 154       local->pure_const_state = IPA_NEITHER;
 155       local->looping = false;
 156       return;
 157     }
 158
 159   /* Do not care about a local automatic that is not static.  */
 160   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 161     return;
 162
 163   /* Since we have dealt with the locals and params cases above, if we
 164      are CHECKING_WRITE, this cannot be a pure or constant
 165      function.  */
 166   if (checking_write)
 167     {
 168       local->pure_const_state = IPA_NEITHER;
 169       local->looping = false;
 170       return;
 171     }
 172
 173   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 174     {
 175       /* If the front end set the variable to be READONLY and
 176          constant, we can allow this variable in pure or const
 177          functions but the scope is too large for our analysis to set
 178          these bits ourselves.  */
 179
 180       if (TREE_READONLY (t)
 181           && DECL_INITIAL (t)
 182           && is_gimple_min_invariant (DECL_INITIAL (t)))
 183         ; /* Read of a constant, do not change the function state.  */
 184       else
 185         {
 186           /* Just a regular read.  */
 187           if (local->pure_const_state == IPA_CONST)
 188             local->pure_const_state = IPA_PURE;
 189         }
 190     }
 191
 192   /* Compilation level statics can be read if they are readonly
 193      variables.  */
 194   if (TREE_READONLY (t))
 195     return;
 196
 197   /* Just a regular read.  */
 198   if (local->pure_const_state == IPA_CONST)
 199     local->pure_const_state = IPA_PURE;
 200 }
 201
 202 /* If T is a VAR_DECL check to see if it is an allowed reference.  */
 203
 204 static void
 205 check_operand (funct_state local,
 206                tree t, bool checking_write)
 207 {
 208   if (!t) return;
 209
 210   if (TREE_CODE (t) == VAR_DECL)
 211     check_decl (local, t, checking_write);
 212 }
 213
 214 /* Examine tree T for references.  */
 215
 216 static void
 217 check_tree (funct_state local, tree t, bool checking_write)
 218 {
 219   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)
 220       || TREE_CODE (t) == SSA_NAME)
 221     return;
 222
 223   /* Any tree which is volatile disqualifies this function from being
 224      const or pure. */
 225   if (TREE_THIS_VOLATILE (t))
 226     {
 227       local->pure_const_state = IPA_NEITHER;
 228       local->looping = false;
 229       return;
 230     }
 231
 232   while (TREE_CODE (t) == REALPART_EXPR
 233          || TREE_CODE (t) == IMAGPART_EXPR
 234          || handled_component_p (t))
 235     {
 236       if (TREE_CODE (t) == ARRAY_REF)
 237         check_operand (local, TREE_OPERAND (t, 1), false);
 238       t = TREE_OPERAND (t, 0);
 239     }
 240
 241   /* The bottom of an indirect reference can only be read, not
 242      written.  */
 243   if (INDIRECT_REF_P (t))
 244     {
 245       check_tree (local, TREE_OPERAND (t, 0), false);
 246
 247       /* Any indirect reference that occurs on the lhs
 248          disqualifies the function from being pure or const. Any
 249          indirect reference that occurs on the rhs disqualifies the
 250          function from being const.  */
 251       if (checking_write)
 252         {
 253           local->pure_const_state = IPA_NEITHER;
 254           local->looping = false;
 255           return;
 256         }
 257       else if (local->pure_const_state == IPA_CONST)
 258         local->pure_const_state = IPA_PURE;
 259     }
 260
 261   if (SSA_VAR_P (t))
 262     check_operand (local, t, checking_write);
 263 }
 264
 265 /* Scan tree T to see if there are any addresses taken in within T.  */
 266
 267 static void
 268 look_for_address_of (funct_state local, tree t)
 269 {
 270   if (TREE_CODE (t) == ADDR_EXPR)
 271     {
 272       tree x = get_base_var (t);
 273       if (TREE_CODE (x) == VAR_DECL)
 274         {
 275           check_decl (local, x, false);
 276
 277           /* Taking the address of something appears to be reasonable
 278              in PURE code.  Not allowed in const.  */
 279           if (local->pure_const_state == IPA_CONST)
 280             local->pure_const_state = IPA_PURE;
 281         }
 282     }
 283 }
 284
 285 /* Check to see if T is a read or address of operation on a var we are
 286    interested in analyzing.  LOCAL is passed in to get access to its
 287    bit vectors.  */
 288
 289 static void
 290 check_rhs_var (funct_state local, tree t)
 291 {
 292   look_for_address_of (local, t);
 293
 294   /* Memcmp and strlen can both trap and they are declared pure.  */
 295   if (tree_could_trap_p (t)
 296       && local->pure_const_state == IPA_CONST)
 297     local->pure_const_state = IPA_PURE;
 298
 299   check_tree(local, t, false);
 300 }
 301
 302 /* Check to see if T is an assignment to a var we are interested in
 303    analyzing.  LOCAL is passed in to get access to its bit vectors. */
 304
 305 static void
 306 check_lhs_var (funct_state local, tree t)
 307 {
 308   /* Memcmp and strlen can both trap and they are declared pure.
 309      Which seems to imply that we can apply the same rule here.  */
 310   if (tree_could_trap_p (t)
 311       && local->pure_const_state == IPA_CONST)
 312     local->pure_const_state = IPA_PURE;
 313
 314   check_tree(local, t, true);
 315 }
 316
 317 /* This is a scaled down version of get_asm_expr_operands from
 318    tree_ssa_operands.c.  The version there runs much later and assumes
 319    that aliasing information is already available. Here we are just
 320    trying to find if the set of inputs and outputs contain references
 321    or address of operations to local static variables.  STMT is the
 322    actual asm statement.  */
 323
 324 static void
 325 get_asm_expr_operands (funct_state local, gimple stmt)
 326 {
 327   size_t noutputs = gimple_asm_noutputs (stmt);
 328   const char **oconstraints
 329     = (const char **) alloca ((noutputs) * sizeof (const char *));
 330   size_t i;
 331   tree op;
 332   const char *constraint;
 333   bool allows_mem, allows_reg, is_inout;
 334
 335   for (i = 0; i < noutputs; i++)
 336     {
 337       op = gimple_asm_output_op (stmt, i);
 338       oconstraints[i] = constraint
 339         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
 340       parse_output_constraint (&constraint, i, 0, 0,
 341                                &allows_mem, &allows_reg, &is_inout);
 342
 343       check_lhs_var (local, TREE_VALUE (op));
 344     }
 345
 346   for (i = 0; i < gimple_asm_ninputs (stmt); i++)
 347     {
 348       op = gimple_asm_input_op (stmt, i);
 349       constraint
 350         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op)));
 351       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
 352                               oconstraints, &allows_mem, &allows_reg);
 353
 354       check_rhs_var (local, TREE_VALUE (op));
 355     }
 356
 357   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 358     {
 359       op = gimple_asm_clobber_op (stmt, i);
 360       if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1)
 361         /* Abandon all hope, ye who enter here. */
 362         local->pure_const_state = IPA_NEITHER;
 363     }
 364
 365   if (gimple_asm_volatile_p (stmt))
 366     local->pure_const_state = IPA_NEITHER;
 367 }
 368
 369 /* Check the parameters of a function call to CALL_EXPR to see if
 370    there are any references in the parameters that are not allowed for
 371    pure or const functions.  Also check to see if this is either an
 372    indirect call, a call outside the compilation unit, or has special
 373    attributes that may also effect the purity.  The CALL_EXPR node for
 374    the entire call expression.  */
 375
 376 static void
 377 check_call (funct_state local, gimple call)
 378 {
 379   int flags = gimple_call_flags (call);
 380   tree lhs, callee_t = gimple_call_fndecl (call);
 381   struct cgraph_node* callee;
 382   enum availability avail = AVAIL_NOT_AVAILABLE;
 383   size_t i;
 384
 385   lhs = gimple_call_lhs (call);
 386   if (lhs)
 387     check_lhs_var (local, lhs);
 388
 389   for (i = 0; i < gimple_call_num_args (call); i++)
 390     check_rhs_var (local, gimple_call_arg (call, i));
 391
 392   /* The const and pure flags are set by a variety of places in the
 393      compiler (including here).  If someone has already set the flags
 394      for the callee, (such as for some of the builtins) we will use
 395      them, otherwise we will compute our own information.
 396
 397      Const and pure functions have less clobber effects than other
 398      functions so we process these first.  Otherwise if it is a call
 399      outside the compilation unit or an indirect call we punt.  This
 400      leaves local calls which will be processed by following the call
 401      graph.  */
 402   if (callee_t)
 403     {
 404       callee = cgraph_node(callee_t);
 405       avail = cgraph_function_body_availability (callee);
 406
 407       /* When bad things happen to bad functions, they cannot be const
 408          or pure.  */
 409       if (setjmp_call_p (callee_t))
 410         {
 411           local->pure_const_state = IPA_NEITHER;
 412           local->looping = false;
 413         }
 414
 415       if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
 416         switch (DECL_FUNCTION_CODE (callee_t))
 417           {
 418           case BUILT_IN_LONGJMP:
 419           case BUILT_IN_NONLOCAL_GOTO:
 420             local->pure_const_state = IPA_NEITHER;
 421             local->looping = false;
 422             break;
 423           default:
 424             break;
 425           }
 426     }
 427
 428   /* The callee is either unknown (indirect call) or there is just no
 429      scannable code for it (external call) .  We look to see if there
 430      are any bits available for the callee (such as by declaration or
 431      because it is builtin) and process solely on the basis of those
 432      bits. */
 433   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 434     {
 435       if (flags & ECF_PURE)
 436         {
 437           if (local->pure_const_state == IPA_CONST)
 438             local->pure_const_state = IPA_PURE;
 439         }
 440       else
 441         local->pure_const_state = IPA_NEITHER;
 442     }
 443   else
 444     {
 445       /* We have the code and we will scan it for the effects. */
 446       if (flags & ECF_PURE)
 447         {
 448           if (local->pure_const_state == IPA_CONST)
 449             local->pure_const_state = IPA_PURE;
 450         }
 451     }
 452 }
 453
 454 /* TP is the part of the tree currently under the microscope.
 455    WALK_SUBTREES is part of the walk_tree api but is unused here.
 456    DATA is cgraph_node of the function being walked.  */
 457
 458 /* FIXME: When this is converted to run over SSA form, this code
 459    should be converted to use the operand scanner.  */
 460
 461 static tree
 462 scan_function_op (tree *tp, int *walk_subtrees, void *data)
 463 {
 464   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 465   struct cgraph_node *fn = (struct cgraph_node *) wi->info;
 466   tree t = *tp;
 467   funct_state local = get_function_state (fn);
 468
 469   switch (TREE_CODE (t))
 470     {
 471     case VAR_DECL:
 472       if (DECL_INITIAL (t))
 473         walk_tree (&DECL_INITIAL (t), scan_function_op, data, visited_nodes);
 474       *walk_subtrees = 0;
 475       break;
 476
 477     case ADDR_EXPR:
 478       /* This case is here to find addresses on rhs of constructors in
 479          decl_initial of static variables. */
 480       check_rhs_var (local, t);
 481       *walk_subtrees = 0;
 482       break;
 483
 484     default:
 485       break;
 486     }
 487   return NULL;
 488 }
 489
 490 static tree
 491 scan_function_stmt (gimple_stmt_iterator *gsi_p,
 492                     bool *handled_ops_p,
 493                     struct walk_stmt_info *wi)
 494 {
 495   struct cgraph_node *fn = (struct cgraph_node *) wi->info;
 496   gimple stmt = gsi_stmt (*gsi_p);
 497   funct_state local = get_function_state (fn);
 498
 499   switch (gimple_code (stmt))
 500     {
 501     case GIMPLE_ASSIGN:
 502       {
 503         /* First look on the lhs and see what variable is stored to */
 504         tree lhs = gimple_assign_lhs (stmt);
 505         tree rhs1 = gimple_assign_rhs1 (stmt);
 506         tree rhs2 = gimple_assign_rhs2 (stmt);
 507         enum tree_code code = gimple_assign_rhs_code (stmt);
 508
 509         check_lhs_var (local, lhs);
 510
 511         /* For the purposes of figuring out what the cast affects */
 512
 513         /* Next check the operands on the rhs to see if they are ok. */
 514         switch (TREE_CODE_CLASS (code))
 515           {
 516           case tcc_binary:
 517             {
 518               check_rhs_var (local, rhs1);
 519               check_rhs_var (local, rhs2);
 520             }
 521             break;
 522           case tcc_unary:
 523             {
 524               check_rhs_var (local, rhs1);
 525             }
 526
 527             break;
 528           case tcc_reference:
 529             check_rhs_var (local, rhs1);
 530             break;
 531           case tcc_declaration:
 532             check_rhs_var (local, rhs1);
 533             break;
 534           case tcc_expression:
 535             switch (code)
 536               {
 537               case ADDR_EXPR:
 538                 check_rhs_var (local, rhs1);
 539                 break;
 540               default:
 541                 break;
 542               }
 543             break;
 544           default:
 545             break;
 546           }
 547         *handled_ops_p = true;
 548       }
 549       break;
 550
 551     case GIMPLE_LABEL:
 552       if (DECL_NONLOCAL (gimple_label_label (stmt)))
 553         /* Target of long jump. */
 554         {
 555           local->pure_const_state = IPA_NEITHER;
 556           local->looping = false;
 557         }
 558       break;
 559
 560     case GIMPLE_CALL:
 561       check_call (local, stmt);
 562       *handled_ops_p = true;
 563       break;
 564
 565     case GIMPLE_ASM:
 566       get_asm_expr_operands (local, stmt);
 567       *handled_ops_p = true;
 568       break;
 569
 570     default:
 571       break;
 572     }
 573   return NULL;
 574 }
 575
 576
 577 /* This is the main routine for finding the reference patterns for
 578    global variables within a function FN.  */
 579
 580 static void
 581 analyze_function (struct cgraph_node *fn)
 582 {
 583   tree decl = fn->decl;
 584   funct_state l = XCNEW (struct funct_state_d);
 585
 586   set_function_state (fn, l);
 587
 588   l->pure_const_state = IPA_CONST;
 589   l->state_set_in_source = false;
 590   if (DECL_LOOPING_CONST_OR_PURE_P (decl))
 591     l->looping = true;
 592   else
 593     l->looping = false;
 594
 595   /* If this function does not return normally or does not bind local,
 596      do not touch this unless it has been marked as const or pure by the
 597      front end.  */
 598   if (TREE_THIS_VOLATILE (decl)
 599       || !targetm.binds_local_p (decl))
 600     {
 601       l->pure_const_state = IPA_NEITHER;
 602       return;
 603     }
 604
 605   if (TREE_READONLY (decl))
 606     {
 607       l->pure_const_state = IPA_CONST;
 608       l->state_set_in_source = true;
 609     }
 610   if (DECL_PURE_P (decl))
 611     {
 612       l->pure_const_state = IPA_PURE;
 613       l->state_set_in_source = true;
 614     }
 615
 616   if (dump_file)
 617     {
 618       fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ",
 619                cgraph_node_name (fn),
 620                l->pure_const_state);
 621     }
 622
 623   if (!l->state_set_in_source)
 624     {
 625       struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 626       basic_block this_block;
 627
 628       FOR_EACH_BB_FN (this_block, this_cfun)
 629         {
 630           gimple_stmt_iterator gsi;
 631           struct walk_stmt_info wi;
 632
 633           memset (&wi, 0, sizeof(wi));
 634           for (gsi = gsi_start_bb (this_block);
 635                !gsi_end_p (gsi);
 636                gsi_next (&gsi))
 637             {
 638               wi.info = fn;
 639               wi.pset = visited_nodes;
 640               walk_gimple_stmt (&gsi, scan_function_stmt, scan_function_op,
 641                                 &wi);
 642               if (l->pure_const_state == IPA_NEITHER)
 643                 goto end;
 644             }
 645         }
 646
 647       if (l->pure_const_state != IPA_NEITHER)
 648         {
 649           tree old_decl = current_function_decl;
 650           /* Const functions cannot have back edges (an
 651              indication of possible infinite loop side
 652              effect.  */
 653
 654           current_function_decl = fn->decl;
 655
 656           /* The C++ front end, has a tendency to some times jerk away
 657              a function after it has created it.  This should have
 658              been fixed.  */
 659           gcc_assert (DECL_STRUCT_FUNCTION (fn->decl));
 660
 661           push_cfun (DECL_STRUCT_FUNCTION (fn->decl));
 662
 663           if (mark_dfs_back_edges ())
 664             l->pure_const_state = IPA_NEITHER;
 665
 666           current_function_decl = old_decl;
 667           pop_cfun ();
 668         }
 669     }
 670
 671 end:
 672   if (dump_file)
 673     {
 674       fprintf (dump_file, "after local analysis of %s with initial value = %d\n ",
 675                cgraph_node_name (fn),
 676                l->pure_const_state);
 677     }
 678 }
 679
 680 \f
 681 /* Analyze each function in the cgraph to see if it is locally PURE or
 682    CONST.  */
 683
 684 static void
 685 generate_summary (void)
 686 {
 687   struct cgraph_node *node;
 688
 689   init_state ();
 690   /* There are some shared nodes, in particular the initializers on
 691      static declarations.  We do not need to scan them more than once
 692      since all we would be interested in are the addressof
 693      operations.  */
 694   visited_nodes = pointer_set_create ();
 695
 696   /* Process all of the functions.
 697
 698      We do not want to process any of the clones so we check that this
 699      is a master clone.  However, we do NOT process any
 700      AVAIL_OVERWRITABLE functions (these are never clones) we cannot
 701      guarantee that what we learn about the one we see will be true
 702      for the one that overrides it.
 703   */
 704   for (node = cgraph_nodes; node; node = node->next)
 705     if (node->analyzed && cgraph_is_master_clone (node))
 706       analyze_function (node);
 707
 708   pointer_set_destroy (visited_nodes);
 709   visited_nodes = NULL;
 710 }
 711
 712 /* Produce the global information by preforming a transitive closure
 713    on the local information that was produced by generate_summary.
 714    Note that there is no function_transform pass since this only
 715    updates the function_decl.  */
 716
 717 static unsigned int
 718 propagate (void)
 719 {
 720   struct cgraph_node *node;
 721   struct cgraph_node *w;
 722   struct cgraph_node **order =
 723     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 724   int order_pos;
 725   int i;
 726   struct ipa_dfs_info * w_info;
 727
 728   order_pos = ipa_utils_reduced_inorder (order, true, false);
 729   if (dump_file)
 730     {
 731       dump_cgraph (dump_file);
 732       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 733     }
 734
 735   /* Propagate the local information thru the call graph to produce
 736      the global information.  All the nodes within a cycle will have
 737      the same info so we collapse cycles first.  Then we can do the
 738      propagation in one pass from the leaves to the roots.  */
 739   for (i = 0; i < order_pos; i++ )
 740     {
 741       enum pure_const_state_e pure_const_state = IPA_CONST;
 742       bool looping = false;
 743       int count = 0;
 744       node = order[i];
 745
 746       /* Find the worst state for any node in the cycle.  */
 747       w = node;
 748       while (w)
 749         {
 750           funct_state w_l = get_function_state (w);
 751           if (pure_const_state < w_l->pure_const_state)
 752             pure_const_state = w_l->pure_const_state;
 753
 754           if (w_l->looping)
 755             looping = true;
 756
 757           if (pure_const_state == IPA_NEITHER)
 758             break;
 759
 760           if (!w_l->state_set_in_source)
 761             {
 762               struct cgraph_edge *e;
 763               count++;
 764
 765               if (count > 1)
 766                 looping = true;
 767
 768               for (e = w->callees; e; e = e->next_callee)
 769                 {
 770                   struct cgraph_node *y = e->callee;
 771                   /* Only look at the master nodes and skip external nodes.  */
 772                   y = cgraph_master_clone (y);
 773
 774                   if (w == y)
 775                     looping = true;
 776                   if (y)
 777                     {
 778                       funct_state y_l = get_function_state (y);
 779                       if (pure_const_state < y_l->pure_const_state)
 780                         pure_const_state = y_l->pure_const_state;
 781                       if (pure_const_state == IPA_NEITHER)
 782                         break;
 783                       if (y_l->looping)
 784                         looping = true;
 785                     }
 786                 }
 787             }
 788           w_info = (struct ipa_dfs_info *) w->aux;
 789           w = w_info->next_cycle;
 790         }
 791
 792       /* Copy back the region's pure_const_state which is shared by
 793          all nodes in the region.  */
 794       w = node;
 795       while (w)
 796         {
 797           funct_state w_l = get_function_state (w);
 798
 799           /* All nodes within a cycle share the same info.  */
 800           if (!w_l->state_set_in_source)
 801             {
 802               w_l->pure_const_state = pure_const_state;
 803               w_l->looping = looping;
 804
 805               switch (pure_const_state)
 806                 {
 807                 case IPA_CONST:
 808                   TREE_READONLY (w->decl) = 1;
 809                   DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
 810                   if (dump_file)
 811                     fprintf (dump_file, "Function found to be %sconst: %s\n",
 812                              looping ? "looping " : "",
 813                              lang_hooks.decl_printable_name(w->decl, 2));
 814                   break;
 815
 816                 case IPA_PURE:
 817                   DECL_PURE_P (w->decl) = 1;
 818                   DECL_LOOPING_CONST_OR_PURE_P (w->decl) = looping;
 819                   if (dump_file)
 820                     fprintf (dump_file, "Function found to be %spure: %s\n",
 821                              looping ? "looping " : "",
 822                              lang_hooks.decl_printable_name(w->decl, 2));
 823                   break;
 824
 825                 default:
 826                   break;
 827                 }
 828             }
 829           w_info = (struct ipa_dfs_info *) w->aux;
 830           w = w_info->next_cycle;
 831         }
 832     }
 833
 834   /* Cleanup. */
 835   for (node = cgraph_nodes; node; node = node->next)
 836     {
 837       /* Get rid of the aux information.  */
 838       if (node->aux)
 839         {
 840           w_info = (struct ipa_dfs_info *) node->aux;
 841           free (node->aux);
 842           node->aux = NULL;
 843         }
 844       if (node->analyzed && cgraph_is_master_clone (node))
 845         free (get_function_state (node));
 846     }
 847
 848   free (order);
 849   finish_state ();
 850   return 0;
 851 }
 852
 853 static bool
 854 gate_pure_const (void)
 855 {
 856   return (flag_ipa_pure_const
 857           /* Don't bother doing anything if the program has errors.  */
 858           && !(errorcount || sorrycount));
 859 }
 860
 861 struct ipa_opt_pass pass_ipa_pure_const =
 862 {
 863  {
 864   IPA_PASS,
 865   "pure-const",                         /* name */
 866   gate_pure_const,                      /* gate */
 867   propagate,                            /* execute */
 868   NULL,                                 /* sub */
 869   NULL,                                 /* next */
 870   0,                                    /* static_pass_number */
 871   TV_IPA_PURE_CONST,                    /* tv_id */
 872   0,                                    /* properties_required */
 873   0,                                    /* properties_provided */
 874   0,                                    /* properties_destroyed */
 875   0,                                    /* todo_flags_start */
 876   0                                     /* todo_flags_finish */
 877  },
 878  generate_summary,                      /* generate_summary */
 879  NULL,                                  /* write_summary */
 880  NULL,                                  /* read_summary */
 881  NULL,                                  /* function_read_summary */
 882  0,                                     /* TODOs */
 883  NULL,                                  /* function_transform */
 884  NULL                                   /* variable_transform */
 885 };