OSDN Git Service

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