OSDN Git Service

* cgraph.c (cgraph_clone_node): Add redirect_callers parameter.
[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 /* Return true if NODE is self recursive function.  */
692
693 static bool
694 self_recursive_p (struct cgraph_node *node)
695 {
696   struct cgraph_edge *e;
697   for (e = node->callees; e; e = e->next_callee)
698     if (e->callee == node)
699       return true;
700   return false;
701 }
702
703 /* Produce the global information by preforming a transitive closure
704    on the local information that was produced by generate_summary.
705    Note that there is no function_transform pass since this only
706    updates the function_decl.  */
707
708 static unsigned int
709 propagate (void)
710 {
711   struct cgraph_node *node;
712   struct cgraph_node *w;
713   struct cgraph_node **order =
714     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
715   int order_pos;
716   int i;
717   struct ipa_dfs_info * w_info;
718
719   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
720   cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
721   cgraph_remove_node_removal_hook (node_removal_hook_holder);
722   order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
723   if (dump_file)
724     {
725       dump_cgraph (dump_file);
726       ipa_utils_print_order(dump_file, "reduced", order, order_pos);
727     }
728
729   /* Propagate the local information thru the call graph to produce
730      the global information.  All the nodes within a cycle will have
731      the same info so we collapse cycles first.  Then we can do the
732      propagation in one pass from the leaves to the roots.  */
733   for (i = 0; i < order_pos; i++ )
734     {
735       enum pure_const_state_e pure_const_state = IPA_CONST;
736       bool looping = false;
737       int count = 0;
738       node = order[i];
739
740       /* Find the worst state for any node in the cycle.  */
741       w = node;
742       while (w)
743         {
744           struct cgraph_edge *e;
745           funct_state w_l = get_function_state (w);
746           if (pure_const_state < w_l->pure_const_state)
747             pure_const_state = w_l->pure_const_state;
748
749           if (w_l->looping)
750             looping = true;
751
752           if (pure_const_state == IPA_NEITHER)
753             break;
754
755           count++;
756
757           if (count > 1)
758             looping = true;
759                 
760           for (e = w->callees; e; e = e->next_callee) 
761             {
762               struct cgraph_node *y = e->callee;
763
764               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
765                 {
766                   funct_state y_l = get_function_state (y);
767                   if (pure_const_state < y_l->pure_const_state)
768                     pure_const_state = y_l->pure_const_state;
769                   if (pure_const_state == IPA_NEITHER)
770                     break;
771                   if (y_l->looping)
772                     looping = true;
773                 }
774             }
775           w_info = (struct ipa_dfs_info *) w->aux;
776           w = w_info->next_cycle;
777         }
778
779       /* Copy back the region's pure_const_state which is shared by
780          all nodes in the region.  */
781       w = node;
782       while (w)
783         {
784           funct_state w_l = get_function_state (w);
785           enum pure_const_state_e this_state = pure_const_state;
786           bool this_looping = looping;
787
788           if (w_l->state_previously_known != IPA_NEITHER
789               && this_state > w_l->state_previously_known)
790             this_state = w_l->state_previously_known;
791           if (!this_looping && self_recursive_p (w))
792             this_looping = true;
793           if (!w_l->looping_previously_known)
794             this_looping = false;
795
796           /* All nodes within a cycle share the same info.  */
797           w_l->pure_const_state = this_state;
798           w_l->looping = this_looping;
799
800           switch (this_state)
801             {
802             case IPA_CONST:
803               if (!TREE_READONLY (w->decl) && dump_file)
804                 fprintf (dump_file, "Function found to be %sconst: %s\n",  
805                          this_looping ? "looping " : "",
806                          cgraph_node_name (w)); 
807               TREE_READONLY (w->decl) = 1;
808               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
809               break;
810               
811             case IPA_PURE:
812               if (!DECL_PURE_P (w->decl) && dump_file)
813                 fprintf (dump_file, "Function found to be %spure: %s\n",  
814                          this_looping ? "looping " : "",
815                          cgraph_node_name (w)); 
816               DECL_PURE_P (w->decl) = 1;
817               DECL_LOOPING_CONST_OR_PURE_P (w->decl) = this_looping;
818               break;
819               
820             default:
821               break;
822             }
823           w_info = (struct ipa_dfs_info *) w->aux;
824           w = w_info->next_cycle;
825         }
826     }
827
828   /* Cleanup. */
829   for (node = cgraph_nodes; node; node = node->next)
830     {
831       /* Get rid of the aux information.  */
832       if (node->aux)
833         {
834           w_info = (struct ipa_dfs_info *) node->aux;
835           free (node->aux);
836           node->aux = NULL;
837         }
838     }
839   order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
840   if (dump_file)
841     {
842       dump_cgraph (dump_file);
843       ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
844     }
845   /* Propagate the local information thru the call graph to produce
846      the global information.  All the nodes within a cycle will have
847      the same info so we collapse cycles first.  Then we can do the
848      propagation in one pass from the leaves to the roots.  */
849   for (i = 0; i < order_pos; i++ )
850     {
851       bool can_throw = false;
852       node = order[i];
853
854       /* Find the worst state for any node in the cycle.  */
855       w = node;
856       while (w)
857         {
858           struct cgraph_edge *e;
859           funct_state w_l = get_function_state (w);
860
861           if (w_l->can_throw)
862             can_throw = true;
863
864           if (can_throw)
865             break;
866                 
867           for (e = w->callees; e; e = e->next_callee) 
868             {
869               struct cgraph_node *y = e->callee;
870
871               if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
872                 {
873                   funct_state y_l = get_function_state (y);
874
875                   if (can_throw) 
876                     break;
877                   if (y_l->can_throw && !TREE_NOTHROW (w->decl)
878                       && e->can_throw_external)
879                     can_throw = true;
880                 }
881             }
882           w_info = (struct ipa_dfs_info *) w->aux;
883           w = w_info->next_cycle;
884         }
885
886       /* Copy back the region's pure_const_state which is shared by
887          all nodes in the region.  */
888       w = node;
889       while (w)
890         {
891           funct_state w_l = get_function_state (w);
892           if (!can_throw && !TREE_NOTHROW (w->decl))
893             {
894               struct cgraph_edge *e;
895               TREE_NOTHROW (w->decl) = true;
896               for (e = w->callers; e; e = e->next_caller)
897                 e->can_throw_external = false;
898               if (dump_file)
899                 fprintf (dump_file, "Function found to be nothrow: %s\n",  
900                          cgraph_node_name (w));
901             }
902           else if (can_throw && !TREE_NOTHROW (w->decl))
903             w_l->can_throw = true;
904           w_info = (struct ipa_dfs_info *) w->aux;
905           w = w_info->next_cycle;
906         }
907     }
908
909   /* Cleanup. */
910   for (node = cgraph_nodes; node; node = node->next)
911     {
912       /* Get rid of the aux information.  */
913       if (node->aux)
914         {
915           w_info = (struct ipa_dfs_info *) node->aux;
916           free (node->aux);
917           node->aux = NULL;
918         }
919       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
920         free (get_function_state (node));
921     }
922   
923   free (order);
924   VEC_free (funct_state, heap, funct_state_vec);
925   finish_state ();
926   return 0;
927 }
928
929 static bool
930 gate_pure_const (void)
931 {
932   return (flag_ipa_pure_const
933           /* Don't bother doing anything if the program has errors.  */
934           && !(errorcount || sorrycount));
935 }
936
937 struct ipa_opt_pass_d pass_ipa_pure_const =
938 {
939  {
940   IPA_PASS,
941   "pure-const",                         /* name */
942   gate_pure_const,                      /* gate */
943   propagate,                            /* execute */
944   NULL,                                 /* sub */
945   NULL,                                 /* next */
946   0,                                    /* static_pass_number */
947   TV_IPA_PURE_CONST,                    /* tv_id */
948   0,                                    /* properties_required */
949   0,                                    /* properties_provided */
950   0,                                    /* properties_destroyed */
951   0,                                    /* todo_flags_start */
952   0                                     /* todo_flags_finish */
953  },
954  generate_summary,                      /* generate_summary */
955  NULL,                                  /* write_summary */
956  NULL,                                  /* read_summary */
957  NULL,                                  /* function_read_summary */
958  0,                                     /* TODOs */
959  NULL,                                  /* function_transform */
960  NULL                                   /* variable_transform */
961 };
962
963 /* Simple local pass for pure const discovery reusing the analysis from
964    ipa_pure_const.   This pass is effective when executed together with
965    other optimization passes in early optimization pass queue.  */
966
967 static unsigned int
968 local_pure_const (void)
969 {
970   bool changed = false;
971   funct_state l;
972
973   /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
974      we must not promote functions that are called by already processed functions.  */
975
976   if (function_called_by_processed_nodes_p ())
977     {
978       if (dump_file)
979         fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
980       return 0;
981     }
982
983   l = analyze_function (cgraph_node (current_function_decl), false);
984   if (!l)
985     {
986       if (dump_file)
987         fprintf (dump_file, "Function has wrong visibility; ignoring\n");
988       return 0;
989     }
990
991   switch (l->pure_const_state)
992     {
993     case IPA_CONST:
994       if (!TREE_READONLY (current_function_decl))
995         {
996           TREE_READONLY (current_function_decl) = 1;
997           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
998           changed = true;
999           if (dump_file)
1000             fprintf (dump_file, "Function found to be %sconst: %s\n",
1001                      l->looping ? "looping " : "",
1002                      lang_hooks.decl_printable_name (current_function_decl,
1003                                                      2));
1004         }
1005       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1006                && !l->looping)
1007         {
1008           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
1009           changed = true;
1010           if (dump_file)
1011             fprintf (dump_file, "Function found to be non-looping: %s\n",
1012                      lang_hooks.decl_printable_name (current_function_decl,
1013                                                      2));
1014         }
1015       break;
1016
1017     case IPA_PURE:
1018       if (!TREE_READONLY (current_function_decl))
1019         {
1020           DECL_PURE_P (current_function_decl) = 1;
1021           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = l->looping;
1022           changed = true;
1023           if (dump_file)
1024             fprintf (dump_file, "Function found to be %spure: %s\n",
1025                      l->looping ? "looping " : "",
1026                      lang_hooks.decl_printable_name (current_function_decl,
1027                                                      2));
1028         }
1029       else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1030                && !l->looping)
1031         {
1032           DECL_LOOPING_CONST_OR_PURE_P (current_function_decl) = false;
1033           changed = true;
1034           if (dump_file)
1035             fprintf (dump_file, "Function found to be non-looping: %s\n",
1036                      lang_hooks.decl_printable_name (current_function_decl,
1037                                                      2));
1038         }
1039       break;
1040
1041     default:
1042       break;
1043     }
1044   if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1045     {
1046       struct cgraph_edge *e;
1047
1048       TREE_NOTHROW (current_function_decl) = true;
1049       for (e = cgraph_node (current_function_decl)->callers;
1050            e; e = e->next_caller)
1051         e->can_throw_external = false;
1052       changed = true;
1053       if (dump_file)
1054         fprintf (dump_file, "Function found to be nothrow: %s\n",
1055                  lang_hooks.decl_printable_name (current_function_decl,
1056                                                  2));
1057     }
1058   if (l)
1059     free (l);
1060   if (changed)
1061     return execute_fixup_cfg ();
1062   else
1063     return 0;
1064 }
1065
1066 struct gimple_opt_pass pass_local_pure_const =
1067 {
1068  {
1069   GIMPLE_PASS,
1070   "local-pure-const",                   /* name */
1071   gate_pure_const,                      /* gate */
1072   local_pure_const,                     /* execute */
1073   NULL,                                 /* sub */
1074   NULL,                                 /* next */
1075   0,                                    /* static_pass_number */
1076   TV_IPA_PURE_CONST,                    /* tv_id */
1077   0,                                    /* properties_required */
1078   0,                                    /* properties_provided */
1079   0,                                    /* properties_destroyed */
1080   0,                                    /* todo_flags_start */
1081   0                                     /* todo_flags_finish */
1082  }
1083 };