OSDN Git Service

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