proc_cloning.c 19.4 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Michael Beck's avatar
Michael Beck committed
7
8
9
 * @file
 * @brief   Procedure cloning.
 * @author  Beyhan Veliev, Michael Beck
10
 * @brief
11
 *
Beyhan's avatar
Beyhan committed
12
13
14
15
16
17
 * The purpose is first to find and analyze functions, that are called
 * with constant parameter(s).
 * The second step is to optimize the function that are found from our
 * analyze. Optimize mean to make a new function with parameters, that
 * aren't be constant. The constant parameters of the function are placed
 * in the function graph. They aren't be passed as parameters.
18
 */
19
#include "debug.h"
20
#include "iroptimize.h"
21
22
23
24
25
26
27
#include "tv.h"
#include "set.h"
#include "irprog_t.h"
#include "hashptr.h"
#include "irgwalk.h"
#include "analyze_irg_args.h"
#include "irprintf.h"
Beyhan's avatar
Beyhan committed
28
#include "ircons.h"
29
#include "irouts_t.h"
Beyhan's avatar
Beyhan committed
30
#include "irnode_t.h"
31
32
#include "irtools.h"
#include "irgmod.h"
33
#include "array.h"
34
#include "panic.h"
35

36
/**
37
 * This struct contains the information quadruple for a Call, which we need to
38
39
 * decide if this function must be cloned.
 */
40
typedef struct quadruple {
Christoph Mallon's avatar
Christoph Mallon committed
41
42
43
44
	ir_entity *ent;   /**< The entity of our Call. */
	size_t     pos;   /**< Position of a constant argument of our Call. */
	ir_tarval *tv;    /**< The tarval of this argument if Const node. */
	ir_node  **calls; /**< The list of all calls with the same characteristics */
45
} quadruple_t;
46
47
48
49
50

/**
 * The quadruplets are hold in a sorted list
 */
typedef struct entry {
Christoph Mallon's avatar
Christoph Mallon committed
51
52
53
	quadruple_t   q;      /**< the quadruple */
	float         weight; /**< its weight */
	struct entry *next;   /**< link to the next one */
54
55
} entry_t;

56
typedef struct q_set {
Christoph Mallon's avatar
Christoph Mallon committed
57
	struct obstack  obst;       /**< an obstack containing all entries */
Michael Beck's avatar
Michael Beck committed
58
59
	pset           *map;        /**< a hash map containing the quadruples */
	entry_t        *heavy_uses; /**< the ordered list of heavy uses */
60
61
} q_set;

62
/**
Michael Beck's avatar
Michael Beck committed
63
 * Compare two quadruplets.
64
 *
Michael Beck's avatar
Michael Beck committed
65
 * @return zero if they are identically, non-zero else
66
 */
67
68
static int entry_cmp(const void *elt, const void *key)
{
69
70
	const entry_t *e1 = (const entry_t*)elt;
	const entry_t *e2 = (const entry_t*)key;
71

Michael Beck's avatar
Michael Beck committed
72
	return (e1->q.ent != e2->q.ent) || (e1->q.pos != e2->q.pos) || (e1->q.tv != e2->q.tv);
73
74
75
}

/**
Michael Beck's avatar
Michael Beck committed
76
 * Hash an element of type entry_t.
77
 *
Michael Beck's avatar
Michael Beck committed
78
 * @param entry  The element to be hashed.
79
 */
80
static unsigned hash_entry(const entry_t *entry)
81
{
82
	return hash_ptr(entry->q.ent) ^ hash_ptr(entry->q.tv) ^ (unsigned)(entry->q.pos * 9);
83
84
85
}

/**
Michael Beck's avatar
Michael Beck committed
86
 * Free memory associated with a quadruplet.
87
 */
