xref: /openbsd-src/gnu/gcc/gcc/ipa-cp.c (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
1 /* Interprocedural constant propagation
2    Copyright (C) 2005 Free Software Foundation, Inc.
3    Contributed by Razya Ladelsky <RAZYA@il.ibm.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 2, 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 COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21 
22 /* Interprocedural constant propagation.
23    The aim of interprocedural constant propagation (IPCP) is to find which
24    function's argument has the same constant value in each invocation throughout
25    the whole program. For example, for an application consisting of two files,
26    foo1.c, foo2.c:
27 
28    foo1.c contains :
29 
30    int f (int x)
31    {
32      g (x);
33    }
34    void main (void)
35    {
36      f (3);
37      h (3);
38    }
39 
40    foo2.c contains :
41 
42    int h (int y)
43    {
44      g (y);
45    }
46    int g (int y)
47    {
48      printf ("value is %d",y);
49    }
50 
51    The IPCP algorithm will find that g's formal argument y
52    is always called with the value 3.
53 
54    The algorithm used is based on "Interprocedural Constant Propagation",
55    by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86,
56    pg 152-161
57 
58    The optimization is divided into three stages:
59 
60    First stage - intraprocedural analysis
61    =======================================
62    This phase computes jump_function and modify information.
63 
64    A jump function for a callsite represents the values passed as actual
65    arguments
66    of the callsite. There are three types of values :
67    Formal - the caller's formal parameter is passed as an actual argument.
68    Constant - a constant is passed as a an actual argument.
69    Unknown - neither of the above.
70 
71    In order to compute the jump functions, we need the modify information for
72    the formal parameters of methods.
73 
74    The jump function info, ipa_jump_func, is defined in ipa_edge
75    structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
76    The modify info, ipa_modify, is defined in ipa_node structure
77    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
78 
79    -ipcp_init_stage() is the first stage driver.
80 
81    Second stage - interprocedural analysis
82    ========================================
83    This phase does the interprocedural constant propagation.
84    It computes for all formal parameters in the program
85    their cval value that may be:
86    TOP - unknown.
87    BOTTOM - non constant.
88    CONSTANT_TYPE - constant value.
89 
90    Cval of formal f will have a constant value if all callsites to this
91    function have the same constant value passed to f.
92 
93    The cval info, ipcp_formal, is defined in ipa_node structure
94    (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
95 
96    -ipcp_iterate_stage() is the second stage driver.
97 
98    Third phase - transformation of methods code
99    ============================================
100    Propagates the constant-valued formals into the function.
101    For each method mt, whose parameters are consts, we create a clone/version.
102 
103    We use two ways to annotate the versioned function with the constant
104    formal information:
105    1. We insert an assignment statement 'parameter = const' at the beginning
106    of the cloned method.
107    2. For read-only formals whose address is not taken, we replace all uses
108    of the formal with the constant (we provide versioning with an
109    ipa_replace_map struct representing the trees we want to replace).
110 
111    We also need to modify some callsites to call to the cloned methods instead
112    of the original ones. For a callsite passing an argument found to be a
113    constant by IPCP, there are two different cases to handle:
114    1. A constant is passed as an argument.
115    2. A parameter (of the caller) passed as an argument (pass through argument).
116 
117    In the first case, the callsite in the original caller should be redirected
118    to call the cloned callee.
119    In the second case, both the caller and the callee have clones
120    and the callsite of the cloned caller would be redirected to call to
121    the cloned callee.
122 
123    The callgraph is updated accordingly.
124 
125    This update is done in two stages:
126    First all cloned methods are created during a traversal of the callgraph,
127    during which all callsites are redirected to call the cloned method.
128    Then the callsites are traversed and updated as described above.
129 
130    -ipcp_insert_stage() is the third phase driver.
131 
132 */
133 
134 #include "config.h"
135 #include "system.h"
136 #include "coretypes.h"
137 #include "tree.h"
138 #include "target.h"
139 #include "cgraph.h"
140 #include "ipa-prop.h"
141 #include "tree-flow.h"
142 #include "tree-pass.h"
143 #include "flags.h"
144 #include "timevar.h"
145 #include "diagnostic.h"
146 
147 /* Get orig node field of ipa_node associated with method MT.  */
148 static inline struct cgraph_node *
ipcp_method_orig_node(struct cgraph_node * mt)149 ipcp_method_orig_node (struct cgraph_node *mt)
150 {
151   return IPA_NODE_REF (mt)->ipcp_orig_node;
152 }
153 
154 /* Return true if NODE is a cloned/versioned method.  */
155 static inline bool
ipcp_method_is_cloned(struct cgraph_node * node)156 ipcp_method_is_cloned (struct cgraph_node *node)
157 {
158   return (ipcp_method_orig_node (node) != NULL);
159 }
160 
161 /* Set ORIG_NODE in ipa_node associated with method NODE.  */
162 static inline void
ipcp_method_set_orig_node(struct cgraph_node * node,struct cgraph_node * orig_node)163 ipcp_method_set_orig_node (struct cgraph_node *node,
164 			   struct cgraph_node *orig_node)
165 {
166   IPA_NODE_REF (node)->ipcp_orig_node = orig_node;
167 }
168 
169 /* Create ipa_node and its data structures for NEW_NODE.
170    Set ORIG_NODE as the orig_node field in ipa_node.  */
171 static void
ipcp_cloned_create(struct cgraph_node * orig_node,struct cgraph_node * new_node)172 ipcp_cloned_create (struct cgraph_node *orig_node,
173 		    struct cgraph_node *new_node)
174 {
175   ipa_node_create (new_node);
176   ipcp_method_set_orig_node (new_node, orig_node);
177   ipa_method_formal_compute_count (new_node);
178   ipa_method_compute_tree_map (new_node);
179 }
180 
181 /* Return cval_type field of CVAL.  */
182 static inline enum cvalue_type
ipcp_cval_get_cvalue_type(struct ipcp_formal * cval)183 ipcp_cval_get_cvalue_type (struct ipcp_formal *cval)
184 {
185   return cval->cval_type;
186 }
187 
188 /* Return scale for MT.  */
189 static inline gcov_type
ipcp_method_get_scale(struct cgraph_node * mt)190 ipcp_method_get_scale (struct cgraph_node *mt)
191 {
192   return IPA_NODE_REF (mt)->count_scale;
193 }
194 
195 /* Set COUNT as scale for MT.  */
196 static inline void
ipcp_method_set_scale(struct cgraph_node * node,gcov_type count)197 ipcp_method_set_scale (struct cgraph_node *node, gcov_type count)
198 {
199   IPA_NODE_REF (node)->count_scale = count;
200 }
201 
202 /* Set TYPE as cval_type field of CVAL.  */
203 static inline void
ipcp_cval_set_cvalue_type(struct ipcp_formal * cval,enum cvalue_type type)204 ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type)
205 {
206   cval->cval_type = type;
207 }
208 
209 /* Return cvalue field of CVAL.  */
210 static inline union parameter_info *
ipcp_cval_get_cvalue(struct ipcp_formal * cval)211 ipcp_cval_get_cvalue (struct ipcp_formal *cval)
212 {
213   return &(cval->cvalue);
214 }
215 
216 /* Set VALUE as cvalue field  CVAL.  */
217 static inline void
ipcp_cval_set_cvalue(struct ipcp_formal * cval,union parameter_info * value,enum cvalue_type type)218 ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value,
219 		      enum cvalue_type type)
220 {
221   if (type == CONST_VALUE || type == CONST_VALUE_REF)
222     cval->cvalue.value =  value->value;
223 }
224 
225 /* Return whether TYPE is a constant type.  */
226 static bool
ipcp_type_is_const(enum cvalue_type type)227 ipcp_type_is_const (enum cvalue_type type)
228 {
229   if (type == CONST_VALUE || type == CONST_VALUE_REF)
230     return true;
231   else
232     return false;
233 }
234 
235 /* Return true if CONST_VAL1 and CONST_VAL2 are equal.  */
236 static inline bool
ipcp_cval_equal_cvalues(union parameter_info * const_val1,union parameter_info * const_val2,enum cvalue_type type1,enum cvalue_type type2)237 ipcp_cval_equal_cvalues (union parameter_info *const_val1,
238 			 union parameter_info *const_val2,
239 			 enum cvalue_type type1, enum cvalue_type type2)
240 {
241   gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2));
242   if (type1 != type2)
243     return false;
244 
245   if (operand_equal_p (const_val1->value, const_val2->value, 0))
246     return true;
247 
248   return false;
249 }
250 
251 /* Compute Meet arithmetics:
252    Meet (BOTTOM, x) = BOTTOM
253    Meet (TOP,x) = x
254    Meet (const_a,const_b) = BOTTOM,  if const_a != const_b.
255    MEET (const_a,const_b) = const_a, if const_a == const_b.*/
256 static void
ipcp_cval_meet(struct ipcp_formal * cval,struct ipcp_formal * cval1,struct ipcp_formal * cval2)257 ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1,
258 		struct ipcp_formal *cval2)
259 {
260   if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM
261       || ipcp_cval_get_cvalue_type (cval2) == BOTTOM)
262     {
263       ipcp_cval_set_cvalue_type (cval, BOTTOM);
264       return;
265     }
266   if (ipcp_cval_get_cvalue_type (cval1) == TOP)
267     {
268       ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2));
269       ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2),
270 			    ipcp_cval_get_cvalue_type (cval2));
271       return;
272     }
273   if (ipcp_cval_get_cvalue_type (cval2) == TOP)
274     {
275       ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
276       ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
277 			    ipcp_cval_get_cvalue_type (cval1));
278       return;
279     }
280   if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
281 				ipcp_cval_get_cvalue (cval2),
282 				ipcp_cval_get_cvalue_type (cval1),
283 				ipcp_cval_get_cvalue_type (cval2)))
284     {
285       ipcp_cval_set_cvalue_type (cval, BOTTOM);
286       return;
287     }
288   ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
289   ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
290 			ipcp_cval_get_cvalue_type (cval1));
291 }
292 
293 /* Return cval structure for the formal at index INFO_TYPE in MT.  */
294 static inline struct ipcp_formal *
ipcp_method_cval(struct cgraph_node * mt,int info_type)295 ipcp_method_cval (struct cgraph_node *mt, int info_type)
296 {
297   return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]);
298 }
299 
300 /* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.
301    If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is
302    drawn from MT.  */
303 static void
ipcp_cval_compute(struct ipcp_formal * cval,struct cgraph_node * mt,enum jump_func_type type,union parameter_info * info_type)304 ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt,
305 		   enum jump_func_type type, union parameter_info *info_type)
306 {
307   if (type == UNKNOWN_IPATYPE)
308     ipcp_cval_set_cvalue_type (cval, BOTTOM);
309   else if (type == CONST_IPATYPE)
310     {
311       ipcp_cval_set_cvalue_type (cval, CONST_VALUE);
312       ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE);
313     }
314   else if (type == CONST_IPATYPE_REF)
315     {
316       ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF);
317       ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF);
318     }
319   else if (type == FORMAL_IPATYPE)
320     {
321       enum cvalue_type type =
322 	ipcp_cval_get_cvalue_type (ipcp_method_cval
323 				   (mt, info_type->formal_id));
324       ipcp_cval_set_cvalue_type (cval, type);
325       ipcp_cval_set_cvalue (cval,
326 			    ipcp_cval_get_cvalue (ipcp_method_cval
327 						  (mt, info_type->formal_id)),
328 			    type);
329     }
330 }
331 
332 /* True when CVAL1 and CVAL2 values are not the same.  */
333 static bool
ipcp_cval_changed(struct ipcp_formal * cval1,struct ipcp_formal * cval2)334 ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2)
335 {
336   if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2))
337     {
338       if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE &&
339 	  ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF)
340 	return false;
341       if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
342 				   ipcp_cval_get_cvalue (cval2),
343 				   ipcp_cval_get_cvalue_type (cval1),
344 				   ipcp_cval_get_cvalue_type (cval2)))
345 	return false;
346     }
347   return true;
348 }
349 
350 /* Create cval structure for method MT.  */
351 static inline void
ipcp_formal_create(struct cgraph_node * mt)352 ipcp_formal_create (struct cgraph_node *mt)
353 {
354   IPA_NODE_REF (mt)->ipcp_cval =
355     XCNEWVEC (struct ipcp_formal, ipa_method_formal_count (mt));
356 }
357 
358 /* Set cval structure of I-th formal of MT to CVAL.  */
359 static inline void
ipcp_method_cval_set(struct cgraph_node * mt,int i,struct ipcp_formal * cval)360 ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval)
361 {
362   IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type;
363   ipcp_cval_set_cvalue (ipcp_method_cval (mt, i),
364 			ipcp_cval_get_cvalue (cval), cval->cval_type);
365 }
366 
367 /* Set type of cval structure of formal I of MT to CVAL_TYPE1.  */
368 static inline void
ipcp_method_cval_set_cvalue_type(struct cgraph_node * mt,int i,enum cvalue_type cval_type1)369 ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i,
370 				  enum cvalue_type cval_type1)
371 {
372   IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1;
373 }
374 
375 /* Print ipcp_cval data structures to F.  */
376 static void
ipcp_method_cval_print(FILE * f)377 ipcp_method_cval_print (FILE * f)
378 {
379   struct cgraph_node *node;
380   int i, count;
381   tree cvalue;
382 
383   fprintf (f, "\nCVAL PRINT\n");
384   for (node = cgraph_nodes; node; node = node->next)
385     {
386       fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node));
387       count = ipa_method_formal_count (node);
388       for (i = 0; i < count; i++)
389 	{
390 	  if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i))
391 	      == CONST_VALUE
392 	      || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) ==
393 	      CONST_VALUE_REF)
394 	    {
395 	      fprintf (f, " param [%d]: ", i);
396 	      fprintf (f, "type is CONST ");
397 	      cvalue =
398 		ipcp_cval_get_cvalue (ipcp_method_cval (node, i))->
399 		  value;
400               print_generic_expr (f, cvalue, 0);
401               fprintf (f, "\n");
402 	    }
403 	  else if (ipcp_method_cval (node, i)->cval_type == TOP)
404 	    fprintf (f, "param [%d]: type is TOP  \n", i);
405 	  else
406 	    fprintf (f, "param [%d]: type is BOTTOM  \n", i);
407 	}
408     }
409 }
410 
411 /* Initialize ipcp_cval array of MT with TOP values.
412    All cvals for a method's formal parameters are initialized to BOTTOM
413    The currently supported types are integer types, real types and
414    Fortran constants (i.e. references to constants defined as
415    const_decls). All other types are not analyzed and therefore are
416    assigned with BOTTOM.  */
417 static void
ipcp_method_cval_init(struct cgraph_node * mt)418 ipcp_method_cval_init (struct cgraph_node *mt)
419 {
420   int i;
421   tree parm_tree;
422 
423   ipcp_formal_create (mt);
424   for (i = 0; i < ipa_method_formal_count (mt); i++)
425     {
426       parm_tree = ipa_method_get_tree (mt, i);
427       if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree))
428 	  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree))
429 	  || POINTER_TYPE_P (TREE_TYPE (parm_tree)))
430 	ipcp_method_cval_set_cvalue_type (mt, i, TOP);
431       else
432 	ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM);
433     }
434 }
435 
436 /* Create a new assignment statment and make
437    it the first statement in the function FN
438    tree.
439    PARM1 is the lhs of the assignment and
440    VAL is the rhs. */
441 static void
constant_val_insert(tree fn,tree parm1,tree val)442 constant_val_insert (tree fn, tree parm1, tree val)
443 {
444   struct function *func;
445   tree init_stmt;
446   edge e_step;
447   edge_iterator ei;
448 
449   init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val);
450   func = DECL_STRUCT_FUNCTION (fn);
451   cfun = func;
452   current_function_decl = fn;
453   if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
454     FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
455       bsi_insert_on_edge_immediate (e_step, init_stmt);
456 }
457 
458 /* build INTEGER_CST tree with type TREE_TYPE and
459    value according to CVALUE. Return the tree.   */
460 static tree
build_const_val(union parameter_info * cvalue,enum cvalue_type type,tree tree_type)461 build_const_val (union parameter_info *cvalue, enum cvalue_type type,
462 		 tree tree_type)
463 {
464   tree const_val = NULL;
465 
466   gcc_assert (ipcp_type_is_const (type));
467   const_val = fold_convert (tree_type, cvalue->value);
468   return const_val;
469 }
470 
471 /* Build the tree representing the constant and call
472    constant_val_insert().  */
473 static void
ipcp_propagate_const(struct cgraph_node * mt,int param,union parameter_info * cvalue,enum cvalue_type type)474 ipcp_propagate_const (struct cgraph_node *mt, int param,
475 		      union parameter_info *cvalue ,enum cvalue_type type)
476 {
477   tree fndecl;
478   tree const_val;
479   tree parm_tree;
480 
481   if (dump_file)
482     fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
483   fndecl = mt->decl;
484   parm_tree = ipa_method_get_tree (mt, param);
485   const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
486   constant_val_insert (fndecl, parm_tree, const_val);
487 }
488 
489 /* Compute the proper scale for NODE.  It is the ratio between
490    the number of direct calls (represented on the incoming
491    cgraph_edges) and sum of all invocations of NODE (represented
492    as count in cgraph_node). */
493 static void
ipcp_method_compute_scale(struct cgraph_node * node)494 ipcp_method_compute_scale (struct cgraph_node *node)
495 {
496   gcov_type sum;
497   struct cgraph_edge *cs;
498 
499   sum = 0;
500   /* Compute sum of all counts of callers. */
501   for (cs = node->callers; cs != NULL; cs = cs->next_caller)
502     sum += cs->count;
503   if (node->count == 0)
504     ipcp_method_set_scale (node, 0);
505   else
506     ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
507 }
508 
509 /* Initialization and computation of IPCP data structures.
510    It is an intraprocedural
511    analysis of methods, which gathers information to be propagated
512    later on.  */
513 static void
ipcp_init_stage(void)514 ipcp_init_stage (void)
515 {
516   struct cgraph_node *node;
517   struct cgraph_edge *cs;
518 
519   for (node = cgraph_nodes; node; node = node->next)
520     {
521       ipa_method_formal_compute_count (node);
522       ipa_method_compute_tree_map (node);
523       ipcp_method_cval_init (node);
524       ipa_method_compute_modify (node);
525       ipcp_method_compute_scale (node);
526     }
527   for (node = cgraph_nodes; node; node = node->next)
528     {
529       /* building jump functions  */
530       for (cs = node->callees; cs; cs = cs->next_callee)
531 	{
532 	  ipa_callsite_compute_count (cs);
533 	  if (ipa_callsite_param_count (cs)
534 	      != ipa_method_formal_count (cs->callee))
535 	    {
536 	      /* Handle cases of functions with
537 	         a variable number of parameters.  */
538 	      ipa_callsite_param_count_set (cs, 0);
539 	      ipa_method_formal_count_set (cs->callee, 0);
540 	    }
541 	  else
542 	    ipa_callsite_compute_param (cs);
543 	}
544     }
545 }
546 
547 /* Return true if there are some formal parameters whose value is TOP.
548    Change their values to BOTTOM, since they weren't determined.  */
549 static bool
ipcp_after_propagate(void)550 ipcp_after_propagate (void)
551 {
552   int i, count;
553   struct cgraph_node *node;
554   bool prop_again;
555 
556   prop_again = false;
557   for (node = cgraph_nodes; node; node = node->next)
558     {
559       count = ipa_method_formal_count (node);
560       for (i = 0; i < count; i++)
561 	if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP)
562 	  {
563 	    prop_again = true;
564 	    ipcp_method_cval_set_cvalue_type (node, i, BOTTOM);
565 	  }
566     }
567   return prop_again;
568 }
569 
570 /* Interprocedural analysis. The algorithm propagates constants from
571    the caller's parameters to the callee's arguments.  */
572 static void
ipcp_propagate_stage(void)573 ipcp_propagate_stage (void)
574 {
575   int i;
576   struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} };
577   struct ipcp_formal *cval2;
578   struct cgraph_node *mt, *callee;
579   struct cgraph_edge *cs;
580   struct ipa_jump_func *jump_func;
581   enum jump_func_type type;
582   union parameter_info *info_type;
583   ipa_methodlist_p wl;
584   int count;
585 
586   /* Initialize worklist to contain all methods.  */
587   wl = ipa_methodlist_init ();
588   while (ipa_methodlist_not_empty (wl))
589     {
590       mt = ipa_remove_method (&wl);
591       for (cs = mt->callees; cs; cs = cs->next_callee)
592 	{
593 	  callee = ipa_callsite_callee (cs);
594 	  count = ipa_callsite_param_count (cs);
595 	  for (i = 0; i < count; i++)
596 	    {
597 	      jump_func = ipa_callsite_param (cs, i);
598 	      type = get_type (jump_func);
599 	      info_type = ipa_jf_get_info_type (jump_func);
600 	      ipcp_cval_compute (&cval1, mt, type, info_type);
601 	      cval2 = ipcp_method_cval (callee, i);
602 	      ipcp_cval_meet (&cval, &cval1, cval2);
603 	      if (ipcp_cval_changed (&cval, cval2))
604 		{
605 		  ipcp_method_cval_set (callee, i, &cval);
606 		  ipa_add_method (&wl, callee);
607 		}
608 	    }
609 	}
610     }
611 }
612 
613 /* Call the constant propagation algorithm and re-call it if necessary
614    (if there are undetermined values left).  */
615 static void
ipcp_iterate_stage(void)616 ipcp_iterate_stage (void)
617 {
618   ipcp_propagate_stage ();
619   if (ipcp_after_propagate ())
620     /* Some cvals have changed from TOP to BOTTOM.
621        This change should be propagated.  */
622     ipcp_propagate_stage ();
623 }
624 
625 /* Check conditions to forbid constant insertion to MT.  */
626 static bool
ipcp_method_dont_insert_const(struct cgraph_node * mt)627 ipcp_method_dont_insert_const (struct cgraph_node *mt)
628 {
629   /* ??? Handle pending sizes case.  */
630   if (DECL_UNINLINABLE (mt->decl))
631     return true;
632   return false;
633 }
634 
635 /* Print ipa_jump_func data structures to F.  */
636 static void
ipcp_callsite_param_print(FILE * f)637 ipcp_callsite_param_print (FILE * f)
638 {
639   struct cgraph_node *node;
640   int i, count;
641   struct cgraph_edge *cs;
642   struct ipa_jump_func *jump_func;
643   enum jump_func_type type;
644   tree info_type;
645 
646   fprintf (f, "\nCALLSITE PARAM PRINT\n");
647   for (node = cgraph_nodes; node; node = node->next)
648     {
649       for (cs = node->callees; cs; cs = cs->next_callee)
650 	{
651 	  fprintf (f, "callsite  %s ", cgraph_node_name (node));
652 	  fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
653 	  count = ipa_callsite_param_count (cs);
654 	  for (i = 0; i < count; i++)
655 	    {
656 	      jump_func = ipa_callsite_param (cs, i);
657 	      type = get_type (jump_func);
658 
659 	      fprintf (f, " param %d: ", i);
660 	      if (type == UNKNOWN_IPATYPE)
661 		fprintf (f, "UNKNOWN\n");
662 	      else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF)
663 		{
664 		  info_type =
665 		    ipa_jf_get_info_type (jump_func)->value;
666                   fprintf (f, "CONST : ");
667                   print_generic_expr (f, info_type, 0);
668                   fprintf (f, "\n");
669 		}
670 	      else if (type == FORMAL_IPATYPE)
671 		{
672 		  fprintf (f, "FORMAL : ");
673 		  fprintf (f, "%d\n",
674 			   ipa_jf_get_info_type (jump_func)->formal_id);
675 		}
676 	    }
677 	}
678     }
679 }
680 
681 /* Print count scale data structures.  */
682 static void
ipcp_method_scale_print(FILE * f)683 ipcp_method_scale_print (FILE * f)
684 {
685   struct cgraph_node *node;
686 
687   for (node = cgraph_nodes; node; node = node->next)
688     {
689       fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
690       fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
691 	       "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
692     }
693 }
694 
695 /* Print counts of all cgraph nodes.  */
696 static void
ipcp_profile_mt_count_print(FILE * f)697 ipcp_profile_mt_count_print (FILE * f)
698 {
699   struct cgraph_node *node;
700 
701   for (node = cgraph_nodes; node; node = node->next)
702     {
703       fprintf (f, "method %s: ", cgraph_node_name (node));
704       fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
705 	       "  \n", (HOST_WIDE_INT) node->count);
706     }
707 }
708 
709 /* Print counts of all cgraph edges.  */
710 static void
ipcp_profile_cs_count_print(FILE * f)711 ipcp_profile_cs_count_print (FILE * f)
712 {
713   struct cgraph_node *node;
714   struct cgraph_edge *cs;
715 
716   for (node = cgraph_nodes; node; node = node->next)
717     {
718       for (cs = node->callees; cs; cs = cs->next_callee)
719 	{
720 	  fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
721 		   cgraph_node_name (cs->callee));
722 	  fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
723 		   (HOST_WIDE_INT) cs->count);
724 	}
725     }
726 }
727 
728 /* Print all counts and probabilities of cfg edges of all methods.  */
729 static void
ipcp_profile_edge_print(FILE * f)730 ipcp_profile_edge_print (FILE * f)
731 {
732   struct cgraph_node *node;
733   basic_block bb;
734   edge_iterator ei;
735   edge e;
736 
737   for (node = cgraph_nodes; node; node = node->next)
738     {
739       fprintf (f, "method %s: \n", cgraph_node_name (node));
740       if (DECL_SAVED_TREE (node->decl))
741 	{
742 	  bb =
743 	    ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
744 	  fprintf (f, "ENTRY: ");
745 	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
746 		   " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
747 
748 	  if (bb->succs)
749 	    FOR_EACH_EDGE (e, ei, bb->succs)
750 	    {
751 	      if (e->dest ==
752 		  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
753 					       (node->decl)))
754 		fprintf (f, "edge ENTRY -> EXIT,  Count");
755 	      else
756 		fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
757 	      fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
758 		       " Prob %d\n", (HOST_WIDE_INT) e->count,
759 		       e->probability);
760 	    }
761 	  FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
762 	  {
763 	    fprintf (f, "bb[%d]: ", bb->index);
764 	    fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
765 		     " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
766 	    FOR_EACH_EDGE (e, ei, bb->succs)
767 	    {
768 	      if (e->dest ==
769 		  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
770 					       (node->decl)))
771 		fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
772 	      else
773 		fprintf (f, "edge %d -> %d,  Count", e->src->index,
774 			 e->dest->index);
775 	      fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
776 		       (HOST_WIDE_INT) e->count, e->probability);
777 	    }
778 	  }
779 	}
780     }
781 }
782 
783 /* Print counts and frequencies for all basic blocks of all methods.  */
784 static void
ipcp_profile_bb_print(FILE * f)785 ipcp_profile_bb_print (FILE * f)
786 {
787   basic_block bb;
788   struct cgraph_node *node;
789 
790   for (node = cgraph_nodes; node; node = node->next)
791     {
792       fprintf (f, "method %s: \n", cgraph_node_name (node));
793       if (DECL_SAVED_TREE (node->decl))
794 	{
795 	  bb =
796 	    ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
797 	  fprintf (f, "ENTRY: Count");
798 	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
799 		   " Frquency  %d\n", (HOST_WIDE_INT) bb->count,
800 		   bb->frequency);
801 
802 	  FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
803 	  {
804 	    fprintf (f, "bb[%d]: Count", bb->index);
805 	    fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
806 		     " Frequency %d\n", (HOST_WIDE_INT) bb->count,
807 		     bb->frequency);
808 	  }
809 	  bb =
810 	    EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
811 	  fprintf (f, "EXIT: Count");
812 	  fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
813 		   " Frequency %d\n", (HOST_WIDE_INT) bb->count,
814 		   bb->frequency);
815 
816 	}
817     }
818 }
819 
820 /* Print all IPCP data structures to F.  */
821 static void
ipcp_structures_print(FILE * f)822 ipcp_structures_print (FILE * f)
823 {
824   ipcp_method_cval_print (f);
825   ipcp_method_scale_print (f);
826   ipa_method_tree_print (f);
827   ipa_method_modify_print (f);
828   ipcp_callsite_param_print (f);
829 }
830 
831 /* Print profile info for all methods.  */
832 static void
ipcp_profile_print(FILE * f)833 ipcp_profile_print (FILE * f)
834 {
835   fprintf (f, "\nNODE COUNTS :\n");
836   ipcp_profile_mt_count_print (f);
837   fprintf (f, "\nCS COUNTS stage:\n");
838   ipcp_profile_cs_count_print (f);
839   fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
840   ipcp_profile_bb_print (f);
841   fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
842   ipcp_profile_edge_print (f);
843 }
844 
845 /* Build and initialize ipa_replace_map struct
846    according to TYPE. This struct is read by versioning, which
847    operates according to the flags sent.  PARM_TREE is the
848    formal's tree found to be constant.  CVALUE represents the constant.  */
849 static struct ipa_replace_map *
ipcp_replace_map_create(enum cvalue_type type,tree parm_tree,union parameter_info * cvalue)850 ipcp_replace_map_create (enum cvalue_type type, tree parm_tree,
851 			 union parameter_info *cvalue)
852 {
853   struct ipa_replace_map *replace_map;
854   tree const_val;
855 
856   replace_map = XCNEW (struct ipa_replace_map);
857   gcc_assert (ipcp_type_is_const (type));
858   if (type == CONST_VALUE_REF )
859     {
860       const_val =
861 	build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree)));
862       replace_map->old_tree = parm_tree;
863       replace_map->new_tree = const_val;
864       replace_map->replace_p = true;
865       replace_map->ref_p = true;
866     }
867   else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree))
868     {
869       const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
870       replace_map->old_tree = parm_tree;
871       replace_map->new_tree = const_val;
872       replace_map->replace_p = true;
873       replace_map->ref_p = false;
874     }
875   else
876     {
877       replace_map->old_tree = NULL;
878       replace_map->new_tree = NULL;
879       replace_map->replace_p = false;
880       replace_map->ref_p = false;
881     }
882 
883   return replace_map;
884 }
885 
886 /* Return true if this callsite should be redirected to
887    the orig callee (instead of the cloned one).  */
888 static bool
ipcp_redirect(struct cgraph_edge * cs)889 ipcp_redirect (struct cgraph_edge *cs)
890 {
891   struct cgraph_node *caller, *callee, *orig_callee;
892   int i, count;
893   struct ipa_jump_func *jump_func;
894   enum jump_func_type type;
895   enum cvalue_type cval_type;
896 
897   caller = cs->caller;
898   callee = cs->callee;
899   orig_callee = ipcp_method_orig_node (callee);
900   count = ipa_method_formal_count (orig_callee);
901   for (i = 0; i < count; i++)
902     {
903       cval_type =
904 	ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
905       if (ipcp_type_is_const (cval_type))
906 	{
907 	  jump_func = ipa_callsite_param (cs, i);
908 	  type = get_type (jump_func);
909 	  if (type != CONST_IPATYPE
910 	      && type != CONST_IPATYPE_REF)
911 	    return true;
912 	}
913     }
914 
915   return false;
916 }
917 
918 /* Fix the callsites and the callgraph after function cloning was done.  */
919 static void
ipcp_update_callgraph(void)920 ipcp_update_callgraph (void)
921 {
922   struct cgraph_node *node, *orig_callee;
923   struct cgraph_edge *cs;
924 
925   for (node = cgraph_nodes; node; node = node->next)
926     {
927       /* want to fix only original nodes  */
928       if (ipcp_method_is_cloned (node))
929 	continue;
930       for (cs = node->callees; cs; cs = cs->next_callee)
931 	if (ipcp_method_is_cloned (cs->callee))
932 	  {
933 	    /* Callee is a cloned node  */
934 	    orig_callee = ipcp_method_orig_node (cs->callee);
935 	    if (ipcp_redirect (cs))
936 	      {
937 		cgraph_redirect_edge_callee (cs, orig_callee);
938 		TREE_OPERAND (TREE_OPERAND
939 			      (get_call_expr_in (cs->call_stmt), 0), 0) =
940 		  orig_callee->decl;
941 	      }
942 	  }
943     }
944 }
945 
946 /* Update all cfg basic blocks in NODE according to SCALE.  */
947 static void
ipcp_update_bb_counts(struct cgraph_node * node,gcov_type scale)948 ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
949 {
950   basic_block bb;
951 
952   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
953     bb->count = bb->count * scale / REG_BR_PROB_BASE;
954 }
955 
956 /* Update all cfg edges in NODE according to SCALE.  */
957 static void
ipcp_update_edges_counts(struct cgraph_node * node,gcov_type scale)958 ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
959 {
960   basic_block bb;
961   edge_iterator ei;
962   edge e;
963 
964   FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
965     FOR_EACH_EDGE (e, ei, bb->succs)
966     e->count = e->count * scale / REG_BR_PROB_BASE;
967 }
968 
969 /* Update profiling info for versioned methods and the
970    methods they were versioned from.  */
971 static void
ipcp_update_profiling(void)972 ipcp_update_profiling (void)
973 {
974   struct cgraph_node *node, *orig_node;
975   gcov_type scale, scale_complement;
976   struct cgraph_edge *cs;
977 
978   for (node = cgraph_nodes; node; node = node->next)
979     {
980       if (ipcp_method_is_cloned (node))
981 	{
982 	  orig_node = ipcp_method_orig_node (node);
983 	  scale = ipcp_method_get_scale (orig_node);
984 	  node->count = orig_node->count * scale / REG_BR_PROB_BASE;
985 	  scale_complement = REG_BR_PROB_BASE - scale;
986 	  orig_node->count =
987 	    orig_node->count * scale_complement / REG_BR_PROB_BASE;
988 	  for (cs = node->callees; cs; cs = cs->next_callee)
989 	    cs->count = cs->count * scale / REG_BR_PROB_BASE;
990 	  for (cs = orig_node->callees; cs; cs = cs->next_callee)
991 	    cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
992 	  ipcp_update_bb_counts (node, scale);
993 	  ipcp_update_bb_counts (orig_node, scale_complement);
994 	  ipcp_update_edges_counts (node, scale);
995 	  ipcp_update_edges_counts (orig_node, scale_complement);
996 	}
997     }
998 }
999 
1000 /* Propagate the constant parameters found by ipcp_iterate_stage()
1001    to the function's code.  */
1002 static void
ipcp_insert_stage(void)1003 ipcp_insert_stage (void)
1004 {
1005   struct cgraph_node *node, *node1 = NULL;
1006   int i, const_param;
1007   union parameter_info *cvalue;
1008   VEC(cgraph_edge_p,heap) *redirect_callers;
1009   varray_type replace_trees;
1010   struct cgraph_edge *cs;
1011   int node_callers, count;
1012   tree parm_tree;
1013   enum cvalue_type type;
1014   struct ipa_replace_map *replace_param;
1015 
1016   for (node = cgraph_nodes; node; node = node->next)
1017     {
1018       /* Propagation of the constant is forbidden in
1019          certain conditions.  */
1020       if (ipcp_method_dont_insert_const (node))
1021 	continue;
1022       const_param = 0;
1023       count = ipa_method_formal_count (node);
1024       for (i = 0; i < count; i++)
1025 	{
1026 	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1027 	  if (ipcp_type_is_const (type))
1028 	    const_param++;
1029 	}
1030       if (const_param == 0)
1031 	continue;
1032       VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
1033       for (i = 0; i < count; i++)
1034 	{
1035 	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1036 	  if (ipcp_type_is_const (type))
1037 	    {
1038 	      cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1039 	      parm_tree = ipa_method_get_tree (node, i);
1040 	      replace_param =
1041 		ipcp_replace_map_create (type, parm_tree, cvalue);
1042 	      VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1043 	    }
1044 	}
1045       /* Compute how many callers node has.  */
1046       node_callers = 0;
1047       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1048 	node_callers++;
1049       redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1050       for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1051 	VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1052       /* Redirecting all the callers of the node to the
1053          new versioned node.  */
1054       node1 =
1055 	cgraph_function_versioning (node, redirect_callers, replace_trees);
1056       VEC_free (cgraph_edge_p, heap, redirect_callers);
1057       VARRAY_CLEAR (replace_trees);
1058       if (node1 == NULL)
1059 	continue;
1060       if (dump_file)
1061 	fprintf (dump_file, "versioned function %s\n",
1062 		 cgraph_node_name (node));
1063       ipcp_cloned_create (node, node1);
1064       for (i = 0; i < count; i++)
1065 	{
1066 	  type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1067 	  if (ipcp_type_is_const (type))
1068 	    {
1069 	      cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1070 	      parm_tree = ipa_method_get_tree (node, i);
1071 	      if (type != CONST_VALUE_REF
1072 		  && !TREE_READONLY (parm_tree))
1073 		ipcp_propagate_const (node1, i, cvalue, type);
1074 	    }
1075 	}
1076     }
1077   ipcp_update_callgraph ();
1078   ipcp_update_profiling ();
1079 }
1080 
1081 /* The IPCP driver.  */
1082 unsigned int
ipcp_driver(void)1083 ipcp_driver (void)
1084 {
1085   if (dump_file)
1086     fprintf (dump_file, "\nIPA constant propagation start:\n");
1087   ipa_nodes_create ();
1088   ipa_edges_create ();
1089   /* 1. Call the init stage to initialize
1090      the ipa_node and ipa_edge structures.  */
1091   ipcp_init_stage ();
1092   if (dump_file)
1093     {
1094       fprintf (dump_file, "\nIPA structures before propagation:\n");
1095       ipcp_structures_print (dump_file);
1096     }
1097   /* 2. Do the interprocedural propagation.  */
1098   ipcp_iterate_stage ();
1099   if (dump_file)
1100     {
1101       fprintf (dump_file, "\nIPA structures after propagation:\n");
1102       ipcp_structures_print (dump_file);
1103       fprintf (dump_file, "\nProfiling info before insert stage:\n");
1104       ipcp_profile_print (dump_file);
1105     }
1106   /* 3. Insert the constants found to the functions.  */
1107   ipcp_insert_stage ();
1108   if (dump_file)
1109     {
1110       fprintf (dump_file, "\nProfiling info after insert stage:\n");
1111       ipcp_profile_print (dump_file);
1112     }
1113   /* Free all IPCP structures.  */
1114   ipa_free ();
1115   ipa_nodes_free ();
1116   ipa_edges_free ();
1117   if (dump_file)
1118     fprintf (dump_file, "\nIPA constant propagation end\n");
1119   cgraph_remove_unreachable_nodes (true, NULL);
1120   return 0;
1121 }
1122 
1123 /* Gate for IPCP optimization.  */
1124 static bool
cgraph_gate_cp(void)1125 cgraph_gate_cp (void)
1126 {
1127   return flag_ipa_cp;
1128 }
1129 
1130 struct tree_opt_pass pass_ipa_cp = {
1131   "cp",				/* name */
1132   cgraph_gate_cp,		/* gate */
1133   ipcp_driver,			/* execute */
1134   NULL,				/* sub */
1135   NULL,				/* next */
1136   0,				/* static_pass_number */
1137   TV_IPA_CONSTANT_PROP,		/* tv_id */
1138   0,				/* properties_required */
1139   PROP_trees,			/* properties_provided */
1140   0,				/* properties_destroyed */
1141   0,				/* todo_flags_start */
1142   TODO_dump_cgraph | TODO_dump_func,	/* todo_flags_finish */
1143   0				/* letter */
1144 };
1145