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.
35 #include "proc_cloning.h"
36 #include "analyze_irg_args.h"
38 #include "old_fctnames.h"
40 #include "loop_unrolling.h"
47 /* A macro to iterate sets.*/
48 #define ITERATE_SET(set_entries, entry) for(entry = set_first(set_entries); entry; entry = set_next(set_entries))
51 * This struct contains the information quadruple for a Call, which we need to
52 * decide if this function must be cloned.
54 typedef struct quadruple {
55 entity *ent; /**< The entity of our Call. */
56 int pos; /**< Position of a constant argument of our Call. */
57 tarval *tv; /**< The tarval of this argument if Const node. */
58 ir_node **calls; /**< The list of all calls with the same characteristics */
62 * The quadruplets are hold in a sorted list
64 typedef struct entry {
65 quad_t q; /**< the quadruple */
66 float weight; /**< its weight */
67 struct entry *next; /**< link to the next one */
70 typedef struct q_set {
71 struct obstack obst; /**< an obstack containing all entries */
72 pset *map; /**< a hash map containing the quadruples */
73 entry_t *heavy_uses; /**< the ordered list of heavy uses */
77 * Compare two quadruples.
79 * @return 0 if they are identically
81 static int entry_cmp(const void *elt, const void *key)
83 const entry_t *e1 = elt;
84 const entry_t *e2 = key;
86 return (e1->q.ent != e2->q.ent) || (e1->q.pos != e2->q.pos) || (e1->q.tv != e2->q.tv);
90 * Hash a element of typ entry_t
92 * @param entry The element to be hashed.
94 static int hash_entry(const entry_t *entry)
96 return HASH_PTR(entry->q.ent) ^ HASH_PTR(entry->q.tv) ^ (entry->q.pos * 9);
100 * free memory associated with a quadruplet
102 static void kill_entry(entry_t *entry) {
103 if (entry->q.calls) {
104 DEL_ARR_F(entry->q.calls);
105 entry->q.calls = NULL;
110 * Process a call node
112 * @param call A ir_node to be checked.
113 * @param callee The entity of the callee
114 * @param hmap The quadruple-set containing the calls with constant parameters
116 static void process_call(ir_node *call, entity *callee, q_set *hmap)
119 entry_t *key, *entry;
123 n_params = get_Call_n_params(call);
125 /* Beware: we cannot clone variadic parameters as well as the
126 * last non-variadic one, which might be needed for the va_start()
129 mtp = get_Call_type(call);
130 if (get_method_variadicity(mtp) != variadicity_non_variadic) {
131 n_params = get_method_first_variadic_param_index(mtp) - 1;
134 /* In this for loop we collect the calls, that have
135 an constant parameter. */
136 for (i = n_params - 1; i >= 0; --i) {
137 call_param = get_Call_param(call, i);
138 if (is_Const(call_param)) {
139 /* we have found a Call to collect and we save the informations,
142 hmap->map = new_pset(entry_cmp, 8);
144 key = obstack_alloc(&hmap->obst, sizeof(*key));
148 key->q.tv = get_Const_tarval(call_param);
153 /* We insert our information in the set, where we collect the calls.*/
154 entry = pset_insert(hmap->map, key, hash_entry(key));
157 obstack_free(&hmap->obst, key);
159 /* add the call to the list */
160 if (! entry->q.calls) {
161 entry->q.calls = NEW_ARR_F(ir_node *, 1);
162 entry->q.calls[0] = call;
165 ARR_APP1(ir_node *, entry->q.calls, call);
171 * Collect all calls in a ir_graph to a set.
173 * @param call A ir_node to be checked.
174 * @param env The quadruple-set containing the calls with constant parameters
176 static void collect_irg_calls(ir_node *call, void *env)
182 /* We collect just "Call" nodes*/
183 if (get_irn_op(call) == op_Call) {
184 call_ptr = get_Call_ptr(call);
186 /* Call pointer must be a symconst*/
187 if (op_SymConst != get_irn_op(call_ptr))
189 /* Call pointer must be the address of an entity.*/
190 if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
193 callee = get_SymConst_entity(call_ptr);
195 /* we can only clone calls to existing entities */
196 if (get_entity_visibility(callee) == visibility_external_allocated)
199 process_call(call, callee, hmap);
204 * Make a name for the clone. The clone name is
205 * the name of the original method advanced with "_cl_pos_nr".
206 * pos is the pos from our quadruplet and nr is a counter.
208 * @param id The ident of the cloned function.
209 * @param pos The "pos" from our quadruplet.
210 * @param nr A counter for the clones.
212 static ident *get_clone_ident(ident *id, int pos, unsigned nr)
214 char clone_postfix[32];
216 snprintf(clone_postfix, sizeof(clone_postfix), "_cl_%d_%u", pos, nr);
218 return mangle(id, new_id_from_str(clone_postfix));
222 * The function fill the blocks and nodes, that muss be in
223 * the clone graph, from the original method graph. The cloned method
224 * have one argument few, why it is replaced with a constant.
226 * @param irn A node from the original method graph.
227 * @param env The clone graph.
229 static void fill_clone_irg(ir_node *irn, void *env)
231 ir_node *arg, *irg_args, *irn_copy, *link;
236 arg = get_irg_link(clone_irg);
237 irg_args = get_Proj_pred(arg);
239 if (get_irn_op(irn) == op_Call)
240 link = get_irn_link(irn);
242 /* Copy all nodes except the arg. */
244 copy_irn_to_irg(irn, clone_irg);
246 irn_copy = get_irn_link(irn);
248 if (get_irn_op(irn) == op_Call)
249 irn_copy->link = link;
251 /* Fix argument numbers */
252 if (get_irn_op(irn) == op_Proj && get_Proj_pred(irn) == irg_args) {
253 proj_nr = get_Proj_proj(irn);
254 if (get_Proj_proj(arg) < proj_nr)
255 set_Proj_proj(irn_copy, proj_nr - 1);
260 * Set the predecessors of the copied nodes.
261 * The copied nodes are set as link of their original nodes. The links of
262 * "irn" predecessors are the predecessors of copied node.
264 static void set_preds(ir_node *irn, void *env)
267 ir_node *irn_copy, *pred, *arg;
268 ir_graph *clone_irg = env;
270 arg = get_irg_link(clone_irg);
271 /* Arg is the method argument, that we have replaced by a constant.*/
275 irn_copy = get_irn_link(irn);
278 for (i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) {
279 pred = get_Block_cfgpred(irn, i);
280 /* "End" block must be handled extra, because it is not matured.*/
281 if (get_irg_end_block(current_ir_graph) == irn)
282 add_immBlock_pred(get_irg_end_block(clone_irg), get_irn_link(pred));
284 set_Block_cfgpred(irn_copy, i, get_irn_link(pred));
288 /* First we set the block our copy if it is not a block.*/
289 set_nodes_block(irn_copy, get_irn_link(get_nodes_block(irn)));
290 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
291 pred = get_irn_n(irn, i);
292 set_irn_n(irn_copy, i, get_irn_link(pred));
298 * Get the method argument at the position "pos".
300 * @param irg irg that must be cloned.
301 * @param pos The position of the argument.
303 static ir_node *get_irg_arg(ir_graph *irg, int pos)
305 ir_node *irg_args = get_irg_args(irg), *arg = NULL;
308 /* Call algorithm that computes the out edges */
309 if (get_irg_outs_state(irg) != outs_consistent)
312 /* Search the argument with the number pos.*/
313 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
314 ir_node *proj = get_irn_out(irg_args, i);
315 if (pos == get_Proj_proj(proj)) {
318 * More than one arg node found:
319 * We rely on the fact the only one arg exists, so do
320 * a cheap CSE in this case.
322 set_irn_out(irg_args, i, arg);
329 assert(arg && "Argument not found");
334 * Create a new graph for the clone of the method,
335 * that we want to clone.
337 * @param ent The entity of the method that must be cloned.
338 * @param q Our quadruple.
340 static void create_clone_proc_irg(entity *ent, quad_t *q)
342 ir_graph *method_irg, *clone_irg;
343 ir_node *arg, *const_arg;
346 method_irg = get_entity_irg(ent);
348 /* The ir graph of the cloned procedure have one local few,
349 because one of the arguments is replaced by a constant. */
350 loc_n = get_irg_n_loc(method_irg) - 1;
352 /* We create the skeleton of the clone irg.*/
353 clone_irg = new_ir_graph(ent, loc_n);
355 arg = get_irg_arg(get_entity_irg(q->ent), q->pos);
356 /* we will replace the argument in position "q->pos" by this constant. */
357 const_arg = new_r_Const_type(
358 clone_irg, get_nodes_block(arg), get_irn_mode(arg), q->tv,
359 get_method_param_type(get_entity_type(q->ent), q->pos));
361 /* We have this nodes in the new ir_graph, and they must not be copied.*/
362 set_irn_link(arg, const_arg);
364 /* I need this, because "irg_walk_graph" change "current_ir_graph" to passed irg.*/
365 set_irg_link(clone_irg, arg);
367 /* We fill the blocks and nodes, that must be in
368 the clone graph and set their preds.*/
369 irg_walk_graph(method_irg, fill_clone_irg, set_preds, clone_irg);
371 /* The "cloned" ir_graph must be corrected. */
372 mature_block(get_irg_end_block(clone_irg));
373 irg_finalize_cons(clone_irg);
377 * The function create a new entity type
378 * for our clone and set it to clone entity.
380 * @param q Contains information
381 * for the method to clone.
382 * @param ent The entity of the clone.
383 * @param nr A pointer to the counter of clones.
385 static void change_entity_type(quad_t *q, entity *ent, unsigned *nr)
387 ir_type *mtp, *new_mtp, *tp;
389 int i, n_params, n_ress, pos = 0;
391 mtp = get_entity_type(q->ent);
392 tp_name = get_clone_ident(get_type_ident(mtp), q->pos, (*nr)++);
393 n_params = get_method_n_params(mtp);
394 n_ress = get_method_n_ress(mtp);
396 /* Create the new type for our clone. It must have one parameter
397 less then the original.*/
398 new_mtp = new_type_method(tp_name, n_params - 1, n_ress);
400 /* We must set the type of the methods parameters.*/
401 for( i = 0; pos < (n_params - 1); i++){
404 /* This is the position of the argument, that we have
405 replaced, q. m. "i" must be incremented, but "pos" not
406 and nothing else must be done.*/
409 tp = get_method_param_type(mtp, i);
410 set_method_param_type(new_mtp, pos, tp);
413 /* We must set the type of the methods results.*/
414 for( i = 0; i < n_ress; i++){
415 tp = get_method_res_type(mtp, i);
416 set_method_res_type(new_mtp, i, tp);
419 set_entity_type(ent, new_mtp);
423 * Make a clone of a method.
425 * @param q Contains information
426 * for the method to clone.
428 static entity *clone_method(quad_t *q)
434 /* A counter for the clones.*/
435 static unsigned nr = 0;
437 /* We get a new ident for our clone method.*/
438 clone_ident = get_clone_ident(get_entity_ident(q->ent), q->pos, nr);
439 /* We get our entity for the clone method. */
440 new_entity = copy_entity_name(q->ent, clone_ident);
442 /* a cloned entity is always local */
443 set_entity_visibility(new_entity, visibility_local);
445 /* set a ld name here: Should we mangle this ? */
446 set_entity_ld_ident(new_entity, get_entity_ident(new_entity));
448 /* set a new type here.*/
449 change_entity_type(q, new_entity, &nr);
451 /* We need now a new ir_graph for our clone method. */
452 create_clone_proc_irg(new_entity, q);
453 /* We must set the atomic value of our "new_entity". */
454 sym.entity_p = new_entity;
455 rem = current_ir_graph;
456 current_ir_graph = get_const_code_irg();
457 new_entity->value = new_SymConst(sym, symconst_addr_ent);
458 current_ir_graph = rem;
460 /* The "new_entity" have not this information. */
461 new_entity->param_access = NULL;
462 new_entity->param_weight = NULL;
467 /** The function make a new "Call" node and return it.
469 * @param call The call, that muss be exchanged.
470 * @param new_entity The entity of the cloned function.
471 * @param pos The position of the replaced parameter of this call.
473 static ir_node *new_cl_Call(ir_node *call, entity *new_entity, int pos)
477 int i, n_params, new_params = 0;
481 sym.entity_p = new_entity;
482 callee = new_r_SymConst(get_irn_irg(call), get_nodes_block(call), sym, symconst_addr_ent);
484 mtp = get_entity_type(new_entity);
485 n_params = get_Call_n_params(call);
486 in = malloc(sizeof(ir_node*) * (n_params - 1));
488 /* we save the parameters of the new call in the array "in" without the
489 * parameter in position "pos", that is replaced with a constant.*/
490 for(i = 0; i < n_params; i++){
493 in[new_params] = get_Call_param(call, i);
496 /* We make and return the new call.*/
497 return new_r_Call(get_irn_irg(call), get_nodes_block(call), get_Call_mem(call),
498 callee, n_params - 1, in, get_entity_type(new_entity));
502 * Exchange all Calls now to Calls of the cloned entity
504 * @param q The quadruple
505 * @param cloned_ent The entity of the new function, that must be called from the new call.
507 static void exchange_calls(quad_t *q, entity *cloned_ent)
510 ir_node *new_call, *call;
513 /* We iterate the list of the "call".*/
514 for (i = 0; i < ARR_LEN(q->calls); ++i) {
517 /* A clone exist and the copy of "call" in this
518 * clone graph must be exchanged with new one.*/
519 new_call = new_cl_Call(call, cloned_ent, pos);
520 exchange(call, new_call);
525 * The weight formula:
526 * We save one instruction in every caller and param_weight instructions
529 static float calculate_weight(const entry_t *entry) {
530 return ARR_LEN(entry->q.calls) *
531 (get_method_param_weight(entry->q.ent, entry->q.pos) + 1);
535 * after we exchanged all calls, some entries on the list for
536 * the next cloned entity may get invalid, so we have to check
537 * them and may even update the list of heavy uses.
539 static void reorder_weights(q_set *hmap, float threshold)
541 entry_t **adr, *p, *entry;
546 entry = hmap->heavy_uses;
550 len = ARR_LEN(entry->q.calls);
551 for (i = 0; i < len; ++i) {
552 ir_node *ptr, *call = entry->q.calls[i];
554 /* might be exchanged */
555 call = skip_Id(call);
557 /* we know, that a SymConst is here */
558 ptr = get_Call_ptr(call);
559 assert(get_irn_op(ptr) == op_SymConst);
561 callee = get_SymConst_entity(ptr);
562 if (callee != entry->q.ent) {
564 * This call is already changed because of a previous
565 * optimization. Remove it from the list.
568 entry->q.calls[i] = entry->q.calls[len];
569 entry->q.calls[len] = NULL;
571 /* the new call should be processed */
572 process_call(call, callee, hmap);
576 /* the length might be changed */
577 ARR_SHRINKLEN(entry->q.calls, len);
579 /* recalculate the weight and resort the heavy uses map */
580 entry->weight = calculate_weight(entry);
582 if (len <= 0 || entry->weight < threshold) {
583 hmap->heavy_uses = entry->next;
586 /* we have changed the list, check the next one */
591 for (p = entry->next; p && entry->weight < p->weight; p = p->next) {
596 hmap->heavy_uses = entry->next;
599 entry = hmap->heavy_uses;
601 /* we have changed the list, check the next one */
607 * Do the procedure cloning. Evaluate a heuristic weight for every
608 * call(..., Const, ...). If the weight is bigger than threshold,
609 * clone the entity and fix the calls.
611 void proc_cloning(float threshold)
613 entry_t *entry = NULL, *p;
618 obstack_init(&hmap.obst);
620 hmap.heavy_uses = NULL;
622 /* initially fill our map by visiting all irgs */
623 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
624 irg = get_irp_irg(i);
625 irg_walk_graph(irg, collect_irg_calls, NULL, &hmap);
628 /* We have the "Call" nodes to optimize in set "set_entries". Our algorithm
629 replace one constant parameter and make a new "Call" node for all found "Calls". It exchange the
630 old one with the new one and the algorithm is called with the new "Call".
632 while (hmap.map || hmap.heavy_uses) {
633 /* We iterate the set and arrange the element of the set in a list.
634 The elements are arranged dependent of their value descending.*/
636 for (entry = pset_first(hmap.map); entry; entry = pset_next(hmap.map)) {
637 entry->weight = calculate_weight(entry);
640 * Do not put entry with a weight < threshold in the list
642 if (entry->weight < threshold) {
647 /* put entry in the heavy uses list */
649 if (! hmap.heavy_uses)
650 hmap.heavy_uses = entry;
652 if (entry->weight >= hmap.heavy_uses->weight) {
653 entry->next = hmap.heavy_uses;
654 hmap.heavy_uses = entry;
657 for (p = hmap.heavy_uses; p->next; p = p->next) {
658 if (entry->weight >= p->next->weight) {
659 entry->next = p->next;
673 /* Print some information about the list. */
674 printf("-----------------\n");
675 for (entry = hmap.heavy_uses; entry; entry = entry->next) {
676 printf("\nweight: is %f\n", entry->weight);
677 ir_printf("Call for Method %E\n", entry->q.ent);
678 printf("Position %i\n", entry->q.pos);
679 ir_printf("Value %T\n", entry->q.tv);
682 entry = hmap.heavy_uses;
684 entity *ent = clone_method(&entry->q);
686 hmap.heavy_uses = entry->next;
688 /* We must exchange the copies of this call in all clones too.*/
689 exchange_calls(&entry->q, ent);
693 * after we exchanged all calls, some entries on the list for
694 * the next cloned entity may get invalid, so we have to check
695 * them and may even update the list of heavy uses.
697 reorder_weights(&hmap, threshold);
700 obstack_free(&hmap.obst, NULL);