2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * File name: ir/opt/proc_cloning.c
23 * Purpose: procedure cloning
24 * Author: Beyhan Veliev
27 * Copyright: (c) 1998-2005 Universität Karlsruhe
31 * @file proc_cloning.c
33 * The purpose is first to find and analyze functions, that are called
34 * with constant parameter(s).
35 * The second step is to optimize the function that are found from our
36 * analyze. Optimize mean to make a new function with parameters, that
37 * aren't be constant. The constant parameters of the function are placed
38 * in the function graph. They aren't be passed as parameters.
55 #include "proc_cloning.h"
56 #include "analyze_irg_args.h"
67 /* A macro to iterate sets.*/
68 #define ITERATE_SET(set_entries, entry) for(entry = set_first(set_entries); entry; entry = set_next(set_entries))
71 * This struct contains the information quadruple for a Call, which we need to
72 * decide if this function must be cloned.
74 typedef struct quadruple {
75 ir_entity *ent; /**< The entity of our Call. */
76 int pos; /**< Position of a constant argument of our Call. */
77 tarval *tv; /**< The tarval of this argument if Const node. */
78 ir_node **calls; /**< The list of all calls with the same characteristics */
82 * The quadruplets are hold in a sorted list
84 typedef struct entry {
85 quadruple_t q; /**< the quadruple */
86 float weight; /**< its weight */
87 struct entry *next; /**< link to the next one */
90 typedef struct q_set {
91 struct obstack obst; /**< an obstack containing all entries */
92 pset *map; /**< a hash map containing the quadruples */
93 entry_t *heavy_uses; /**< the ordered list of heavy uses */
97 * Compare two quadruplets.
99 * @return zero if they are identically, non-zero else
101 static int entry_cmp(const void *elt, const void *key)
103 const entry_t *e1 = elt;
104 const entry_t *e2 = key;
106 return (e1->q.ent != e2->q.ent) || (e1->q.pos != e2->q.pos) || (e1->q.tv != e2->q.tv);
110 * Hash an element of type entry_t.
112 * @param entry The element to be hashed.
114 static int hash_entry(const entry_t *entry)
116 return HASH_PTR(entry->q.ent) ^ HASH_PTR(entry->q.tv) ^ (entry->q.pos * 9);
120 * Free memory associated with a quadruplet.
122 static void kill_entry(entry_t *entry) {
123 if (entry->q.calls) {
124 DEL_ARR_F(entry->q.calls);
125 entry->q.calls = NULL;
130 * Process a call node.
132 * @param call A ir_node to be checked.
133 * @param callee The entity of the callee
134 * @param hmap The quadruple-set containing the calls with constant parameters
136 static void process_call(ir_node *call, ir_entity *callee, q_set *hmap)
139 entry_t *key, *entry;
143 n_params = get_Call_n_params(call);
145 /* Beware: we cannot clone variadic parameters as well as the
146 * last non-variadic one, which might be needed for the va_start()
149 mtp = get_Call_type(call);
150 if (get_method_variadicity(mtp) != variadicity_non_variadic) {
151 n_params = get_method_first_variadic_param_index(mtp) - 1;
154 /* In this for loop we collect the calls, that have
155 an constant parameter. */
156 for (i = n_params - 1; i >= 0; --i) {
157 call_param = get_Call_param(call, i);
158 if (is_Const(call_param)) {
159 /* we have found a Call to collect and we save the informations,
162 hmap->map = new_pset(entry_cmp, 8);
164 key = obstack_alloc(&hmap->obst, sizeof(*key));
168 key->q.tv = get_Const_tarval(call_param);
173 /* We insert our information in the set, where we collect the calls.*/
174 entry = pset_insert(hmap->map, key, hash_entry(key));
177 obstack_free(&hmap->obst, key);
179 /* add the call to the list */
180 if (! entry->q.calls) {
181 entry->q.calls = NEW_ARR_F(ir_node *, 1);
182 entry->q.calls[0] = call;
185 ARR_APP1(ir_node *, entry->q.calls, call);
191 * Collect all calls in a ir_graph to a set.
193 * @param call A ir_node to be checked.
194 * @param env The quadruple-set containing the calls with constant parameters
196 static void collect_irg_calls(ir_node *call, void *env)
202 /* We collect just "Call" nodes */
204 call_ptr = get_Call_ptr(call);
206 /* Call pointer must be a SymConst*/
207 if (op_SymConst != get_irn_op(call_ptr))
209 /* Call pointer must be the address of an entity.*/
210 if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
213 callee = get_SymConst_entity(call_ptr);
215 /* we can only clone calls to existing entities */
216 if (get_entity_visibility(callee) == visibility_external_allocated)
219 process_call(call, callee, hmap);
224 * Make a name for a clone. The clone name is
225 * the name of the original method suffixed with "_cl_pos_nr".
226 * pos is the pos from our quadruplet and nr is a counter.
228 * @param id The ident of the cloned function.
229 * @param pos The "pos" from our quadruplet.
230 * @param nr A counter for the clones.
232 static ident *get_clone_ident(ident *id, int pos, unsigned nr)
234 char clone_postfix[32];
236 snprintf(clone_postfix, sizeof(clone_postfix), "_cl_%d_%u", pos, nr);
238 return mangle(id, new_id_from_str(clone_postfix));
242 * Pre-Walker: Copies blocks and nodes from the original method graph
243 * to the cloned graph. Fixes the argument projection numbers for
244 * all arguments behind the removed one.
246 * @param irn A node from the original method graph.
247 * @param env The clone graph.
249 static void copy_nodes(ir_node *irn, void *env)
251 ir_node *arg, *irg_args, *irn_copy;
253 ir_graph *clone_irg = env;
255 arg = get_irg_link(clone_irg);
256 irg_args = get_Proj_pred(arg);
258 /* Copy all nodes except the arg. */
260 copy_irn_to_irg(irn, clone_irg);
262 irn_copy = get_irn_link(irn);
264 /* Fix argument numbers */
265 if (is_Proj(irn) && get_Proj_pred(irn) == irg_args) {
266 proj_nr = get_Proj_proj(irn);
267 if (get_Proj_proj(arg) < proj_nr)
268 set_Proj_proj(irn_copy, proj_nr - 1);
273 * Post-walker: Set the predecessors of the copied nodes.
274 * The copied nodes are set as link of their original nodes. The links of
275 * "irn" predecessors are the predecessors of copied node.
277 static void set_preds(ir_node *irn, void *env)
280 ir_node *irn_copy, *pred, *arg;
281 ir_graph *clone_irg = env;
283 arg = get_irg_link(clone_irg);
284 /* Arg is the method argument, that we have replaced by a constant.*/
288 irn_copy = get_irn_link(irn);
291 for (i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) {
292 pred = get_Block_cfgpred(irn, i);
293 /* "End" block must be handled extra, because it is not matured.*/
294 if (get_irg_end_block(current_ir_graph) == irn)
295 add_immBlock_pred(get_irg_end_block(clone_irg), get_irn_link(pred));
297 set_Block_cfgpred(irn_copy, i, get_irn_link(pred));
301 /* First we set the block our copy if it is not a block.*/
302 set_nodes_block(irn_copy, get_irn_link(get_nodes_block(irn)));
303 if (get_irn_op(irn) == op_End) {
304 /* Handle the keep-alives. This must be done separately, because
305 the End node was NOT copied */
306 for (i = 0; i < get_End_n_keepalives(irn); ++i)
307 add_End_keepalive(irn_copy, get_irn_link(get_End_keepalive(irn, i)));
310 for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
311 pred = get_irn_n(irn, i);
312 set_irn_n(irn_copy, i, get_irn_link(pred));
319 * Get the method argument at the position "pos".
321 * @param irg irg that must be cloned.
322 * @param pos The position of the argument.
324 static ir_node *get_irg_arg(ir_graph *irg, int pos)
326 ir_node *irg_args = get_irg_args(irg), *arg = NULL;
329 /* Call algorithm that computes the out edges */
330 if (get_irg_outs_state(irg) != outs_consistent)
331 compute_irg_outs(irg);
333 /* Search the argument with the number pos.*/
334 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
335 ir_node *proj = get_irn_out(irg_args, i);
336 if (pos == get_Proj_proj(proj)) {
339 * More than one arg node found:
340 * We rely on the fact the only one arg exists, so do
341 * a cheap CSE in this case.
343 set_irn_out(irg_args, i, arg);
350 assert(arg && "Argument not found");
355 * Create a new graph for the clone of the method,
356 * that we want to clone.
358 * @param ent The entity of the method that must be cloned.
359 * @param q Our quadruplet.
361 static void create_clone_proc_irg(ir_entity *ent, quadruple_t *q)
363 ir_graph *method_irg, *clone_irg;
364 ir_node *arg, *const_arg;
366 method_irg = get_entity_irg(ent);
368 /* We create the skeleton of the clone irg.*/
369 clone_irg = new_ir_graph(ent, 0);
371 arg = get_irg_arg(get_entity_irg(q->ent), q->pos);
372 /* we will replace the argument in position "q->pos" by this constant. */
373 const_arg = new_r_Const_type(
374 clone_irg, get_nodes_block(arg), get_irn_mode(arg), q->tv,
375 get_method_param_type(get_entity_type(q->ent), q->pos));
377 /* args copy in the cloned graph will be the const. */
378 set_irn_link(arg, const_arg);
380 /* Store the arg that will be replaced here, so we can easily detect it. */
381 set_irg_link(clone_irg, arg);
383 /* We copy the blocks and nodes, that must be in
384 the clone graph and set their predecessors. */
385 irg_walk_graph(method_irg, copy_nodes, set_preds, clone_irg);
387 /* The "cloned" graph must be matured. */
388 mature_immBlock(get_irg_end_block(clone_irg));
389 irg_finalize_cons(clone_irg);
393 * The function create a new entity type
394 * for our clone and set it to clone entity.
396 * @param q Contains information for the method to clone.
397 * @param ent The entity of the clone.
398 * @param nr A pointer to the counter of clones.
400 static void change_entity_type(quadruple_t *q, ir_entity *ent, unsigned *nr)
402 ir_type *mtp, *new_mtp, *tp;
404 int i, j, n_params, n_ress;
406 mtp = get_entity_type(q->ent);
407 tp_name = get_clone_ident(get_type_ident(mtp), q->pos, (*nr)++);
408 n_params = get_method_n_params(mtp);
409 n_ress = get_method_n_ress(mtp);
411 /* Create the new type for our clone. It must have one parameter
412 less then the original.*/
413 new_mtp = new_type_method(tp_name, n_params - 1, n_ress);
415 /* We must set the type of the methods parameters.*/
416 for (i = j = 0; i < n_params; ++i) {
418 /* This is the position of the argument, that we have
422 tp = get_method_param_type(mtp, i);
423 set_method_param_type(new_mtp, j++, tp);
425 /* Copy the methods result types. */
426 for (i = 0; i < n_ress; ++i) {
427 tp = get_method_res_type(mtp, i);
428 set_method_res_type(new_mtp, i, tp);
430 set_entity_type(ent, new_mtp);
434 * Make a clone of a method.
436 * @param q Contains information for the method to clone.
438 static ir_entity *clone_method(quadruple_t *q)
440 ir_entity *new_entity;
444 /* A counter for the clones.*/
445 static unsigned nr = 0;
447 /* We get a new ident for our clone method.*/
448 clone_ident = get_clone_ident(get_entity_ident(q->ent), q->pos, nr);
449 /* We get our entity for the clone method. */
450 new_entity = copy_entity_name(q->ent, clone_ident);
452 /* a cloned entity is always local */
453 set_entity_visibility(new_entity, visibility_local);
455 /* set a ld name here: Should we mangle this ? */
456 set_entity_ld_ident(new_entity, get_entity_ident(new_entity));
458 /* set a new type here. */
459 change_entity_type(q, new_entity, &nr);
461 /* We need now a new ir_graph for our clone method. */
462 create_clone_proc_irg(new_entity, q);
464 /* We must set the atomic value of our "new_entity". */
465 sym.entity_p = new_entity;
466 rem = current_ir_graph;
467 current_ir_graph = get_const_code_irg();
468 new_entity->value = new_SymConst(sym, symconst_addr_ent);
469 current_ir_graph = rem;
471 /* The "new_entity" don't have this information. */
472 new_entity->attr.mtd_attr.param_access = NULL;
473 new_entity->attr.mtd_attr.param_weight = NULL;
479 * Creates a new "cloned" Call node and return it.
481 * @param call The call that must be cloned.
482 * @param new_entity The entity of the cloned function.
483 * @param pos The position of the replaced parameter of this call.
485 static ir_node *new_cl_Call(ir_node *call, ir_entity *new_entity, int pos)
489 int i, n_params, new_params = 0;
492 ir_graph *irg = get_irn_irg(call);
493 ir_node *bl = get_nodes_block(call);
495 sym.entity_p = new_entity;
496 callee = new_r_SymConst(irg, bl, sym, symconst_addr_ent);
498 mtp = get_entity_type(new_entity);
499 n_params = get_Call_n_params(call);
500 NEW_ARR_A(ir_node *, in, n_params - 1);
502 /* we save the parameters of the new call in the array "in" without the
503 * parameter in position "pos", that is replaced with a constant.*/
504 for (i = 0; i < n_params; i++){
506 in[new_params++] = get_Call_param(call, i);
508 /* Create and return the new Call. */
509 return new_r_Call(irg, bl, get_Call_mem(call),
510 callee, n_params - 1, in, get_entity_type(new_entity));
514 * Exchange all Calls stored in the quadruplet to Calls of the cloned entity.
516 * @param q The quadruple
517 * @param cloned_ent The entity of the new function that must be called
520 static void exchange_calls(quadruple_t *q, ir_entity *cloned_ent)
523 ir_node *new_call, *call;
526 /* We iterate the list of the "call".*/
527 for (i = 0; i < ARR_LEN(q->calls); ++i) {
530 /* A clone exist and the copy of "call" in this
531 * clone graph must be exchanged with new one.*/
532 new_call = new_cl_Call(call, cloned_ent, pos);
533 exchange(call, new_call);
538 * The weight formula:
539 * We save one instruction in every caller and param_weight instructions
542 static float calculate_weight(const entry_t *entry) {
543 return ARR_LEN(entry->q.calls) *
544 (get_method_param_weight(entry->q.ent, entry->q.pos) + 1);
548 * After we exchanged all calls, some entries on the list for
549 * the next cloned entity may get invalid, so we have to check
550 * them and may even update the list of heavy uses.
552 static void reorder_weights(q_set *hmap, float threshold)
554 entry_t **adr, *p, *entry;
559 entry = hmap->heavy_uses;
563 len = ARR_LEN(entry->q.calls);
564 for (i = 0; i < len; ++i) {
565 ir_node *ptr, *call = entry->q.calls[i];
567 /* might be exchanged, so skip Id nodes here. */
568 call = skip_Id(call);
570 /* we know, that a SymConst is here */
571 ptr = get_Call_ptr(call);
572 assert(get_irn_op(ptr) == op_SymConst);
574 callee = get_SymConst_entity(ptr);
575 if (callee != entry->q.ent) {
577 * This call is already changed because of a previous
578 * optimization. Remove it from the list.
581 entry->q.calls[i] = entry->q.calls[len];
582 entry->q.calls[len] = NULL;
584 /* the new call should be processed */
585 process_call(call, callee, hmap);
590 /* the length might be changed */
591 ARR_SHRINKLEN(entry->q.calls, len);
593 /* recalculate the weight and resort the heavy uses map */
594 entry->weight = calculate_weight(entry);
596 if (len <= 0 || entry->weight < threshold) {
597 hmap->heavy_uses = entry->next;
600 /* we have changed the list, check the next one */
605 for (p = entry->next; p && entry->weight < p->weight; p = p->next) {
610 hmap->heavy_uses = entry->next;
613 entry = hmap->heavy_uses;
615 /* we have changed the list, check the next one */
621 * Do the procedure cloning. Evaluate a heuristic weight for every
622 * call(..., Const, ...). If the weight is bigger than threshold,
623 * clone the entity and fix the calls.
625 void proc_cloning(float threshold)
627 entry_t *entry = NULL, *p;
632 obstack_init(&hmap.obst);
634 hmap.heavy_uses = NULL;
636 /* initially fill our map by visiting all irgs */
637 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
638 irg = get_irp_irg(i);
639 irg_walk_graph(irg, collect_irg_calls, NULL, &hmap);
642 /* We have the "Call" nodes to optimize in set "set_entries". Our algorithm
643 replace one constant parameter and make a new "Call" node for all found "Calls". It exchange the
644 old one with the new one and the algorithm is called with the new "Call".
646 while (hmap.map || hmap.heavy_uses) {
647 /* We iterate the set and arrange the element of the set in a list.
648 The elements are arranged dependent of their value descending.*/
650 for (entry = pset_first(hmap.map); entry; entry = pset_next(hmap.map)) {
651 entry->weight = calculate_weight(entry);
654 * Do not put entry with a weight < threshold in the list
656 if (entry->weight < threshold) {
661 /* put entry in the heavy uses list */
663 if (! hmap.heavy_uses)
664 hmap.heavy_uses = entry;
666 if (entry->weight >= hmap.heavy_uses->weight) {
667 entry->next = hmap.heavy_uses;
668 hmap.heavy_uses = entry;
671 for (p = hmap.heavy_uses; p->next; p = p->next) {
672 if (entry->weight >= p->next->weight) {
673 entry->next = p->next;
687 /* Print some information about the list. */
688 printf("-----------------\n");
689 for (entry = hmap.heavy_uses; entry; entry = entry->next) {
690 printf("\nweight: is %f\n", entry->weight);
691 ir_printf("Call for Method %E\n", entry->q.ent);
692 printf("Position %i\n", entry->q.pos);
693 ir_printf("Value %T\n", entry->q.tv);
696 entry = hmap.heavy_uses;
698 ir_entity *ent = clone_method(&entry->q);
700 hmap.heavy_uses = entry->next;
702 /* We must exchange the copies of this call in all clones too.*/
703 exchange_calls(&entry->q, ent);
707 * after we exchanged all calls, some entries on the list for
708 * the next cloned entity may get invalid, so we have to check
709 * them and may even update the list of heavy uses.
711 reorder_weights(&hmap, threshold);
714 obstack_free(&hmap.obst, NULL);