88
89
static void kill_entry(entry_t *entry)
{
Michael Beck's avatar
Michael Beck committed
90
91
92
93
	if (entry->q.calls) {
		DEL_ARR_F(entry->q.calls);
		entry->q.calls = NULL;
	}
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
/**
 * Copies a node to a new irg. The Ins of the new node point to
 * the predecessors on the old irg.  n->link points to the new node.
 *
 * @param n    The node to be copied
 * @param irg  the new irg
 *
 * Does NOT copy standard nodes like Start, End etc that are fixed
 * in an irg. Instead, the corresponding nodes of the new irg are returned.
 * Note further, that the new nodes have no block.
 */
static void copy_irn_to_irg(ir_node *n, ir_graph *irg)
{
	/* do not copy standard nodes */
	ir_node *nn = NULL;
	switch (get_irn_opcode(n)) {
	case iro_NoMem:
		nn = get_irg_no_mem(irg);
		break;

	case iro_Block: {
		ir_graph *old_irg = get_irn_irg(n);
		if (n == get_irg_start_block(old_irg))
			nn = get_irg_start_block(irg);
		else if (n == get_irg_end_block(old_irg))
			nn = get_irg_end_block(irg);
		break;
	}

125
126
127
128
129
130
131
132
133
134
135
136
	case iro_Member: {
		ir_graph *const old_irg = get_irn_irg(n);
		ir_node  *const old_ptr = get_Member_ptr(n);
		if (old_ptr == get_irg_frame(old_irg)) {
			dbg_info  *const dbgi  = get_irn_dbg_info(n);
			ir_node   *const block = get_irg_start_block(irg);
			ir_entity *const ent   = get_entity_link(get_Member_entity(n));
			nn = new_rd_Member(dbgi, block, old_ptr, ent);
		}
		break;
	}

137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
	case iro_Start:
		nn = get_irg_start(irg);
		break;

	case iro_End:
		nn = get_irg_end(irg);
		break;

	case iro_Proj: {
		ir_graph *old_irg = get_irn_irg(n);
		if (n == get_irg_frame(old_irg))
			nn = get_irg_frame(irg);
		else if (n == get_irg_initial_mem(old_irg))
			nn = get_irg_initial_mem(irg);
		else if (n == get_irg_args(old_irg))
			nn = get_irg_args(irg);
		break;
	}
	}

	if (nn) {
		set_irn_link(n, nn);
		return;
	}

	nn = new_ir_node(get_irn_dbg_info(n),
	                 irg,
	                 NULL,            /* no block yet, will be set later */
	                 get_irn_op(n),
	                 get_irn_mode(n),
	                 get_irn_arity(n),
168
	                 get_irn_in(n));
169
170
171
172
173
174
175
176
177


	/* Copy the attributes.  These might point to additional data.  If this
	   was allocated on the old obstack the pointers now are dangling.  This
	   frees e.g. the memory of the graph_arr allocated in new_immBlock. */
	copy_node_attr(irg, n, nn);
	set_irn_link(n, nn);
}

178
/**
Michael Beck's avatar
Michael Beck committed
179
 * Process a call node.
180
 *
181
182
183
 * @param call    A ir_node to be checked.
 * @param callee  The entity of the callee
 * @param hmap    The quadruple-set containing the calls with constant parameters
184
 */
185
186
static void process_call(ir_node *call, ir_entity *callee, q_set *hmap)
{
187
	/* TODO
Christoph Mallon's avatar
Christoph Mallon committed
188
	 * Beware: We cannot clone variadic parameters as well as the
Michael Beck's avatar
Michael Beck committed
189
	 * last non-variadic one, which might be needed for the va_start()
Christoph Mallon's avatar
Christoph Mallon committed
190
	 * magic. */
Michael Beck's avatar
Michael Beck committed
191
192

	/* In this for loop we collect the calls, that have
193
	   a constant parameter. */
Christoph Mallon's avatar
Christoph Mallon committed
194
195
196
	size_t const n_params = get_Call_n_params(call);
	for (size_t i = n_params; i-- > 0;) {
		ir_node *const call_param = get_Call_param(call, i);
Michael Beck's avatar
Michael Beck committed
197
		if (is_Const(call_param)) {
198
199
			/* we have found a Call to collect and we save the information
			 * we need.*/
Christoph Mallon's avatar
Christoph Mallon committed
200
			if (!hmap->map)
Michael Beck's avatar
Michael Beck committed
201
202
				hmap->map = new_pset(entry_cmp, 8);

Christoph Mallon's avatar
Christoph Mallon committed
203
			entry_t *const key = OALLOC(&hmap->obst, entry_t);
Michael Beck's avatar
Michael Beck committed
204
205
206
207
208
209
210
			key->q.ent   = callee;
			key->q.pos   = i;
			key->q.tv    = get_Const_tarval(call_param);
			key->q.calls = NULL;
			key->weight  = 0.0F;
			key->next    = NULL;

211
			/* Insert entry or get existing equivalent entry */
Christoph Mallon's avatar
Christoph Mallon committed
212
			entry_t *const entry = (entry_t*)pset_insert(hmap->map, key, hash_entry(key));
213
			/* Free memory if entry already is in set */
Michael Beck's avatar
Michael Beck committed
214
215
216
217
			if (entry != key)
				obstack_free(&hmap->obst, key);

			/* add the call to the list */
Christoph Mallon's avatar
Christoph Mallon committed
218
219
			if (!entry->q.calls) {
				entry->q.calls = NEW_ARR_F(ir_node*, 1);
Michael Beck's avatar
Michael Beck committed
220
				entry->q.calls[0] = call;
Christoph Mallon's avatar
Christoph Mallon committed
221
			} else {
Michael Beck's avatar
Michael Beck committed
222
				ARR_APP1(ir_node *, entry->q.calls, call);
Christoph Mallon's avatar
Christoph Mallon committed
223
			}
Michael Beck's avatar
Michael Beck committed
224
225
		}
	}
Beyhan's avatar
Beyhan committed
226
}
227
228
229
230
231
232
233

/**
 * Collect all calls in a ir_graph to a set.
 *
 * @param call   A ir_node to be checked.
 * @param env   The quadruple-set containing the calls with constant parameters
 */
234
235
static void collect_irg_calls(ir_node *call, void *env)
{
Christoph Mallon's avatar
Christoph Mallon committed
236
	q_set *const hmap = (q_set*)env;
Michael Beck's avatar
Michael Beck committed
237
238

	/* We collect just "Call" nodes */
239
240
	if (!is_Call(call))
		return;
Christoph Mallon's avatar
Christoph Mallon committed
241
	ir_entity *const callee = get_Call_callee(call);
242
243
	if (callee == NULL)
		return;
Christoph Mallon's avatar
Christoph Mallon committed
244
	ir_graph *const callee_irg = get_entity_linktime_irg(callee);
245
246
	if (callee_irg == NULL)
		return;
Michael Beck's avatar
Michael Beck committed
247

248
	process_call(call, callee, hmap);
249
250
}

Christoph Mallon's avatar
Christoph Mallon committed
251
252
253
254
255
static inline ir_node *get_irn_copy(ir_node *const irn)
{
	return (ir_node*)get_irn_link(irn);
}

Beyhan's avatar
Beyhan committed
256
/**
Michael Beck's avatar
Michael Beck committed
257
258
259
 * Pre-Walker: Copies blocks and nodes from the original method graph
 * to the cloned graph. Fixes the argument projection numbers for
 * all arguments behind the removed one.
Beyhan's avatar
Beyhan committed
260
261
262
263
 *
 * @param irn  A node from the original method graph.
 * @param env  The clone graph.
 */
264
265
static void copy_nodes(ir_node *irn, void *env)
{
Christoph Mallon's avatar
Christoph Mallon committed
266
267
268
	ir_graph *const clone_irg = (ir_graph*)env;
	ir_node  *const arg       = (ir_node*)get_irg_link(clone_irg);
	ir_node  *const irg_args  = get_Proj_pred(arg);
Michael Beck's avatar
Michael Beck committed
269
270
271
272
273
274

	/* Copy all nodes except the arg. */
	if (irn != arg)
		copy_irn_to_irg(irn, clone_irg);

	/* Fix argument numbers */
Christoph Mallon's avatar
Christoph Mallon committed
275
	ir_node *const irn_copy = get_irn_copy(irn);
Michael Beck's avatar
Michael Beck committed
276
	if (is_Proj(irn) && get_Proj_pred(irn) == irg_args) {
Christoph Mallon's avatar
Christoph Mallon committed
277
		unsigned const proj_nr = get_Proj_num(irn);
278
279
		if (get_Proj_num(arg) < proj_nr)
			set_Proj_num(irn_copy, proj_nr - 1);
Michael Beck's avatar
Michael Beck committed
280
	}
Beyhan's avatar
Beyhan committed
281
}
282

Beyhan's avatar
Beyhan committed
283
/**
Michael Beck's avatar
Michael Beck committed
284
 * Post-walker: Set the predecessors of the copied nodes.
Beyhan's avatar
Beyhan committed
285
286
287
 * The copied nodes are set as link of their original nodes. The links of
 * "irn" predecessors are the predecessors of copied node.
 */
288
289
static void set_preds(ir_node *irn, void *env)
{
Christoph Mallon's avatar
Christoph Mallon committed
290
	ir_graph *const clone_irg = (ir_graph*)env;
Michael Beck's avatar
Michael Beck committed
291
292

	/* Arg is the method argument, that we have replaced by a constant.*/
Christoph Mallon's avatar
Christoph Mallon committed
293
	ir_node *const arg = (ir_node*)get_irg_link(clone_irg);
Michael Beck's avatar
Michael Beck committed
294
295
296
	if (arg == irn)
		return;

Christoph Mallon's avatar
Christoph Mallon committed
297
	ir_node  *const irn_copy = get_irn_copy(irn);
Michael Beck's avatar
Michael Beck committed
298
299

	if (is_Block(irn)) {
Christoph Mallon's avatar
Christoph Mallon committed
300
301
302
303
304
305
306
		ir_graph *const irg       = get_irn_irg(irn);
		ir_node  *const end_block = get_irg_end_block(irg);
		for (int i = get_Block_n_cfgpreds(irn); i-- > 0;) {
			ir_node *const pred = get_Block_cfgpred(irn, i);
			/* "End" block must be handled extra, because it is not matured. */
			if (end_block == irn)
				add_immBlock_pred(get_irg_end_block(clone_irg), get_irn_copy(pred));
Michael Beck's avatar
Michael Beck committed
307
			else
Christoph Mallon's avatar
Christoph Mallon committed
308
				set_Block_cfgpred(irn_copy, i, get_irn_copy(pred));
Michael Beck's avatar
Michael Beck committed
309
310
311
		}
	} else {
		/* First we set the block our copy if it is not a block.*/
Christoph Mallon's avatar
Christoph Mallon committed
312
		set_nodes_block(irn_copy, get_irn_copy(get_nodes_block(irn)));
313
		if (is_End(irn)) {
Michael Beck's avatar
Michael Beck committed
314
			/* Handle the keep-alives. This must be done separately, because
Christoph Mallon's avatar
Christoph Mallon committed
315
316
317
			 * the End node was NOT copied */
			for (int i = 0, n = get_End_n_keepalives(irn); i < n; ++i)
				add_End_keepalive(irn_copy, get_irn_copy(get_End_keepalive(irn, i)));
Michael Beck's avatar
Michael Beck committed
318
		} else {
319
			foreach_irn_in_r(irn, i, pred) {
Christoph Mallon's avatar
Christoph Mallon committed
320
				set_irn_n(irn_copy, i, get_irn_copy(pred));
Michael Beck's avatar
Michael Beck committed
321
322
323
			}
		}
	}
Beyhan's avatar
Beyhan committed
324
}
325

Beyhan's avatar
Beyhan committed
326
327
328
/**
 * Get the method argument at the position "pos".
 *
329
330
 * @param irg  irg that must be cloned.
 * @param pos  The position of the argument.
Beyhan's avatar
Beyhan committed
331
 */
332
static ir_node *get_irg_arg(ir_graph *irg, size_t pos)
333
{
Michael Beck's avatar
Michael Beck committed
334
335
336
337
	/* Call algorithm that computes the out edges */
	assure_irg_outs(irg);

	/* Search the argument with the number pos.*/
Christoph Mallon's avatar
Christoph Mallon committed
338
339
	ir_node *arg      = NULL;
	ir_node *irg_args = get_irg_args(irg);
340
	foreach_irn_out_r(irg_args, i, proj) {
341
		if (pos == get_Proj_num(proj)) {
342
343
344
			if (arg != NULL)
				panic("multiple projs for the same argument");
			arg = proj;
Michael Beck's avatar
Michael Beck committed
345
346
347
348
		}
	}
	assert(arg && "Argument not found");
	return arg;
349
}
350

351
352
353
354
355
static void clone_frame(ir_graph *const src_irg, ir_graph *const dst_irg, size_t const param_pos)
{
	ir_type *const src_frame = get_irg_frame_type(src_irg);
	ir_type *const dst_frame = get_irg_frame_type(dst_irg);
	for (size_t i = 0, n = get_compound_n_members(src_frame); i != n; ++i) {
356
		ir_entity       *dst_ent;
357
		ir_entity *const src_ent = get_compound_member(src_frame, i);
358
		ident     *const name    = get_entity_name(src_ent);
359
360
		if (is_parameter_entity(src_ent)) {
			size_t const pos = get_entity_parameter_number(src_ent);
361
362
363
			if (pos == param_pos) {
				panic("specializing parameter with entity not handled yet");
			} else {
364
				dst_ent = clone_entity(src_ent, name, dst_frame);
365
366
				if (pos > param_pos)
					set_entity_parameter_number(dst_ent, pos - 1);
367
368
			}
		} else {
369
			dst_ent = clone_entity(src_ent, name, dst_frame);
370
		}
371
		set_entity_link(src_ent, dst_ent);
372
373
374
	}
}

Beyhan's avatar
Beyhan committed
375
/**
376
377
 * Create a new graph for the clone of the method,
 * that we want to clone.
Beyhan's avatar
Beyhan committed
378
 *
379
 * @param ent The entity of the method that must be cloned.
Michael Beck's avatar
Michael Beck committed
380
 * @param q   Our quadruplet.
Beyhan's avatar
Beyhan committed
381
 */
382
static void create_clone_proc_irg(ir_entity *ent, const quadruple_t *q)
383
{
Christoph Mallon's avatar
Christoph Mallon committed
384
	ir_graph *const method_irg = get_entity_linktime_irg(ent);
385
	ir_reserve_resources(method_irg, IR_RESOURCE_IRN_LINK);
386

Michael Beck's avatar
Michael Beck committed
387
	/* We create the skeleton of the clone irg.*/
Christoph Mallon's avatar
Christoph Mallon committed
388
	ir_graph *const clone_irg  = new_ir_graph(ent, 0);
389
	clone_frame(method_irg, clone_irg, q->pos);
Beyhan's avatar
Beyhan committed
390

Christoph Mallon's avatar
Christoph Mallon committed
391
	ir_node *const arg        = get_irg_arg(get_entity_irg(q->ent), q->pos);
Michael Beck's avatar
Michael Beck committed
392
	/* we will replace the argument in position "q->pos" by this constant. */
Christoph Mallon's avatar
Christoph Mallon committed
393
	ir_node *const const_arg  = new_r_Const(clone_irg, q->tv);
394

Michael Beck's avatar
Michael Beck committed
395
396
	/* args copy in the cloned graph will be the const. */
	set_irn_link(arg, const_arg);
Beyhan's avatar
Beyhan committed
397

Michael Beck's avatar
Michael Beck committed
398
399
	/* Store the arg that will be replaced here, so we can easily detect it. */
	set_irg_link(clone_irg, arg);
400

Michael Beck's avatar
Michael Beck committed
401
402
403
	/* We copy the blocks and nodes, that must be in
	the clone graph and set their predecessors. */
	irg_walk_graph(method_irg, copy_nodes, set_preds, clone_irg);
Beyhan's avatar
Beyhan committed
404

Michael Beck's avatar
Michael Beck committed
405
406
	/* The "cloned" graph must be matured. */
	irg_finalize_cons(clone_irg);
407
	ir_free_resources(method_irg, IR_RESOURCE_IRN_LINK);
Beyhan's avatar
Beyhan committed
408
}
409

Beyhan's avatar
Beyhan committed
410
411
412
413
/**
 * The function create a new entity type
 * for our clone and set it to clone entity.
 *
Michael Beck's avatar
Michael Beck committed
414
 * @param q   Contains information for the method to clone.
Beyhan's avatar
Beyhan committed
415
416
417
 * @param ent The entity of the clone.
 * @param nr  A pointer to the counter of clones.
 **/
418
static void change_entity_type(const quadruple_t *q, ir_entity *ent)
419
{
Christoph Mallon's avatar
Christoph Mallon committed
420
421
422
	ir_type *const mtp      = get_entity_type(q->ent);
	size_t   const n_params = get_method_n_params(mtp);
	size_t   const n_ress   = get_method_n_ress(mtp);
Michael Beck's avatar
Michael Beck committed
423
424
425

	/* Create the new type for our clone. It must have one parameter
	   less then the original.*/
426
	ir_type *const new_mtp  = new_type_method(n_params - 1, n_ress, false, cc_cdecl_set, mtp_no_property);
Michael Beck's avatar
Michael Beck committed
427
428

	/* We must set the type of the methods parameters.*/
Christoph Mallon's avatar
Christoph Mallon committed
429
430
431
	for (size_t i = 0, j = 0; i < n_params; ++i) {
		/* This is the position of the argument, that we have replaced. */
		if (i == q->pos)
432
			continue;
Christoph Mallon's avatar
Christoph Mallon committed
433
		ir_type *const tp = get_method_param_type(mtp, i);
Michael Beck's avatar
Michael Beck committed
434
435
436
		set_method_param_type(new_mtp, j++, tp);
	}
	/* Copy the methods result types. */
Christoph Mallon's avatar
Christoph Mallon committed
437
438
	for (size_t i = 0; i < n_ress; ++i) {
		ir_type *const tp = get_method_res_type(mtp, i);
Michael Beck's avatar
Michael Beck committed
439
440
441
		set_method_res_type(new_mtp, i, tp);
	}
	set_entity_type(ent, new_mtp);
Beyhan's avatar
Beyhan committed
442
443
444
445
446
}

/**
 * Make a clone of a method.
 *
Michael Beck's avatar
Michael Beck committed
447
 * @param q   Contains information for the method to clone.
Beyhan's avatar
Beyhan committed
448
 */
449
static ir_entity *clone_method(const quadruple_t *q)
Matthias Braun's avatar
Matthias Braun committed
450
{
Michael Beck's avatar
Michael Beck committed
451
	/* We get a new ident for our clone method.*/
452
	ident     *const clone_ident = id_unique(get_entity_ident(q->ent));
Michael Beck's avatar
Michael Beck committed
453
	/* We get our entity for the clone method. */
454
455
	ir_type   *const owner       = get_entity_owner(q->ent);
	ir_entity *const new_entity  = clone_entity(q->ent, clone_ident, owner);
Michael Beck's avatar
Michael Beck committed
456
457

	/* a cloned entity is always local */
458
	set_entity_visibility(new_entity, ir_visibility_local);
Michael Beck's avatar
Michael Beck committed
459
460

	/* set a new type here. */
461
	change_entity_type(q, new_entity);
Michael Beck's avatar
Michael Beck committed
462
463
464
465
466

	/* We need now a new ir_graph for our clone method. */
	create_clone_proc_irg(new_entity, q);

	return new_entity;
Beyhan's avatar
Beyhan committed
467
}
468

Michael Beck's avatar
Michael Beck committed
469
470
/**
 * Creates a new "cloned" Call node and return it.
Beyhan's avatar
Beyhan committed
471
 *
Michael Beck's avatar
Michael Beck committed
472
 * @param call        The call that must be cloned.
Beyhan's avatar
Beyhan committed
473
474
475
 * @param new_entity  The entity of the cloned function.
 * @param pos         The position of the replaced parameter of this call.
 **/
476
static ir_node *new_cl_Call(ir_node *call, ir_entity *new_entity, size_t pos)
477
{
Christoph Mallon's avatar
Christoph Mallon committed
478
479
	size_t    const n_params = get_Call_n_params(call);
	ir_node **const in       = ALLOCAN(ir_node*, n_params - 1);
Michael Beck's avatar
Michael Beck committed
480
481
482

	/* we save the parameters of the new call in the array "in" without the
	 * parameter in position "pos", that is replaced with a constant.*/
Christoph Mallon's avatar
Christoph Mallon committed
483
484
	size_t new_params = 0;
	for (size_t i = 0; i < n_params; ++i) {
Michael Beck's avatar
Michael Beck committed
485
486
487
488
		if (pos != i)
			in[new_params++] = get_Call_param(call, i);
	}
	/* Create and return the new Call. */
Christoph Mallon's avatar
Christoph Mallon committed
489
490
491
492
493
494
	ir_node  *const bl     = get_nodes_block(call);
	ir_node  *const mem    = get_Call_mem(call);
	ir_graph *const irg    = get_irn_irg(call);
	ir_node  *const callee = new_r_Address(irg, new_entity);
	ir_type  *const type   = get_entity_type(new_entity);
	return new_r_Call(bl, mem, callee, n_params - 1, in, type);
Beyhan's avatar
Beyhan committed
495
}
496
497

/**
Michael Beck's avatar
Michael Beck committed
498
 * Exchange all Calls stored in the quadruplet to Calls of the cloned entity.
Beyhan's avatar
Beyhan committed
499
 *
500
 * @param q             The quadruple
Michael Beck's avatar
Michael Beck committed
501
502
 * @param cloned_ent    The entity of the new function that must be called
 *                      from the new Call.
Beyhan's avatar
Beyhan committed
503
 */
504
505
static void exchange_calls(quadruple_t *q, ir_entity *cloned_ent)
{
Michael Beck's avatar
Michael Beck committed
506
	/* We iterate the list of the "call".*/
Christoph Mallon's avatar
Christoph Mallon committed
507
508
509
	size_t const pos = q->pos;
	for (size_t i = 0; i < ARR_LEN(q->calls); ++i) {
		ir_node *const call = q->calls[i];
Michael Beck's avatar
Michael Beck committed
510
		/* A clone exist and the copy of "call" in this
Christoph Mallon's avatar
Christoph Mallon committed
511
512
		 * clone graph must be exchanged with new one. */
		ir_node *const new_call = new_cl_Call(call, cloned_ent, pos);
Michael Beck's avatar
Michael Beck committed
513
514
		exchange(call, new_call);
	}
515
516
517
518
519
520
521
}

/**
 * The weight formula:
 * We save one instruction in every caller and param_weight instructions
 * in the callee.
 */
522
523
static float calculate_weight(const entry_t *entry)
{
Michael Beck's avatar
Michael Beck committed
524
	return ARR_LEN(entry->q.calls) *
525
		(float)(get_method_param_weight(entry->q.ent, entry->q.pos) + 1);
526
527
}

Michael Beck's avatar
Michael Beck committed
528
529
/**
 * After we exchanged all calls, some entries on the list for
530
531
532
 * the next cloned entity may get invalid, so we have to check
 * them and may even update the list of heavy uses.
 */
533
534
static void reorder_weights(q_set *hmap, float threshold)
{
535
restart:
Christoph Mallon's avatar
Christoph Mallon committed
536
537
538
	;
	entry_t *const entry = hmap->heavy_uses;
	if (!entry)
Michael Beck's avatar
Michael Beck committed
539
540
		return;

Christoph Mallon's avatar
Christoph Mallon committed
541
542
	size_t len = ARR_LEN(entry->q.calls);
	for (size_t i = 0; i < len;) {
Michael Beck's avatar
Michael Beck committed
543
		/* might be exchanged, so skip Id nodes here. */
Christoph Mallon's avatar
Christoph Mallon committed
544
		ir_node   *const call   = skip_Id(entry->q.calls[i]);
545
		/* we know, that an Address is here */
546
		ir_entity *const callee = get_Call_callee(call);
Michael Beck's avatar
Michael Beck committed
547
		if (callee != entry->q.ent) {
Christoph Mallon's avatar
Christoph Mallon committed
548
549
			/* This call is already changed because of a previous
			 * optimization. Remove it from the list. */
Michael Beck's avatar
Michael Beck committed
550
			--len;
Christoph Mallon's avatar
Christoph Mallon committed
551
			entry->q.calls[i]   = entry->q.calls[len];
Michael Beck's avatar
Michael Beck committed
552
553
554
555
			entry->q.calls[len] = NULL;

			/* the new call should be processed */
			process_call(call, callee, hmap);
Christoph Mallon's avatar
Christoph Mallon committed
556
557
		} else {
			++i;
Michael Beck's avatar
Michael Beck committed
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
		}
	}

	/* the length might be changed */
	ARR_SHRINKLEN(entry->q.calls, len);

	/* recalculate the weight and resort the heavy uses map */
	entry->weight = calculate_weight(entry);

	if (len <= 0 || entry->weight < threshold) {
		hmap->heavy_uses = entry->next;
		kill_entry(entry);

		/* we have changed the list, check the next one */
		goto restart;
	}

Christoph Mallon's avatar
Christoph Mallon committed
575
576
	entry_t **adr = NULL;
	for (entry_t *p = entry->next; p && entry->weight < p->weight; p = p->next) {
Michael Beck's avatar
Michael Beck committed
577
578
579
580
581
582
583
584
585
586
587
		adr = &p->next;
	}

	if (adr) {
		hmap->heavy_uses = entry->next;
		entry->next      = *adr;
		*adr             = entry;

		/* we have changed the list, check the next one */
		goto restart;
	}
Beyhan's avatar
Beyhan committed
588
}
589

590
591
void proc_cloning(float threshold)
{
592
593
594
595
596
	DEBUG_ONLY(firm_dbg_module_t *dbg;)

	/* register a debug mask */
	FIRM_DBG_REGISTER(dbg, "firm.opt.proc_cloning");

Christoph Mallon's avatar
Christoph Mallon committed
597
	q_set hmap;
Michael Beck's avatar
Michael Beck committed
598
599
600
601
602
	obstack_init(&hmap.obst);
	hmap.map        = NULL;
	hmap.heavy_uses = NULL;

	/* initially fill our map by visiting all irgs */
603
	all_irg_walk(collect_irg_calls, NULL, &hmap);
Michael Beck's avatar
Michael Beck committed
604
605
606
607
608
609
610
611
612

	/* We have the "Call" nodes to optimize in set "set_entries". Our algorithm
	   replace one constant parameter and make a new "Call" node for all found "Calls". It exchange the
	   old one with the new one and the algorithm is called with the new "Call".
	 */
	while (hmap.map || hmap.heavy_uses) {
		/* We iterate the set and arrange the element of the set in a list.
		   The elements are arranged dependent of their value descending.*/
		if (hmap.map) {
613
			foreach_pset(hmap.map, entry_t, entry) {
Michael Beck's avatar
Michael Beck committed
614
615
616
617
618
619
620
621
622
623
624
				entry->weight = calculate_weight(entry);

				/*
				 * Do not put entry with a weight < threshold in the list
				 */
				if (entry->weight < threshold) {
					kill_entry(entry);
					continue;
				}

				/* put entry in the heavy uses list */
Christoph Mallon's avatar
Christoph Mallon committed
625
626
627
628
629
				for (entry_t **anchor = &hmap.heavy_uses;; anchor = &(*anchor)->next) {
					if (!*anchor || entry->weight >= (*anchor)->weight) {
						entry->next = *anchor;
						*anchor     = entry;
						break;
Michael Beck's avatar
Michael Beck committed
630
631
632
633
634
635
636
					}
				}
			}
			del_pset(hmap.map);
			hmap.map = NULL;
		}

637
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
638
		/* Print some information about the list. */
639
		DB((dbg, LEVEL_2, "-----------------\n"));
640
		for (entry_t *entry = hmap.heavy_uses; entry; entry = entry->next) {
641
642
643
644
			DB((dbg, LEVEL_2, "\nweight: is %f\n", entry->weight));
			DB((dbg, LEVEL_2, "Call for Method %E\n", entry->q.ent));
			DB((dbg, LEVEL_2, "Position %zu\n", entry->q.pos));
			DB((dbg, LEVEL_2, "Value %T\n", entry->q.tv));
Michael Beck's avatar
Michael Beck committed
645
		}
646
#endif
647
		entry_t *const entry = hmap.heavy_uses;
Michael Beck's avatar
Michael Beck committed
648
		if (entry) {
Christoph Mallon's avatar
Christoph Mallon committed
649
650
			quadruple_t *const qp  = &entry->q;
			ir_entity   *const ent = clone_method(qp);
651
			DB((dbg, LEVEL_1, "Cloned <%+F, %zu, %T> info %+F\n", qp->ent, qp->pos, qp->tv, ent));
Michael Beck's avatar
Michael Beck committed
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667

			hmap.heavy_uses = entry->next;

			/* We must exchange the copies of this call in all clones too.*/
			exchange_calls(&entry->q, ent);
			kill_entry(entry);

			/*
			 * after we exchanged all calls, some entries on the list for
			 * the next cloned entity may get invalid, so we have to check
			 * them and may even update the list of heavy uses.
			 */
			reorder_weights(&hmap, threshold);
		}
	}
	obstack_free(&hmap.obst, NULL);
668
}