OSDN Git Service

e5ff3a7725346121b75c31e7aa92aa44b4585f99
[pf3gnuchains/gcc-fork.git] / 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 to lp %i\n",
350                        lookup_stmt_eh_lp (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 };