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
29 #include "proc_cloning.h"
30 #include "analyze_irg_args.h"
33 /* A macro to iterate sets.*/
34 #define ITERATE_SET(set_entrys, entry) for(entry = set_first(set_entrys); entry; entry = set_next(set_entrys))
37 * This struct contains the information triple for a Call, which we need to
38 * decide if this function must be cloned.
40 typedef struct _entry {
42 entity *ent; /**< The entity of our Call. */
43 int pos; /**< Position of a constant argument of our Call. */
44 tarval *tv; /**< The tarval of this constant argument. */
45 } t; /**< The heuristic triple. */
47 float weight; /**< The estimated weight of this triple. */
48 struct _entry *next; /**< used for linking and sorting */
52 * Compare two triples.
54 * @return 0 if they are identically
56 static int entry_cmp(const void *elt, const void *key, size_t size)
58 const entry_t *c1 = elt;
59 const entry_t *c2 = key;
61 return (c1->t.ent != c2->t.ent) || (c1->t.pos != c2->t.pos) || (c1->t.tv != c2->t.tv);
65 * Hash a element of typ entry_t
67 * @param name A string (the name of the method)
68 * @param length The length of this string
69 * @param pos A integer value.
71 static int hash_entry(const entry_t *entry)
73 return HASH_PTR(entry->t.ent) ^ HASH_PTR(entry->t.tv) ^ (entry->t.pos * 9);
77 * Collect all calls in a ir_graph
80 * @param call A ir_node to be checked.
81 * @param env The set where we will collect the calls.
83 static void collect_irg_calls(ir_node *call, void *env)
93 /* We collect just "Call" nodes*/
94 if (get_irn_op(call) != op_Call)
97 call_ptr = get_Call_ptr(call);
99 /* Call pointer must be a symconst*/
100 if (op_SymConst != get_irn_op(call_ptr))
102 /* Call pointer must be the address of an entity.*/
103 if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
107 call_ent = get_SymConst_entity(call_ptr);
109 /* In this for loop we collect the calls, that have
110 an constant parameter. */
111 for (i = get_Call_n_params(call) - 1; i >= 0; i--) {
112 call_param = get_Call_param(call, i);
113 if (is_Const(call_param)) {
114 /* we have found a Call to collect and we save the informations,
116 key.t.ent = call_ent;
118 key.t.tv = get_Const_tarval(call_param);
121 /* We insert our information in the set, where we collect the calls.*/
122 entry = set_insert(entrys, &key, sizeof(key), hash_entry(&key));
124 /* we found one more */
125 entry->weight += 1.0f;
131 * Do the procedure cloning. Evaluate a heuristic weight for every
132 * call(..., Const, ...). If the weight is bigger than threshold,
133 * clone the entity and fix the calls.
135 void proc_cloning(float threshold)
138 entry_t *entry, *p, *heavy_uses = NULL;
142 set_entrys = new_set(entry_cmp, 8);
145 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
146 irg = get_irp_irg(i);
147 irg_walk_graph(irg, collect_irg_calls, NULL, set_entrys);
150 /* We iterate the set and arrange the element of the set in a plist'
151 The elements are arranged dependent of their value descending.*/
152 ITERATE_SET(set_entrys, entry) {
153 entry->weight *= get_method_param_weight(entry->t.ent, entry->t.pos);
156 * Do not put entry with a weight < threshold in the list
158 if (entry->weight < threshold)
161 /* put entry in the heavy uses list */
166 if (entry->weight >= heavy_uses->weight) {
167 entry->next = heavy_uses;
171 for (p = heavy_uses; p->next; p = p->next) {
172 if (entry->weight >= p->next->weight) {
173 entry->next = p->next;
184 /* Print some informations about the list. */
185 for (entry = heavy_uses; entry; entry = entry->next) {
186 printf("\nweight: is %f\n", entry->weight);
187 ir_printf("Call for Method %E\n", entry->t.ent);
188 printf("Position %i\n", entry->t.pos);
189 ir_printf("Value %T\n", entry->t.tv);