analyze_irg_args.c 10.8 KB
Newer Older
1
/*
Matthias Braun's avatar
Matthias Braun committed
2
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
 */

/**
Matthias Braun's avatar
Matthias Braun committed
7
8
 * @file
 * @brief      read/write analyze of graph argument, which have mode reference.
Michael Beck's avatar
Michael Beck committed
9
 * @author     Beyhan Veliev
10
 */
11
#include <stdlib.h>
12

13
#include "irouts_t.h"
14
15
#include "irnode_t.h"
#include "irmode_t.h"
16
#include "array.h"
17
#include "cgana.h"
18
19
20
#include "irprog.h"
#include "entity_t.h"
#include "analyze_irg_args.h"
Christoph Mallon's avatar
Christoph Mallon committed
21
#include "util.h"
22
23
24

/**
 * Walk recursive the successors of a graph argument
25
 * with mode reference and mark if it will be read,
Michael Beck's avatar
Michael Beck committed
26
 * written or stored.
27
28
29
30
 *
 * @param arg   The graph argument with mode reference,
 *             that must be checked.
 */
31
static ptr_access_kind analyze_arg(ir_node *arg, ptr_access_kind bits)
32
{
33
	/* We must visit a node once to avoid endless recursion.*/
34
	mark_irn_visited(arg);
35

36
	foreach_irn_out_r(arg, i, succ) {
37
		if (irn_visited(succ))
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
			continue;

		/* We should not walk over the memory edge.*/
		if (get_irn_mode(succ) == mode_M)
			continue;

		/* If we reach with the recursion a Call node and our reference
		   isn't the address of this Call we accept that the reference will
		   be read and written if the graph of the method represented by
		   "Call" isn't computed else we analyze that graph. If our
		   reference is the address of this
		   Call node that mean the reference will be read.*/
		switch (get_irn_opcode(succ)) {

		case iro_Call: {
53
			ir_node *ptr = get_Call_ptr(succ);
54
55
56
57
58

			if (ptr == arg) {
				/* Hmm: not sure what this is, most likely a read */
				bits |= ptr_access_read;
			} else {
59
				ir_entity *callee = get_Call_callee(succ);
60

61
				if (callee != NULL) {
Matthias Braun's avatar
Matthias Braun committed
62
					for (int p = get_Call_n_params(succ); p-- > 0; ) {
63
64
						if (get_Call_param(succ, p) == arg) {
							/* an arg can be used more than once ! */
65
							bits |= get_method_param_access(callee, p);
66
67
						}
					}
68
				} else if (is_Member(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
69
					/* is be a polymorphic call but callee information is available */
Matthias Braun's avatar
Matthias Braun committed
70
					size_t n_params = get_Call_n_params(succ);
71
72

					/* simply look into ALL possible callees */
73
					for (int c = cg_get_call_n_callees(succ); c-- > 0; ) {
74
						ir_entity *meth_ent = cg_get_call_callee(succ, c);
75
76

						/* unknown_entity is used to signal that we don't know what is called */
77
						if (is_unknown_entity(meth_ent)) {
78
79
80
81
							bits |= ptr_access_all;
							break;
						}

Matthias Braun's avatar
Matthias Braun committed
82
						for (size_t p = n_params; p-- > 0; ) {
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
							if (get_Call_param(succ, p) == arg) {
								/* an arg can be used more than once ! */
								bits |= get_method_param_access(meth_ent, p);
							}
						}
					}
				} else /* can do anything */
					bits |= ptr_access_all;
			}

			/* search stops here anyway */
			continue;
		}
		case iro_Store:
			/* We have reached a Store node => the reference is written or stored. */
			if (get_Store_ptr(succ) == arg) {
				/* written to */
				bits |= ptr_access_write;
			} else {
				/* stored itself */
				bits |= ptr_access_store;
			}

			/* search stops here anyway */
			continue;

		case iro_Load:
			/* We have reached a Load node => the reference is read. */
			bits |= ptr_access_read;

			/* search stops here anyway */
			continue;

		case iro_Conv:
			/* our address is casted into something unknown. Break our search. */
			bits = ptr_access_all;
			break;

		default:
			break;
		}

		/* If we know that, the argument will be read, write and stored, we
		   can break the recursion.*/
		if (bits == ptr_access_all) {
			bits = ptr_access_all;
			break;
		}

		/*
		 * A calculation that do not lead to a reference mode ends our search.
		 * This is dangerous: It would allow to cast into integer and that cast back ...
		 * so, when we detect a Conv we go mad, see the Conv case above.
		 */
		if (!mode_is_reference(get_irn_mode(succ)))
			continue;

		/* follow further the address calculation */
		bits = analyze_arg(succ, bits);
	}
	return bits;
144
145
146
147
148
149
150
151
}

/**
 * Check if a argument of the ir graph with mode
 * reference is read, write or both.
 *
 * @param irg   The ir graph to analyze.
 */
152
153
static void analyze_ent_args(ir_entity *ent)
{
Matthias Braun's avatar
Matthias Braun committed
154
155
	ir_type *mtp     = get_entity_type(ent);
	size_t   nparams = get_method_n_params(mtp);
156

157
	ent->attr.mtd_attr.param_access = NEW_ARR_F(ptr_access_kind, nparams);
158

159
160
161
162
163
	/* If the method haven't parameters we have
	 * nothing to do.
	 */
	if (nparams <= 0)
		return;
164

165
  /* we have not yet analyzed the graph, set ALL access for pointer args */
Matthias Braun's avatar
Matthias Braun committed
166
	for (size_t i = nparams; i-- > 0; ) {
167
168
169
		ir_type *type = get_method_param_type(mtp, i);
		ent->attr.mtd_attr.param_access[i] = is_Pointer_type(type) ? ptr_access_all : ptr_access_none;
	}
170

Matthias Braun's avatar
Matthias Braun committed
171
172
	ir_graph *irg = get_entity_irg(ent);
	if (irg == NULL) {
173
174
175
		/* no graph, no better info */
		return;
	}
176

177
	assure_irg_outs(irg);
Matthias Braun's avatar
Matthias Braun committed
178
	ir_node *irg_args = get_irg_args(irg);
179

180
181
	/* A array to save the information for each argument with
	   mode reference.*/
182
	ptr_access_kind *rw_info = ALLOCAN(ptr_access_kind, nparams);
183

184
	/* We initialize the element with none state. */
Matthias Braun's avatar
Matthias Braun committed
185
	for (size_t i = nparams; i-- > 0; )
186
		rw_info[i] = ptr_access_none;
187

188
189
	/* search for arguments with mode reference
	   to analyze them.*/
190
	foreach_irn_out_r(irg_args, i, arg) {
Matthias Braun's avatar
Matthias Braun committed
191
		ir_mode *arg_mode = get_irn_mode(arg);
192
		unsigned proj_nr  = get_Proj_num(arg);
193

194
195
196
		if (mode_is_reference(arg_mode))
			rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
	}
197

198
	/* copy the temporary info */
Christoph Mallon's avatar
Christoph Mallon committed
199
	MEMCPY(ent->attr.mtd_attr.param_access, rw_info, nparams);
200
201
}

202
203
void analyze_irg_args(ir_graph *irg)
{
204
205
	if (irg == get_const_code_irg())
		return;
206

Matthias Braun's avatar
Matthias Braun committed
207
	ir_entity *entity = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
208
	if (entity == NULL)
209
		return;
210

Matthias Braun's avatar
Matthias Braun committed
211
	if (!entity->attr.mtd_attr.param_access)
Matthias Braun's avatar
Matthias Braun committed
212
		analyze_ent_args(entity);
213
214
}

215
ptr_access_kind get_method_param_access(ir_entity *ent, size_t pos)
216
{
217
#ifndef NDEBUG
218
	ir_type *mtp = get_entity_type(ent);
219
	assert(is_method_variadic(mtp) || pos < get_method_n_params(mtp));
220
#endif
221

222
223
224
225
226
227
	if (ent->attr.mtd_attr.param_access) {
		if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
			return ent->attr.mtd_attr.param_access[pos];
		else
			return ptr_access_all;
	}
228

229
	analyze_ent_args(ent);
230

231
232
233
234
	if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
		return ent->attr.mtd_attr.param_access[pos];
	else
		return ptr_access_all;
235
236
}

237
/* Weights for parameters */
238
enum args_weight {
239
240
241
242
243
244
	null_weight          = 0,   /**< If can't be anything optimized. */
	binop_weight         = 1,   /**< If the argument have mode_weight and take part in binop. */
	const_binop_weight   = 1,   /**< If the argument have mode_weight and take part in binop with a constant.*/
	cmp_weight           = 4,   /**< If the argument take part in cmp. */
	const_cmp_weight     = 10,  /**< If the argument take part in cmp with a constant. */
	indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */
245
246
};

247
/**
248
 * Computes the weight of a method parameter
249
 *
250
 * @param arg  The parameter whose weight is to be computed.
251
 */
252
253
static unsigned calc_method_param_weight(ir_node *arg)
{
254
	/* We mark the nodes to avoid endless recursion */
255
	mark_irn_visited(arg);
256

Matthias Braun's avatar
Matthias Braun committed
257
	unsigned weight = null_weight;
258
	foreach_irn_out_r(arg, i, succ) {
259
		if (irn_visited(succ))
260
261
262
263
264
265
			continue;

		/* We should not walk over the memory edge.*/
		if (get_irn_mode(succ) == mode_M)
			continue;

266
267
268
269
270
271
272
273
		switch (get_irn_opcode(succ)) {
		case iro_Call:
			if (get_Call_ptr(succ) == arg) {
				/* the arguments is used as an pointer input for a call,
				   we can probably change an indirect Call into a direct one. */
				weight += indirect_call_weight;
			}
			break;
Matthias Braun's avatar
Matthias Braun committed
274
		case iro_Cmp: {
275
276
			/* We have reached a cmp and we must increase the
			   weight with the cmp_weight. */
Matthias Braun's avatar
Matthias Braun committed
277
			ir_node *op;
278
279
280
281
282
283
284
285
286
			if (get_Cmp_left(succ) == arg)
				op = get_Cmp_right(succ);
			else
				op = get_Cmp_left(succ);

			if (is_irn_constlike(op)) {
				weight += const_cmp_weight;
			} else
				weight += cmp_weight;
287
			break;
Matthias Braun's avatar
Matthias Braun committed
288
		}
289
		case iro_Cond:
290
291
			/* the argument is used for a SwitchCond, a big win */
			weight += const_cmp_weight * get_irn_n_outs(succ);
292
293
294
295
296
297
298
			break;
		case iro_Id:
			/* when looking backward we might find Id nodes */
			weight += calc_method_param_weight(succ);
			break;
		case iro_Tuple:
			/* unoptimized tuple */
299
			for (unsigned j = get_Tuple_n_preds(succ); j-- > 0; ) {
300
301
302
				ir_node *pred = get_Tuple_pred(succ, j);
				if (pred == arg) {
					/* look for Proj(j) */
303
					foreach_irn_out_r(succ, k, succ_succ) {
304
305
306
						if (get_Proj_num(succ_succ) == j) {
							/* found */
							weight += calc_method_param_weight(succ_succ);
307
308
309
310
311
312
313
314
315
316
317
318
						}
					}
				}
			}
			break;
		default:
			if (is_binop(succ)) {
				/* We have reached a BinOp and we must increase the
				   weight with the binop_weight. If the other operand of the
				   BinOp is a constant we increase the weight with const_binop_weight
				   and call the function recursive.
				 */
Matthias Braun's avatar
Matthias Braun committed
319
				ir_node *op;
320
321
322
323
324
325
326
327
328
329
				if (get_binop_left(succ) == arg)
					op = get_binop_right(succ);
				else
					op = get_binop_left(succ);

				if (is_irn_constlike(op)) {
					weight += const_binop_weight;
					weight += calc_method_param_weight(succ);
				} else
					weight += binop_weight;
330
			} else if (get_irn_arity(succ) == 1) {
331
				/* We have reached a binop and we must increase the
332
333
				   weight with the const_binop_weight and call the function
				   recursive.*/
334
335
				weight += const_binop_weight;
				weight += calc_method_param_weight(succ);
336
337
			}
			break;
338
339
340
		}
	}
	return weight;
341
342
343
}

/**
344
 * Calculate a weight for each argument of an entity.
345
346
347
 *
 * @param ent  The entity of the ir_graph.
 */
348
349
static void analyze_method_params_weight(ir_entity *ent)
{
350
	/* allocate a new array. currently used as 'analysed' flag */
Matthias Braun's avatar
Matthias Braun committed
351
352
	ir_type *mtp      = get_entity_type(ent);
	size_t   nparams  = get_method_n_params(mtp);
353
	ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
354

355
	/* If the method has no parameters, we have nothing to do */
356
357
	if (nparams <= 0)
	  return;
358

359
	/* First we initialize the parameter weights with 0. */
Matthias Braun's avatar
Matthias Braun committed
360
	for (size_t i = nparams; i-- > 0; )
361
		ent->attr.mtd_attr.param_weight[i] = null_weight;
362

Matthias Braun's avatar
Matthias Braun committed
363
	ir_graph *irg = get_entity_irg(ent);
364
365
366
367
	if (irg == NULL) {
		/* no graph, no better info */
		return;
	}
368

369
370
	/* Call algorithm that computes the out edges */
	assure_irg_outs(irg);
371

Matthias Braun's avatar
Matthias Braun committed
372
	ir_node *irg_args = get_irg_args(irg);
373
	foreach_irn_out_r(irg_args, i, arg) {
374
		unsigned const proj_nr = get_Proj_num(arg);
375
		ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
376
	}
377
378
}

379
unsigned get_method_param_weight(ir_entity *ent, size_t pos)
380
{
381
382
	if (!ent->attr.mtd_attr.param_weight)
		analyze_method_params_weight(ent);
383

384
385
386
387
	if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
		return ent->attr.mtd_attr.param_weight[pos];
	else
		return null_weight;
388
389
}

390
391
void analyze_irg_args_weight(ir_graph *irg)
{
392
393
394
	ir_entity *entity = get_irg_entity(irg);
	if (entity == NULL)
		return;
395

396
	assert(is_method_entity(entity));
Matthias Braun's avatar
Matthias Braun committed
397
	if (entity->attr.mtd_attr.param_weight != NULL)
398
		return;
399

400
401
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);
Matthias Braun's avatar
Matthias Braun committed
402
	analyze_method_params_weight(entity);
403
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
404
}