2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief read/write analyze of graph argument, which have mode reference.
23 * @author Beyhan Veliev
42 #include "analyze_irg_args.h"
45 static void *VISITED = &v;
48 * Walk recursive the successors of a graph argument
49 * with mode reference and mark if it will be read,
52 * @param arg The graph argument with mode reference,
53 * that must be checked.
55 static unsigned analyze_arg(ir_node *arg, unsigned bits) {
59 /* We must visit a node once to avoid endless recursion.*/
60 set_irn_link(arg, VISITED);
62 for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
63 succ = get_irn_out(arg, i);
66 if (get_irn_link(succ) == VISITED)
69 /* We should not walk over the memory edge.*/
70 if (get_irn_mode(succ) == mode_M)
73 /* If we reach with the recursion a Call node and our reference
74 isn't the address of this Call we accept that the reference will
75 be read and written if the graph of the method represented by
76 "Call" isn't computed else we analyze that graph. If our
77 reference is the address of this
78 Call node that mean the reference will be read.*/
79 switch (get_irn_opcode(succ)) {
82 ir_node *ptr = get_Call_ptr(succ);
85 /* Hmm: not sure what this is, most likely a read */
86 bits |= ptr_access_read;
88 ir_op *op = get_irn_op(ptr);
92 meth_ent = get_Global_entity(ptr);
94 for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
95 if (get_Call_param(succ, p) == arg) {
96 /* an arg can be used more than once ! */
97 bits |= get_method_param_access(meth_ent, p);
100 } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
101 /* is be a polymorphic call but callee information is available */
102 int i, n_params = get_Call_n_params(succ);
104 /* simply look into ALL possible callees */
105 for (i = get_Call_n_callees(succ) - 1; i >= 0; --i) {
106 meth_ent = get_Call_callee(succ, i);
108 /* unknown_entity is used to signal that we don't know what is called */
109 if (meth_ent == unknown_entity) {
110 bits |= ptr_access_all;
114 for (p = n_params - 1; p >= 0; --p) {
115 if (get_Call_param(succ, p) == arg) {
116 /* an arg can be used more than once ! */
117 bits |= get_method_param_access(meth_ent, p);
121 } else /* can do anything */
122 bits |= ptr_access_all;
125 /* search stops here anyway */
129 /* We have reached a Store node => the reference is written or stored. */
130 if (get_Store_ptr(succ) == arg) {
132 bits |= ptr_access_write;
135 bits |= ptr_access_store;
138 /* search stops here anyway */
142 /* We have reached a Load node => the reference is read. */
143 bits |= ptr_access_read;
145 /* search stops here anyway */
149 /* our address is casted into something unknown. Break our search. */
150 bits = ptr_access_all;
157 /* If we know that, the argument will be read, write and stored, we
158 can break the recursion.*/
159 if (bits == ptr_access_all) {
160 bits = ptr_access_all;
165 * A calculation that do not lead to a reference mode ends our search.
166 * This is dangerous: It would allow to cast into integer and that cast back ...
167 * so, when we detect a Conv we go mad, see the Conv case above.
169 if (!mode_is_reference(get_irn_mode(succ)))
172 /* follow further the address calculation */
173 bits = analyze_arg(succ, bits);
175 set_irn_link(arg, NULL);
180 * Check if a argument of the ir graph with mode
181 * reference is read, write or both.
183 * @param irg The ir graph to analyze.
185 static void analyze_ent_args(ir_entity *ent) {
187 ir_node *irg_args, *arg;
192 ptr_access_kind *rw_info;
194 mtp = get_entity_type(ent);
195 nparams = get_method_n_params(mtp);
197 ent->attr.mtd_attr.param_access = NEW_ARR_F(ptr_access_kind, nparams);
199 /* If the method haven't parameters we have
205 irg = get_entity_irg(ent);
207 /* we have not yet analyzed the graph, set ALL access for pointer args */
208 for (i = nparams - 1; i >= 0; --i) {
209 ir_type *type = get_method_param_type(mtp, i);
210 ent->attr.mtd_attr.param_access[i] = is_Pointer_type(type) ? ptr_access_all : ptr_access_none;
214 /* no graph, no better info */
218 assure_irg_outs(irg);
220 irg_args = get_irg_args(irg);
222 /* A array to save the information for each argument with
224 NEW_ARR_A(ptr_access_kind, rw_info, nparams);
226 /* We initialize the element with none state. */
227 for (i = nparams - 1; i >= 0; --i)
228 rw_info[i] = ptr_access_none;
230 /* search for arguments with mode reference
232 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
233 arg = get_irn_out(irg_args, i);
234 arg_mode = get_irn_mode(arg);
235 proj_nr = get_Proj_proj(arg);
237 if (mode_is_reference(arg_mode))
238 rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
241 /* copy the temporary info */
242 memcpy(ent->attr.mtd_attr.param_access, rw_info,
243 nparams * sizeof(ent->attr.mtd_attr.param_access[0]));
246 printf("\n%s:\n", get_entity_name(ent));
247 for (i = 0; i < nparams; ++i) {
248 if (is_Pointer_type(get_method_param_type(mtp, i)))
249 if (ent->attr.mtd_attr.param_access[i] != ptr_access_none) {
250 printf(" Pointer Arg %d access: ", i);
251 if (ent->attr.mtd_attr.param_access[i] & ptr_access_read)
253 if (ent->attr.mtd_attr.param_access[i] & ptr_access_write)
255 if (ent->attr.mtd_attr.param_access[i] & ptr_access_store)
264 * Analyze how pointer arguments of a given
265 * ir graph are accessed.
267 * @param irg The ir graph to analyze.
269 void analyze_irg_args(ir_graph *irg) {
272 if (irg == get_const_code_irg())
275 ent = get_irg_entity(irg);
279 if (! ent->attr.mtd_attr.param_access)
280 analyze_ent_args(ent);
284 * Compute for a method with pointer parameter(s)
285 * if they will be read or written.
287 ptr_access_kind get_method_param_access(ir_entity *ent, int pos)
290 ir_type *mtp = get_entity_type(ent);
291 int is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
293 assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
296 if (ent->attr.mtd_attr.param_access) {
297 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
298 return ent->attr.mtd_attr.param_access[pos];
300 return ptr_access_all;
303 analyze_ent_args(ent);
305 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
306 return ent->attr.mtd_attr.param_access[pos];
308 return ptr_access_all;
311 /* Weights for parameters */
313 null_weight = 0, /**< If can't be anything optimized. */
314 binop_weight = 1, /**< If the argument have mode_weight and take part in binop. */
315 const_binop_weight = 1, /**< If the argument have mode_weight and take part in binop with a constant.*/
316 cmp_weight = 4, /**< If the argument take part in cmp. */
317 const_cmp_weight = 10, /**< If the argument take part in cmp with a constant. */
318 indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */
322 * Compute the weight of a method parameter
324 * @param arg The parameter them weight muss be computed.
326 static unsigned calc_method_param_weight(ir_node *arg) {
329 unsigned weight = null_weight;
331 /* We mark the nodes to avoid endless recursion */
332 set_irn_link(arg, VISITED);
334 for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
335 succ = get_irn_out(arg, i);
338 if (get_irn_link(succ) == VISITED)
341 /* We should not walk over the memory edge.*/
342 if (get_irn_mode(succ) == mode_M)
345 if (is_Call(succ) && get_Call_ptr(succ) == arg) {
346 /* the arguments is used as an pointer input for a call,
347 we can probably change an indirect Call into a direct one. */
348 weight += indirect_call_weight;
349 } else if (is_Cmp(succ)) {
350 /* We have reached a cmp and we must increase the
351 weight with the cmp_weight. */
352 if (get_Cmp_left(succ) == arg)
353 op = get_Cmp_right(succ);
355 op = get_Cmp_left(succ);
357 if (is_irn_constlike(op)) {
358 weight += const_cmp_weight;
360 weight += cmp_weight;
361 } else if (is_Cond(succ)) {
362 /* the argument is used for a SwitchCond, a big win */
363 weight += const_cmp_weight * get_irn_n_outs(succ);
364 } else if (is_binop(succ)) {
365 /* We have reached a BinOp and we must increase the
366 weight with the binop_weight. If the other operand of the
367 BinOp is a constant we increase the weight with const_binop_weight
368 and call the function recursive.
370 if (get_binop_left(succ) == arg)
371 op = get_binop_right(succ);
373 op = get_binop_left(succ);
375 if (is_irn_constlike(op)) {
376 weight += const_binop_weight;
377 weight += calc_method_param_weight(succ);
379 weight += binop_weight;
380 } else if (is_unop(succ)) {
381 /* We have reached a binop and we must increase the
382 weight with the const_binop_weight and call the function recursive.*/
383 weight += const_binop_weight;
384 weight += calc_method_param_weight(succ);
387 set_irn_link(arg, NULL);
392 * Calculate a weight for each argument of an entity.
394 * @param ent The entity of the ir_graph.
396 static void analyze_method_params_weight(ir_entity *ent) {
399 int nparams, i, proj_nr;
400 ir_node *irg_args, *arg;
402 mtp = get_entity_type(ent);
403 nparams = get_method_n_params(mtp);
405 /* allocate a new array. currently used as 'analysed' flag */
406 ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
408 /* If the method haven't parameters we have nothing to do. */
412 /* First we initialize the parameter weights with 0. */
413 for (i = nparams - 1; i >= 0; i--)
414 ent->attr.mtd_attr.param_weight[i] = null_weight;
416 irg = get_entity_irg(ent);
418 /* no graph, no better info */
422 /* Call algorithm that computes the out edges */
423 assure_irg_outs(irg);
425 irg_args = get_irg_args(irg);
427 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
428 arg = get_irn_out(irg_args, i);
429 proj_nr = get_Proj_proj(arg);
430 ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
434 printf("\n%s:\n", get_entity_name(ent));
435 for (i = nparams - 1; i >= 0; --i)
436 printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
441 * Returns for a method the 'weight' that every parameter
442 * has on optimization possibility. Higher values allows
443 * higher optimization with procedure cloning.
445 * The values are calculation on demand only.
447 unsigned get_method_param_weight(ir_entity *ent, int pos)
450 ir_type *mtp = get_entity_type(ent);
451 int is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
452 assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
455 if (ent->attr.mtd_attr.param_weight) {
456 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
457 return ent->attr.mtd_attr.param_weight[pos];
462 analyze_method_params_weight(ent);
464 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
465 return ent->attr.mtd_attr.param_weight[pos];
471 * Analyze argument's weight of a given
474 * @param irg The ir graph to analyze.
476 void analyze_irg_args_weight(ir_graph *irg) {
479 ent = get_irg_entity(irg);
483 if (! ent->attr.mtd_attr.param_weight)
484 analyze_method_params_weight(ent);