OSDN Git Service

cdbf94be8aba6ad9ff8d065559b091619222a844
[pf3gnuchains/gcc-fork.git] / gcc / ipa-prop.c
1 /* Interprocedural analyses.
2    Copyright (C) 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "langhooks.h"
26 #include "ggc.h"
27 #include "target.h"
28 #include "cgraph.h"
29 #include "ipa-prop.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "flags.h"
33 #include "timevar.h"
34
35 /* This file contains interfaces that can be used for various IPA 
36    optimizations:
37
38    - ipa_methodlist interface - It is used to create and handle a temporary 
39    worklist used in  the propagation stage of IPCP. (can be used for more 
40    IPA optimizations).  
41
42    - ipa_callsite interface - for each callsite this interface creates and 
43    handles ipa_edge structure associated with it.
44
45    - ipa_method interface - for each method this interface creates and 
46    handles ipa_node structure associated with it.  */
47
48 /* ipa_methodlist interface.  */
49
50 /* Create a new worklist node.  */
51 static inline ipa_methodlist_p
52 ipa_create_methodlist_node (void)
53 {
54   return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist));
55 }
56
57 /* Return true if worklist WL is empty.  */
58 bool
59 ipa_methodlist_not_empty (ipa_methodlist_p wl)
60 {
61   return (wl != NULL);
62 }
63
64 /* Return the method in worklist element WL.  */
65 static inline struct cgraph_node *
66 ipa_methodlist_method (ipa_methodlist_p wl)
67 {
68   return wl->method_p;
69 }
70
71 /* Make worklist element WL point to method MT in the callgraph.  */
72 static inline void
73 ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt)
74 {
75   wl->method_p = mt;
76 }
77
78 /* Return the next element in the worklist following worklist 
79    element WL.  */
80 static inline ipa_methodlist_p
81 ipa_methodlist_next_method (ipa_methodlist_p wl)
82 {
83   return wl->next_method;
84 }
85
86 /* Set worklist element WL1 to point to worklist element WL2.  */
87 static inline void
88 ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2)
89 {
90   wl1->next_method = wl2;
91 }
92
93 /* Initialize worklist to contain all methods.  */
94 ipa_methodlist_p
95 ipa_methodlist_init (void)
96 {
97   struct cgraph_node *node;
98   ipa_methodlist_p wl;
99
100   wl = NULL;
101   for (node = cgraph_nodes; node; node = node->next)
102     ipa_add_method (&wl, node);
103
104   return wl;
105 }
106
107 /* Add method MT to the worklist. Set worklist element WL  
108    to point to MT.  */
109 void
110 ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt)
111 {
112   ipa_methodlist_p temp;
113
114   temp = ipa_create_methodlist_node ();
115   ipa_methodlist_method_set (temp, mt);
116   ipa_methodlist_next_method_set (temp, *wl);
117   *wl = temp;
118 }
119
120 /* Remove a method from the worklist. WL points to the first 
121    element in the list, which is removed.  */
122 struct cgraph_node *
123 ipa_remove_method (ipa_methodlist_p * wl)
124 {
125   ipa_methodlist_p first;
126   struct cgraph_node *return_method;
127
128   first = *wl;
129   *wl = ipa_methodlist_next_method (*wl);
130   return_method = ipa_methodlist_method (first);
131   free (first);
132   return return_method;
133 }
134
135 /* ipa_method interface.  */
136
137 /* Return number of formals of method MT.  */
138 int
139 ipa_method_formal_count (struct cgraph_node *mt)
140 {
141   return IPA_NODE_REF (mt)->ipa_arg_num;
142 }
143
144 /* Set number of formals of method MT to I.  */
145 void
146 ipa_method_formal_count_set (struct cgraph_node *mt, int i)
147 {
148   IPA_NODE_REF (mt)->ipa_arg_num = i;
149 }
150
151 /* Return whether I-th formal of MT is modified in MT.  */
152 static inline bool
153 ipa_method_is_modified (struct cgraph_node *mt, int i)
154 {
155   return IPA_NODE_REF (mt)->ipa_mod[i];
156 }
157
158 /* Return the tree of I-th formal of MT.  */
159 tree
160 ipa_method_get_tree (struct cgraph_node *mt, int i)
161 {
162   return IPA_NODE_REF (mt)->ipa_param_tree[i];
163 }
164
165 /* Create tree map structure for MT.  */
166 static inline void
167 ipa_method_tree_map_create (struct cgraph_node *mt)
168 {
169   IPA_NODE_REF (mt)->ipa_param_tree =
170     xcalloc (ipa_method_formal_count (mt), sizeof (tree));
171 }
172
173 /* Create modify structure for MT.  */
174 static inline void
175 ipa_method_modify_create (struct cgraph_node *mt)
176 {
177   ((struct ipa_node *) mt->aux)->ipa_mod =
178     xcalloc (ipa_method_formal_count (mt), sizeof (bool));
179 }
180
181 /* Set modify of I-th formal of MT to VAL.  */
182 static inline void
183 ipa_method_modify_set (struct cgraph_node *mt, int i, bool val)
184 {
185   IPA_NODE_REF (mt)->ipa_mod[i] = val;
186 }
187
188 /* Return index of the formal whose tree is PTREE in method MT.  */
189 static int
190 ipa_method_tree_map (struct cgraph_node *mt, tree ptree)
191 {
192   int i, count;
193
194   count = ipa_method_formal_count (mt);
195   for (i = 0; i < count; i++)
196     if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree)
197       return i;
198
199   return -1;
200 }
201
202 /* Insert the formal trees to the ipa_param_tree array in method MT.  */
203 void
204 ipa_method_compute_tree_map (struct cgraph_node *mt)
205 {
206   tree fndecl;
207   tree fnargs;
208   tree parm;
209   int param_num;
210
211   ipa_method_tree_map_create (mt);
212   fndecl = mt->decl;
213   fnargs = DECL_ARGUMENTS (fndecl);
214   param_num = 0;
215   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
216     {
217       IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm;
218       param_num++;
219     }
220 }
221
222 /* Count number of formals in MT. Insert the result to the 
223    ipa_node.  */
224 void
225 ipa_method_formal_compute_count (struct cgraph_node *mt)
226 {
227   tree fndecl;
228   tree fnargs;
229   tree parm;
230   int param_num;
231
232   fndecl = mt->decl;
233   fnargs = DECL_ARGUMENTS (fndecl);
234   param_num = 0;
235   for (parm = fnargs; parm; parm = TREE_CHAIN (parm))
236     param_num++;
237   ipa_method_formal_count_set (mt, param_num);
238 }
239
240 /* Check STMT to detect whether a formal is modified within MT,
241    the appropriate entry is updated in the ipa_mod array of ipa_node
242    (associated with MT).  */
243 static void
244 ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt)
245 {
246   int i, j;
247
248   switch (TREE_CODE (stmt))
249     {
250     case MODIFY_EXPR:
251       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL)
252         {
253           i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0));
254           if (i >= 0)
255             ipa_method_modify_set (mt, i, true);
256         }
257       break;
258     case ASM_EXPR:
259       /* Asm code could modify any of the parameters.  */
260       for (j = 0; j < ipa_method_formal_count (mt); j++)
261         ipa_method_modify_set (mt, j, true);
262       break;
263     default:
264       break;
265     }
266 }
267
268 /* Initialize ipa_mod array of MT.  */
269 static void
270 ipa_method_modify_init (struct cgraph_node *mt)
271 {
272   int i, count;
273
274   ipa_method_modify_create (mt);
275   count = ipa_method_formal_count (mt);
276   for (i = 0; i < count; i++)
277     ipa_method_modify_set (mt, i, false);
278 }
279
280 /* The modify computation driver for MT. Compute which formal arguments 
281    of method MT are locally modified.  Formals may be modified in MT 
282    if their address is taken, or if
283    they appear on the left hand side of an assignment.  */
284 void
285 ipa_method_compute_modify (struct cgraph_node *mt)
286 {
287   tree decl;
288   tree body;
289   int j, count;
290   basic_block bb;
291   struct function *func;
292   block_stmt_iterator bsi;
293   tree stmt, parm_tree;
294
295   ipa_method_modify_init (mt);
296   decl = mt->decl;
297   count = ipa_method_formal_count (mt);
298   /* ??? Handle pending sizes case. Set all parameters 
299      of the method to be modified.  */
300   if (DECL_UNINLINABLE (decl))
301     {
302       for (j = 0; j < count; j++)
303         ipa_method_modify_set (mt, j, true);
304       return;
305     }
306   /* Formals whose address is taken are considered modified.  */
307   for (j = 0; j < count; j++)
308     {
309       parm_tree = ipa_method_get_tree (mt, j);
310       if (TREE_ADDRESSABLE (parm_tree))
311         ipa_method_modify_set (mt, j, true);
312     }
313   body = DECL_SAVED_TREE (decl);
314   if (body != NULL)
315     {
316       func = DECL_STRUCT_FUNCTION (decl);
317       FOR_EACH_BB_FN (bb, func)
318       {
319         for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
320           {
321             stmt = bsi_stmt (bsi);
322             ipa_method_modify_stmt (mt, stmt);
323           }
324       }
325     }
326 }
327
328
329 /* ipa_callsite interface.  */
330
331 /* Return number of arguments in callsite CS.  */
332 int
333 ipa_callsite_param_count (struct cgraph_edge *cs)
334 {
335   return IPA_EDGE_REF (cs)->ipa_param_num;
336 }
337
338 /* Set number of arguments in callsite CS to I.  */
339 void
340 ipa_callsite_param_count_set (struct cgraph_edge *cs, int i)
341 {
342   IPA_EDGE_REF (cs)->ipa_param_num = i;
343 }
344
345 /* Return the jump function (ipa_jump_func struct) for argument I of 
346    callsite CS.  */
347 struct ipa_jump_func *
348 ipa_callsite_param (struct cgraph_edge *cs, int i)
349 {
350   return &(IPA_EDGE_REF (cs)->ipa_param_map[i]);
351 }
352
353 /* return the callee (cgraph_node) of callsite CS.  */
354 struct cgraph_node *
355 ipa_callsite_callee (struct cgraph_edge *cs)
356 {
357   return cs->callee;
358 }
359
360 /* Set field 'type' of jump function (ipa_jump_func struct) of argument I 
361    in callsite CS.  */
362 static inline void
363 ipa_callsite_param_set_type (struct cgraph_edge *cs, int i,
364                              enum jump_func_type type1)
365 {
366   IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1;
367 }
368
369 /* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct)
370    of argument I of callsite CS.  */
371 static inline void
372 ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i,
373                                          unsigned int formal)
374 {
375   ipa_callsite_param (cs, i)->info_type.formal_id = formal;
376 }
377
378 /* Set int-valued INFO_TYPE1 as 'info_type' field of 
379    jump function (ipa_jump_func struct) of argument I of callsite CS.  */
380 static inline void
381 ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1)
382 {
383   ipa_callsite_param (cs, i)->info_type.value = info_type1;
384 }
385
386 /* Allocate space for callsite CS.  */
387 static inline void
388 ipa_callsite_param_map_create (struct cgraph_edge *cs)
389 {
390   IPA_EDGE_REF (cs)->ipa_param_map =
391     xcalloc (ipa_callsite_param_count (cs), sizeof (struct ipa_jump_func));
392 }
393
394 /* Return the call expr tree related to callsite CS.  */
395 static inline tree
396 ipa_callsite_tree (struct cgraph_edge *cs)
397 {
398   return cs->call_stmt;
399 }
400
401 /* Return the caller (cgraph_node) of CS.  */
402 static inline struct cgraph_node *
403 ipa_callsite_caller (struct cgraph_edge *cs)
404 {
405   return cs->caller;
406 }
407
408 /* Count number of arguments callsite CS has and store it in 
409    ipa_edge structure corresponding to this callsite.  */
410 void
411 ipa_callsite_compute_count (struct cgraph_edge *cs)
412 {
413   tree call_tree;
414   tree arg;
415   int arg_num;
416
417   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
418   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
419   arg = TREE_OPERAND (call_tree, 1);
420   arg_num = 0;
421   for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
422     arg_num++;
423   ipa_callsite_param_count_set (cs, arg_num);
424 }
425
426 /* Compute jump function for all arguments of callsite CS 
427    and insert the information in the ipa_param_map array 
428    in the ipa_edge corresponding to this callsite. (Explanation 
429    on jump functions is in ipa-prop.h).  */
430 void
431 ipa_callsite_compute_param (struct cgraph_edge *cs)
432 {
433   tree call_tree;
434   tree arg, cst_decl, arg_type, formal_type;
435   int arg_num;
436   int i;
437   struct cgraph_node *mt;
438
439   if (ipa_callsite_param_count (cs) == 0)
440     return;
441   ipa_callsite_param_map_create (cs);
442   call_tree = get_call_expr_in (ipa_callsite_tree (cs));
443   gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);
444   arg = TREE_OPERAND (call_tree, 1);
445   arg_num = 0;
446
447   for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))
448     {
449       /* If the formal parameter was passed as argument, we store 
450          FORMAL_IPATYPE and its index in the caller as the jump function 
451          of this argument.  */
452       if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL)
453         {
454           mt = ipa_callsite_caller (cs);
455           i = ipa_method_tree_map (mt, TREE_VALUE (arg));
456           if (i < 0 || ipa_method_is_modified (mt, i))
457             ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
458           else
459             {
460                 arg_type = TREE_TYPE (TREE_VALUE (arg));
461                 formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
462                 if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
463                     && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
464                     && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
465                                              TYPE_ATTRIBUTES (formal_type)))
466                   {
467                     ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
468                     ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
469                   }
470                 else
471                   ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
472             }
473         }
474       /* If a constant value was passed as argument, 
475          we store CONST_IPATYPE and its value as the jump function 
476          of this argument.  */
477       else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST
478                || TREE_CODE (TREE_VALUE (arg)) == REAL_CST)
479         {
480           arg_type = TREE_TYPE (TREE_VALUE (arg));
481           formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
482           if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
483               && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
484               && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
485                                        TYPE_ATTRIBUTES (formal_type)))
486             {
487               ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
488               ipa_callsite_param_set_info_type (cs, arg_num, TREE_VALUE (arg));
489             }
490           else
491             ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
492         }
493       /* This is for the case of Fortran. If the address of a const_decl 
494          was passed as argument then we store 
495          CONST_IPATYPE_REF/CONST_IPATYPE_REF and the costant 
496          value as the jump function corresponding to this argument.  */
497       else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR
498                && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) ==
499                CONST_DECL)
500         {
501           cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0);
502           arg_type = TREE_TYPE (DECL_INITIAL (cst_decl));
503           formal_type =
504             TREE_TYPE (TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num)));
505           if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
506               || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)
507             {
508               if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
509                   && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
510                   && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
511                                            TYPE_ATTRIBUTES (formal_type)))
512
513                 {
514                   ipa_callsite_param_set_type (cs, arg_num,
515                                                CONST_IPATYPE_REF);
516                   ipa_callsite_param_set_info_type (cs, arg_num, DECL_INITIAL (cst_decl));
517
518                 }
519               else
520                 ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
521             }
522         }
523       else
524         ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
525       arg_num++;
526     }
527 }
528
529 /* Return type of jump function JF.  */
530 enum jump_func_type
531 get_type (struct ipa_jump_func *jf)
532 {
533   return jf->type;
534 }
535
536 /* Return info type of jump function JF.  */
537 union parameter_info *
538 ipa_jf_get_info_type (struct ipa_jump_func *jf)
539 {
540   return &(jf->info_type);
541 }
542
543 /* Allocate and initialize ipa_node structure.  
544    cgraph_node NODE points to the new allocated ipa_node.  */
545 void
546 ipa_node_create (struct cgraph_node *node)
547 {
548   node->aux = xcalloc (1, sizeof (struct ipa_node));
549 }
550
551 /* Allocate and initialize ipa_node structure for all
552    nodes in callgraph.  */
553 void
554 ipa_nodes_create (void)
555 {
556   struct cgraph_node *node;
557
558   for (node = cgraph_nodes; node; node = node->next)
559     ipa_node_create (node);
560 }
561
562 /* Allocate and initialize ipa_edge structure.  */
563 void
564 ipa_edges_create (void)
565 {
566   struct cgraph_node *node;
567   struct cgraph_edge *cs;
568
569   for (node = cgraph_nodes; node; node = node->next)
570     for (cs = node->callees; cs; cs = cs->next_callee)
571       cs->aux = xcalloc (1, sizeof (struct ipa_edge));
572 }
573
574 /* Free ipa_node structure.  */
575 void
576 ipa_nodes_free (void)
577 {
578   struct cgraph_node *node;
579
580   for (node = cgraph_nodes; node; node = node->next)
581     {
582       free (node->aux);
583       node->aux = NULL;
584     }
585 }
586
587 /* Free ipa_edge structure.  */
588 void
589 ipa_edges_free (void)
590 {
591   struct cgraph_node *node;
592   struct cgraph_edge *cs;
593
594   for (node = cgraph_nodes; node; node = node->next)
595     for (cs = node->callees; cs; cs = cs->next_callee)
596       {
597         free (cs->aux);
598         cs->aux = NULL;
599       }
600 }
601
602 /* Free ipa data structures of ipa_node and ipa_edge.  */
603 void
604 ipa_free (void)
605 {
606   struct cgraph_node *node;
607   struct cgraph_edge *cs;
608
609   for (node = cgraph_nodes; node; node = node->next)
610     {
611       if (node->aux == NULL)
612         continue;
613       if (IPA_NODE_REF (node)->ipcp_cval)
614         free (IPA_NODE_REF (node)->ipcp_cval);
615       if (IPA_NODE_REF (node)->ipa_param_tree)
616         free (IPA_NODE_REF (node)->ipa_param_tree);
617       if (IPA_NODE_REF (node)->ipa_mod)
618         free (IPA_NODE_REF (node)->ipa_mod);
619       for (cs = node->callees; cs; cs = cs->next_callee)
620         {
621           if (cs->aux)
622             if (IPA_EDGE_REF (cs)->ipa_param_map)
623               free (IPA_EDGE_REF (cs)->ipa_param_map);
624         }
625     }
626 }
627
628 /* Print ipa_tree_map data structures of all methods in the 
629    callgraph to F.  */
630 void
631 ipa_method_tree_print (FILE * f)
632 {
633   int i, count;
634   tree temp;
635   struct cgraph_node *node;
636
637   fprintf (f, "\nPARAM TREE MAP PRINT\n");
638   for (node = cgraph_nodes; node; node = node->next)
639     {
640       fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));
641       count = ipa_method_formal_count (node);
642       for (i = 0; i < count; i++)
643         {
644           temp = ipa_method_get_tree (node, i);
645           if (TREE_CODE (temp) == PARM_DECL)
646             fprintf (f, "  param [%d] : %s\n", i,
647                      (*lang_hooks.decl_printable_name) (temp, 2));
648         }
649
650     }
651 }
652
653 /* Print ipa_modify data structures of all methods in the 
654    callgraph to F.  */
655 void
656 ipa_method_modify_print (FILE * f)
657 {
658   int i, count;
659   bool temp;
660   struct cgraph_node *node;
661
662   fprintf (f, "\nMODIFY PRINT\n");
663   for (node = cgraph_nodes; node; node = node->next)
664     {
665       fprintf (f, "method  %s :: \n", cgraph_node_name (node));
666       count = ipa_method_formal_count (node);
667       for (i = 0; i < count; i++)
668         {
669           temp = ipa_method_is_modified (node, i);
670           if (temp)
671             fprintf (f, " param [%d] true \n", i);
672           else
673             fprintf (f, " param [%d] false \n", i);
674         }
675     }
676 }