1 /*
2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file
22 * @brief read/write analyze of graph argument, which have mode reference.
23 * @author Beyhan Veliev
24 */
25 #include "config.h"
26
27 #include <stdlib.h>
28
29 #include "irouts.h"
30 #include "irnode_t.h"
31 #include "irmode_t.h"
32 #include "array_t.h"
33 #include "irprog.h"
34 #include "entity_t.h"
35
36 #include "analyze_irg_args.h"
37
38 /**
39 * Walk recursive the successors of a graph argument
40 * with mode reference and mark if it will be read,
41 * written or stored.
42 *
43 * @param arg The graph argument with mode reference,
44 * that must be checked.
45 */
analyze_arg(ir_node * arg,ptr_access_kind bits)46 static ptr_access_kind analyze_arg(ir_node *arg, ptr_access_kind bits)
47 {
48 int i, p;
49 ir_node *succ;
50
51 /* We must visit a node once to avoid endless recursion.*/
52 mark_irn_visited(arg);
53
54 for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
55 succ = get_irn_out(arg, i);
56
57 /* We was here.*/
58 if (irn_visited(succ))
59 continue;
60
61 /* We should not walk over the memory edge.*/
62 if (get_irn_mode(succ) == mode_M)
63 continue;
64
65 /* If we reach with the recursion a Call node and our reference
66 isn't the address of this Call we accept that the reference will
67 be read and written if the graph of the method represented by
68 "Call" isn't computed else we analyze that graph. If our
69 reference is the address of this
70 Call node that mean the reference will be read.*/
71 switch (get_irn_opcode(succ)) {
72
73 case iro_Call: {
74 ir_node *ptr = get_Call_ptr(succ);
75
76 if (ptr == arg) {
77 /* Hmm: not sure what this is, most likely a read */
78 bits |= ptr_access_read;
79 } else {
80 ir_entity *meth_ent;
81
82 if (is_SymConst_addr_ent(ptr)) {
83 meth_ent = get_SymConst_entity(ptr);
84
85 for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
86 if (get_Call_param(succ, p) == arg) {
87 /* an arg can be used more than once ! */
88 bits |= get_method_param_access(meth_ent, p);
89 }
90 }
91 } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
92 /* is be a polymorphic call but callee information is available */
93 int n_params = get_Call_n_params(succ);
94 int c;
95
96 /* simply look into ALL possible callees */
97 for (c = get_Call_n_callees(succ) - 1; c >= 0; --c) {
98 meth_ent = get_Call_callee(succ, c);
99
100 /* unknown_entity is used to signal that we don't know what is called */
101 if (is_unknown_entity(meth_ent)) {
102 bits |= ptr_access_all;
103 break;
104 }
105
106 for (p = n_params - 1; p >= 0; --p) {
107 if (get_Call_param(succ, p) == arg) {
108 /* an arg can be used more than once ! */
109 bits |= get_method_param_access(meth_ent, p);
110 }
111 }
112 }
113 } else /* can do anything */
114 bits |= ptr_access_all;
115 }
116
117 /* search stops here anyway */
118 continue;
119 }
120 case iro_Store:
121 /* We have reached a Store node => the reference is written or stored. */
122 if (get_Store_ptr(succ) == arg) {
123 /* written to */
124 bits |= ptr_access_write;
125 } else {
126 /* stored itself */
127 bits |= ptr_access_store;
128 }
129
130 /* search stops here anyway */
131 continue;
132
133 case iro_Load:
134 /* We have reached a Load node => the reference is read. */
135 bits |= ptr_access_read;
136
137 /* search stops here anyway */
138 continue;
139
140 case iro_Conv:
141 /* our address is casted into something unknown. Break our search. */
142 bits = ptr_access_all;
143 break;
144
145 default:
146 break;
147 }
148
149 /* If we know that, the argument will be read, write and stored, we
150 can break the recursion.*/
151 if (bits == ptr_access_all) {
152 bits = ptr_access_all;
153 break;
154 }
155
156 /*
157 * A calculation that do not lead to a reference mode ends our search.
158 * This is dangerous: It would allow to cast into integer and that cast back ...
159 * so, when we detect a Conv we go mad, see the Conv case above.
160 */
161 if (!mode_is_reference(get_irn_mode(succ)))
162 continue;
163
164 /* follow further the address calculation */
165 bits = analyze_arg(succ, bits);
166 }
167 set_irn_link(arg, NULL);
168 return bits;
169 }
170
171 /**
172 * Check if a argument of the ir graph with mode
173 * reference is read, write or both.
174 *
175 * @param irg The ir graph to analyze.
176 */
analyze_ent_args(ir_entity * ent)177 static void analyze_ent_args(ir_entity *ent)
178 {
179 ir_graph *irg;
180 ir_node *irg_args, *arg;
181 ir_mode *arg_mode;
182 int nparams, i;
183 long proj_nr;
184 ir_type *mtp;
185 ptr_access_kind *rw_info;
186
187 mtp = get_entity_type(ent);
188 nparams = get_method_n_params(mtp);
189
190 ent->attr.mtd_attr.param_access = NEW_ARR_F(ptr_access_kind, nparams);
191
192 /* If the method haven't parameters we have
193 * nothing to do.
194 */
195 if (nparams <= 0)
196 return;
197
198 irg = get_entity_irg(ent);
199
200 /* we have not yet analyzed the graph, set ALL access for pointer args */
201 for (i = nparams - 1; i >= 0; --i) {
202 ir_type *type = get_method_param_type(mtp, i);
203 ent->attr.mtd_attr.param_access[i] = is_Pointer_type(type) ? ptr_access_all : ptr_access_none;
204 }
205
206 if (! irg) {
207 /* no graph, no better info */
208 return;
209 }
210
211 assure_irg_outs(irg);
212
213 irg_args = get_irg_args(irg);
214
215 /* A array to save the information for each argument with
216 mode reference.*/
217 NEW_ARR_A(ptr_access_kind, rw_info, nparams);
218
219 /* We initialize the element with none state. */
220 for (i = nparams - 1; i >= 0; --i)
221 rw_info[i] = ptr_access_none;
222
223 /* search for arguments with mode reference
224 to analyze them.*/
225 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
226 arg = get_irn_out(irg_args, i);
227 arg_mode = get_irn_mode(arg);
228 proj_nr = get_Proj_proj(arg);
229
230 if (mode_is_reference(arg_mode))
231 rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
232 }
233
234 /* copy the temporary info */
235 memcpy(ent->attr.mtd_attr.param_access, rw_info,
236 nparams * sizeof(ent->attr.mtd_attr.param_access[0]));
237
238 #if 0
239 printf("\n%s:\n", get_entity_name(ent));
240 for (i = 0; i < nparams; ++i) {
241 if (is_Pointer_type(get_method_param_type(mtp, i)))
242 if (ent->attr.mtd_attr.param_access[i] != ptr_access_none) {
243 printf(" Pointer Arg %d access: ", i);
244 if (ent->attr.mtd_attr.param_access[i] & ptr_access_read)
245 printf("READ ");
246 if (ent->attr.mtd_attr.param_access[i] & ptr_access_write)
247 printf("WRITE ");
248 if (ent->attr.mtd_attr.param_access[i] & ptr_access_store)
249 printf("STORE ");
250 printf("\n");
251 }
252 }
253 #endif
254 }
255
analyze_irg_args(ir_graph * irg)256 void analyze_irg_args(ir_graph *irg)
257 {
258 ir_entity *ent;
259
260 if (irg == get_const_code_irg())
261 return;
262
263 ent = get_irg_entity(irg);
264 if (! ent)
265 return;
266
267 if (! ent->attr.mtd_attr.param_access)
268 analyze_ent_args(ent);
269 }
270
get_method_param_access(ir_entity * ent,size_t pos)271 ptr_access_kind get_method_param_access(ir_entity *ent, size_t pos)
272 {
273 #ifndef NDEBUG
274 ir_type *mtp = get_entity_type(ent);
275 int is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
276
277 assert(is_variadic || pos < get_method_n_params(mtp));
278 #endif
279
280 if (ent->attr.mtd_attr.param_access) {
281 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
282 return ent->attr.mtd_attr.param_access[pos];
283 else
284 return ptr_access_all;
285 }
286
287 analyze_ent_args(ent);
288
289 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
290 return ent->attr.mtd_attr.param_access[pos];
291 else
292 return ptr_access_all;
293 }
294
295 /* Weights for parameters */
296 enum args_weight {
297 null_weight = 0, /**< If can't be anything optimized. */
298 binop_weight = 1, /**< If the argument have mode_weight and take part in binop. */
299 const_binop_weight = 1, /**< If the argument have mode_weight and take part in binop with a constant.*/
300 cmp_weight = 4, /**< If the argument take part in cmp. */
301 const_cmp_weight = 10, /**< If the argument take part in cmp with a constant. */
302 indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */
303 };
304
305 /**
306 * Compute the weight of a method parameter
307 *
308 * @param arg The parameter them weight muss be computed.
309 */
calc_method_param_weight(ir_node * arg)310 static unsigned calc_method_param_weight(ir_node *arg)
311 {
312 int i, j, k;
313 ir_node *succ, *op;
314 unsigned weight = null_weight;
315
316 /* We mark the nodes to avoid endless recursion */
317 mark_irn_visited(arg);
318
319 for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
320 succ = get_irn_out(arg, i);
321
322 /* We was here.*/
323 if (irn_visited(succ))
324 continue;
325
326 /* We should not walk over the memory edge.*/
327 if (get_irn_mode(succ) == mode_M)
328 continue;
329
330 switch (get_irn_opcode(succ)) {
331 case iro_Call:
332 if (get_Call_ptr(succ) == arg) {
333 /* the arguments is used as an pointer input for a call,
334 we can probably change an indirect Call into a direct one. */
335 weight += indirect_call_weight;
336 }
337 break;
338 case iro_Cmp:
339 /* We have reached a cmp and we must increase the
340 weight with the cmp_weight. */
341 if (get_Cmp_left(succ) == arg)
342 op = get_Cmp_right(succ);
343 else
344 op = get_Cmp_left(succ);
345
346 if (is_irn_constlike(op)) {
347 weight += const_cmp_weight;
348 } else
349 weight += cmp_weight;
350 break;
351 case iro_Cond:
352 /* the argument is used for a SwitchCond, a big win */
353 weight += const_cmp_weight * get_irn_n_outs(succ);
354 break;
355 case iro_Id:
356 /* when looking backward we might find Id nodes */
357 weight += calc_method_param_weight(succ);
358 break;
359 case iro_Tuple:
360 /* unoptimized tuple */
361 for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
362 ir_node *pred = get_Tuple_pred(succ, j);
363 if (pred == arg) {
364 /* look for Proj(j) */
365 for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
366 ir_node *succ_succ = get_irn_out(succ, k);
367 if (is_Proj(succ_succ)) {
368 if (get_Proj_proj(succ_succ) == j) {
369 /* found */
370 weight += calc_method_param_weight(succ_succ);
371 }
372 } else {
373 /* this should NOT happen */
374 }
375 }
376 }
377 }
378 break;
379 default:
380 if (is_binop(succ)) {
381 /* We have reached a BinOp and we must increase the
382 weight with the binop_weight. If the other operand of the
383 BinOp is a constant we increase the weight with const_binop_weight
384 and call the function recursive.
385 */
386 if (get_binop_left(succ) == arg)
387 op = get_binop_right(succ);
388 else
389 op = get_binop_left(succ);
390
391 if (is_irn_constlike(op)) {
392 weight += const_binop_weight;
393 weight += calc_method_param_weight(succ);
394 } else
395 weight += binop_weight;
396 } else if (is_unop(succ)) {
397 /* We have reached a binop and we must increase the
398 weight with the const_binop_weight and call the function recursive.*/
399 weight += const_binop_weight;
400 weight += calc_method_param_weight(succ);
401 }
402 break;
403 }
404 }
405 set_irn_link(arg, NULL);
406 return weight;
407 }
408
409 /**
410 * Calculate a weight for each argument of an entity.
411 *
412 * @param ent The entity of the ir_graph.
413 */
analyze_method_params_weight(ir_entity * ent)414 static void analyze_method_params_weight(ir_entity *ent)
415 {
416 ir_type *mtp;
417 ir_graph *irg;
418 int nparams, i, proj_nr;
419 ir_node *irg_args, *arg;
420
421 mtp = get_entity_type(ent);
422 nparams = get_method_n_params(mtp);
423
424 /* allocate a new array. currently used as 'analysed' flag */
425 ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
426
427 /* If the method haven't parameters we have nothing to do. */
428 if (nparams <= 0)
429 return;
430
431 /* First we initialize the parameter weights with 0. */
432 for (i = nparams - 1; i >= 0; i--)
433 ent->attr.mtd_attr.param_weight[i] = null_weight;
434
435 irg = get_entity_irg(ent);
436 if (irg == NULL) {
437 /* no graph, no better info */
438 return;
439 }
440
441 /* Call algorithm that computes the out edges */
442 assure_irg_outs(irg);
443
444 irg_args = get_irg_args(irg);
445 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
446 arg = get_irn_out(irg_args, i);
447 proj_nr = get_Proj_proj(arg);
448 ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
449 }
450 }
451
get_method_param_weight(ir_entity * ent,size_t pos)452 unsigned get_method_param_weight(ir_entity *ent, size_t pos)
453 {
454 if (ent->attr.mtd_attr.param_weight) {
455 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
456 return ent->attr.mtd_attr.param_weight[pos];
457 else
458 return null_weight;
459 }
460
461 analyze_method_params_weight(ent);
462
463 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
464 return ent->attr.mtd_attr.param_weight[pos];
465 else
466 return null_weight;
467 }
468
analyze_irg_args_weight(ir_graph * irg)469 void analyze_irg_args_weight(ir_graph *irg)
470 {
471 ir_entity *entity = get_irg_entity(irg);
472 if (entity == NULL)
473 return;
474
475 assert(is_method_entity(entity));
476 if (entity->attr.mtd_attr.param_weight != NULL)
477 return;
478
479 ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
480 inc_irg_visited(irg);
481 analyze_method_params_weight(entity);
482 ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
483 }
484