3 * File name: ir/opt/proc_cloning.c
4 * Purpose: procedure cloning
5 * Author: Beyhan Veliev
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
13 * @file proc_cloning.c
15 * The purpose is first to find and analyze functions, that are called
16 * with constant parameter(s).
17 * The second step is to optimize the function that are found from our
18 * analyze. Optimize mean to make a new function with parameters, that
19 * aren't be constant. The constant parameters of the function are placed
20 * in the function graph. They aren't be passed as parameters.
27 //#ifdef HAVE_MALLOC_H
40 #include "proc_cloning.h"
41 #include "analyze_irg_args.h"
43 #include "old_fctnames.h"
45 #include "loop_unrolling.h"
49 /* A macro to iterate sets.*/
50 #define ITERATE_SET(set_entrys, entry) for(entry = set_first(set_entrys); entry; entry = set_next(set_entrys))
53 * This struct contains the information quartuple for a Call, which we need to
54 * decide if this function must be cloned.
56 typedef struct _entry {
58 entity *ent; /**< The entity of our Call. */
59 int pos; /**< Position of a constant argument of our Call. */
60 tarval *tv; /**< The tarval of this constant argument. */
61 ir_node *call; /**< The Call itself. */
62 } t; /**< The heuristic triple. */
64 unsigned num_calls; /**< number of calls */
65 float weight; /**< The estimated weight of this triple. */
66 struct _entry *next; /**< used for linking and sorting */
70 * Compare two triples.
72 * @return 0 if they are identically
74 static int entry_cmp(const void *elt, const void *key, size_t size)
76 const entry_t *c1 = elt;
77 const entry_t *c2 = key;
79 return (c1->t.ent != c2->t.ent) || (c1->t.pos != c2->t.pos) || (c1->t.tv != c2->t.tv);
83 * Hash a element of typ entry_t
85 * @param entry The element to be heshed.
87 static int hash_entry(const entry_t *entry)
89 return HASH_PTR(entry->t.ent) ^ HASH_PTR(entry->t.tv) ^ (entry->t.pos * 9);
93 * Collect all calls in a ir_graph
96 * @param call A ir_node to be checked.
97 * @param env The set where we will collect the calls.
99 static void collect_irg_calls(ir_node *call, void *env)
109 /* We collect just "Call" nodes*/
110 if (get_irn_op(call) != op_Call)
113 call_ptr = get_Call_ptr(call);
115 /* Call pointer must be a symconst*/
116 if (op_SymConst != get_irn_op(call_ptr))
118 /* Call pointer must be the address of an entity.*/
119 if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
122 call_ent = get_SymConst_entity(call_ptr);
124 /* we can only clone calls to existing entities */
125 if (get_entity_visibility(call_ent) == visibility_external_allocated)
128 n_params = get_Call_n_params(call);
130 /* beware: we cannot clone variadic parameters */
131 mtp = get_Call_type(call);
132 if (get_method_variadicity(mtp) != variadicity_non_variadic) {
133 n_params = get_method_first_variadic_param_index(mtp);
136 /* In this for loop we collect the calls, that have
137 an constant parameter. */
138 for (i = n_params - 1; i >= 0; --i) {
139 call_param = get_Call_param(call, i);
140 if (is_Const(call_param)) {
141 /* we have found a Call to collect and we save the informations,
144 key.t.ent = call_ent;
146 key.t.tv = get_Const_tarval(call_param);
150 /* We insert our information in the set, where we collect the calls.*/
151 entry = set_insert(entrys, &key, sizeof(key), hash_entry(&key));
153 /* we found one more */
160 * Make a name for the clone. The clone name is
161 * the name of the original method advanced with "_cl_pos_nr".
162 * pos is the pos from our quartuple und nr is a counter.
164 * @param id The ident of the cloned function.
165 * @param pos The "pos" from our quartuple.
166 * @param nr A counter for the clones.
168 static ident *get_clone_ident(ident *id, int pos, unsigned nr)
170 char clone_postfix[32];
172 snprintf(clone_postfix, sizeof(clone_postfix), "_cl_%d_%u", pos, nr);
174 return mangle(id, new_id_from_str(clone_postfix));
178 * The function fill the bloks and nodes, that muss be in
179 * the clone graph, from the original method graph. The cloned method
180 * have one argument few, why it is replaced with a constan.
182 * @param irn A node from the original method graph.
183 * @param env The clone graph.
185 static void fill_clone_irg(ir_node *irn, void *env)
187 ir_node *arg, *irg_args, *irn_copy, *link;
192 arg = get_irg_link(clone_irg);
193 irg_args = get_Proj_pred(arg);
195 if(get_irn_op(irn) == op_Call)
196 link = get_irn_link(irn);
198 /* We must copied all node outside the argument,
199 that we wont to replace with a constant,
200 the end node and block.*/
201 if(!(irn == arg || get_irg_end_block(current_ir_graph) == irn ||
202 get_irg_end(current_ir_graph) == irn))
203 copy_irn(irn, clone_irg);
205 irn_copy = get_irn_link(irn);
207 if(get_irn_op(irn) == op_Call)
208 irn_copy->link = link;
210 /* I repair the ir graph of the copy block, why it
211 is set wrong from "copy_irn()".*/
213 irn_copy->attr.block.irg = clone_irg;
214 /* If the original function have arguments with a bigger number
215 of the argument's number, that we want to replace, we muss
216 decrement them with one.*/
217 if(get_irn_op(irn) == op_Proj && get_Proj_pred(irn) == irg_args){
218 proj_nr = get_Proj_proj(irn);
219 if(get_Proj_proj(arg) < proj_nr)
220 set_Proj_proj(irn_copy, proj_nr - 1);
224 * Set the predecessors of the copied nodes.
225 * The copied nodes are set as link of their original nodes. The links of
226 * "irn" predecessors are the predecessors of copied node.
228 static void set_preds(ir_node *irn, void *env)
231 ir_node *irn_copy, *pred, *arg;
235 irn_copy = get_irn_link(irn);
237 /* First we set the block our copy if it is not a block.*/
239 set_nodes_block(irn_copy, get_irn_link(get_nodes_block(irn)));
241 arg = get_irg_link(clone_irg);
242 /* Arg is the method argument, that wi have replaced with a constant.*/
246 if(get_irn_op(irn) == op_Block){
247 for(i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--){
248 pred = get_Block_cfgpred(irn, i);
249 /* "End" block muss be covered extra, why it is not matured.*/
250 if(get_irg_end_block(current_ir_graph) == irn)
251 ARR_APP1 (ir_node *, get_irg_end_block(clone_irg)->in, get_irn_link(pred));
253 set_Block_cfgpred(irn_copy, i, get_irn_link(pred));
256 for(i = get_irn_arity(irn) - 1; i >= 0; i--){
257 pred = get_irn_n(irn, i);
258 set_irn_n(irn_copy, i, get_irn_link(pred));
262 * Get the method argument at the position "pos".
264 * @param ent The entity of the function, that muss be cloned.
265 * @param pos The position of the orgument.
267 static ir_node *get_method_arg(entity *ent, int pos)
270 ir_node *irg_args, *arg, *start;
273 irg = get_entity_irg(ent);
275 /* Call algorithm that computes the out edges */
276 if (get_irg_outs_state(irg) != outs_consistent)
278 start = get_irg_start(irg);
279 for(i = get_irn_n_outs(start) - 1; i >= 0; i--){
280 irg_args = get_irn_out(start, i);
281 if(is_Proj(get_irn_out(irg_args,0))){
282 set_irg_args(irg, irg_args);
286 /* Search the argument whit the numer pos.*/
287 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
288 arg = get_irn_out(irg_args, i);
289 if(pos == get_Proj_proj(arg))
295 * Create a new graph for the clone of the procedur,
296 * that we wont to clone.
298 * @param ent The entity of the function, that muss be cloned.
299 * @param t Our quartuple.
301 static void create_clone_proc_irg(entity *ent, struct triple *t)
303 ir_graph *method_irg, *clone_irg;
304 ir_node *arg, *const_arg;
307 method_irg = get_entity_irg(ent);
309 /* The ir graph of the cloned procedur have one local few,
310 why one of the arguments is replaced with a constant.*/
311 loc_n = get_irg_n_loc(method_irg) - 1;
313 /* We create the skeleton of the clone irg.*/
314 clone_irg = new_ir_graph(ent, loc_n);
316 arg = get_method_arg(t->ent, t->pos);
317 /*This is the constante , with that we will replace the argument in position "t->pos".*/
318 const_arg = new_r_Const(clone_irg, get_nodes_block(arg), get_irn_mode(arg), t->tv);
319 /* We have this nodes in the new ir_graph, and they muss not be
321 set_irn_link(arg, const_arg);
322 set_irn_link(get_irg_end(method_irg), get_irg_end(clone_irg));
323 set_irn_link(get_irg_end_block(method_irg), get_irg_end_block(clone_irg));
325 /* I need this, why "irg_walk_graph" change "current_ir_graph" to passed irg.*/
326 set_irg_link(clone_irg, arg);
327 /* We fill the bloks and nodes, that muss be in
328 the clone graph and set their preds.*/
329 irg_walk_graph(method_irg, fill_clone_irg, set_preds, clone_irg);
331 /* The "cloned" ir_graph muss be corrected.*/
332 set_irg_start_block( clone_irg, get_irn_link(get_irg_start_block(method_irg)));
333 set_irg_start( clone_irg, get_irn_link(get_irg_start(method_irg)));
334 mature_block(get_irg_end_block(clone_irg));
335 irg_finalize_cons(clone_irg);
338 * The function create a new entity type
339 * for our clone and set it to clone entity.
341 * @param t Contains information
342 * for the method to clone.
343 * @param ent The entity of the clone.
344 * @param nr A pointer to the counter of clones.
346 static void change_entity_type(struct triple *t, entity *ent, unsigned *nr)
348 type *mtp, *new_mtp, *tp;
350 int i, n_params, n_ress, pos = 0;
352 mtp = get_entity_type(t->ent);
353 tp_name = get_clone_ident(get_type_ident(mtp), t->pos, (*nr)++);
354 n_params = get_method_n_params(mtp);
355 n_ress = get_method_n_ress(mtp);
356 /* Create the new type for our clone. It muss have 1 parameter
357 few then the original.*/
358 new_mtp = new_type_method(tp_name, n_params - 1, n_ress);
360 /* We muss set the type of the methods parameters.*/
361 for( i = 0; pos < (n_params - 1); i++){
364 /* This is the position of the argument, that we have
365 replaced, t. m. "i" muss be incremented, but "pos" not
366 and nothing else muss be done.*/
369 tp = get_method_param_type(mtp, i);
370 set_method_param_type(new_mtp, pos, tp);
373 /* We muss set the type of the methods results.*/
374 for( i = 0; i < n_ress; i++){
375 tp = get_method_res_type(mtp, i);
376 set_method_res_type(new_mtp, i, tp);
379 set_entity_type(ent, new_mtp);
383 * Make a clone of a method.
385 * @param t Contains information
386 * for the method to clone.
388 static entity *clone_method(struct triple *t)
395 /* A counter for the clones.*/
396 static unsigned nr = 0;
398 /* We get a new ident for our clone method.*/
399 clone_ident = get_clone_ident(get_entity_ident(t->ent), t->pos, nr);
400 /* We get our entity for the clone method.*/
401 new_entity = copy_entity_name (t->ent, clone_ident);
403 /* a cloned entity is always local */
404 set_entity_visibility(new_entity, visibility_local);
406 /* set a ld name here: Should we mangle this ? */
407 set_entity_ld_ident(new_entity, get_entity_ident(new_entity));
409 /* set a new type here.*/
410 change_entity_type(t, new_entity, &nr);
412 /* We need naw a new ir_graph for our clone procedure.
413 This will we make with create_clone_proc_irg.*/
414 create_clone_proc_irg(new_entity, t);
415 /* We muss set the atomic value of our "new_entity". */
416 sym.entity_p = new_entity;
417 rem = current_ir_graph;
418 current_ir_graph = get_const_code_irg();
419 new_entity->value = new_SymConst(sym, symconst_addr_ent);
420 current_ir_graph = rem;
421 /* The "new_entity" have not this information.*/
422 new_entity->param_access = NULL;
423 new_entity->param_weight = NULL;
427 /** The functin make a new "Call" node and return it.
429 * @param call The call, that muss be exchanged.
430 * @param new_entity The entity of the cloned function.
431 * @param pos The position of the replaced parameter of this call.
433 static ir_node *new_cl_Call(ir_node *call, entity *new_entity, int pos)
437 int i, n_params, new_params = 0;
441 sym.entity_p = new_entity;
442 callee = new_r_SymConst(get_irn_irg(call), get_nodes_block(call), sym, symconst_addr_ent);
444 mtp = get_entity_type(new_entity);
445 n_params = get_Call_n_params(call);
446 in = malloc(sizeof(ir_node*) * (n_params - 1));
448 /* we save the parameters of the new call in the array "in" without the
449 * parameter in posiotn "pos", that is replaced with a constant.*/
450 for(i = 0; i < n_params; i++){
453 in[new_params] = get_Call_param(call, i);
456 /* We make and return the new call.*/
457 return new_r_Call(get_irn_irg(call), get_nodes_block(call), get_Call_mem(call),
458 callee, n_params - 1, in, get_entity_type(new_entity));
460 /** A call node in the graph is the head of a list, that contains all
461 * clons lf this graph. If a call muss be exchanged in a graph, this muss
462 * be made in all cloned graph too. "wchange_calls" make this.
464 * @param call The call, that muss be exchanged.
465 * @param new_entity The entity of the new function, that must be called from the new call.
466 * @param pos The position of the replaced parameter of "call".
468 static void exchange_calls(ir_node *call, entity *new_entity, int pos)
470 ir_node *copy, *new_call;
473 n_params = get_Call_n_params(call);
474 copy = get_irn_link(call);
476 /* We iterate the list of the "call".*/
477 for( ; copy; copy = get_irn_link(copy)){
478 if(!is_ir_node(copy) ||
479 get_irn_irg(copy) == get_irn_irg(call))
481 /* A clone exist and the copy of "call" in this
482 * clon graph must be exchanged with new one.*/
483 new_call = new_cl_Call(copy, new_entity, pos);
484 exchange(copy, new_call);
485 /* The list muss be updatet too.*/
486 set_irn_link(call, new_call);
491 * Do the procedure cloning. Evaluate a heuristic weight for every
492 * call(..., Const, ...). If the weight is bigger than threshold,
493 * clone the entity and fix the calls.
495 void proc_cloning(float threshold)
497 ir_node *new_call, *link;
498 set *set_entrys, *new_entrys;
499 entry_t *entry,*p, *heavy_uses = NULL, key;
502 /* "set_entrys" contains the Calls to cloning, after
503 the walk over the graph. */
504 set_entrys = new_set(entry_cmp, 8);
508 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
509 irg = get_irp_irg(i);
510 irg_walk_graph(irg, collect_irg_calls, NULL, set_entrys);
512 /* We have the "Call" nodes to optimize in set "set_entrys". Our algorithm
513 replace one constant parameter and make a new "Call" node for all found "Calls". It exchange the
514 old one with the new one and the algorithm is called with the new "Call".
516 while(set_count(set_entrys)){
517 /* We iterate the set and arrange the element of the set in a list.
518 The elements are arranged dependent of their value descending.*/
519 ITERATE_SET(set_entrys, entry) {
520 entry->weight = entry->num_calls *
521 (get_method_param_weight(entry->t.ent, entry->t.pos) + 1);
524 * Do not put entry with a weight < threshold in the list
526 if (entry->weight < threshold)
529 /* put entry in the heavy uses list */
534 if (entry->weight >= heavy_uses->weight) {
535 entry->next = heavy_uses;
539 for (p = heavy_uses; p->next; p = p->next) {
540 if (entry->weight >= p->next->weight) {
541 entry->next = p->next;
552 /* Print some informations about the list. */
553 for (entry = heavy_uses; entry; entry = entry->next) {
554 printf("\nweight: is %f\n", entry->weight);
555 ir_printf("Call for Method %E\n", entry->t.ent);
556 printf("Position %i\n", entry->t.pos);
557 ir_printf("Value %T\n", entry->t.tv);
560 /* "new_entrys" contain already optimized Calls, that muss
561 be optimized again, why we can optimize just one constan
562 parameter at once and when a Call have to constant parameters
563 the algorithm muss be repeated, but we don't need to walk over
565 new_entrys = new_set(entry_cmp, 8);
567 for (entry = heavy_uses; entry; entry = entry->next) {
568 count = set_count(new_entrys);
569 /* The new cloned method shoul be made.*/
570 entity *ent = clone_method(&entry->t);
572 /* The new Call for the new methode should be made.*/
573 new_call = new_cl_Call(entry->t.call, ent, entry->t.pos);
575 /* A call node in the graph is the head of a list, that contains all
576 * clons lf this graph. The "new_call" must be inherits this list.*/
577 set_irn_link(new_call, get_irn_link(entry->t.call));
579 exchange(entry->t.call, new_call);
580 /* We set the new Call in the set "new_entrys" if it
581 have constant parameter.*/
582 collect_irg_calls(new_call, new_entrys);
583 /* We muss exchange the copies ot this call in all clones too.*/
584 exchange_calls(new_call, ent, entry->t.pos);
586 /* The "Calls" in the set "set_entrys" are optimized. */
588 set_entrys = new_set(entry_cmp, 8);
589 /* The set "set_entrys" must contain the new "Calls" to optimize t.m.
590 we must copy all entys of "new_entrys" to "set_entrys"*/
591 ITERATE_SET(new_entrys, entry) {
592 key.t.ent = entry->t.ent;
593 key.t.pos = entry->t.pos;
594 key.t.tv = entry->t.tv;
595 key.t.call = entry->t.call;
598 set_insert(set_entrys, &key, sizeof(key), hash_entry(&key));