OSDN Git Service

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