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)
106 call_ent = get_SymConst_entity(call_ptr);
108 /* we can only clone calls to existing entities */
109 if (get_entity_visibility(call_ent) == visibility_external_allocated)
112 n_params = get_Call_n_params(call);
114 /* beware: we cannot clone variadic parameters */
115 mtp = get_Call_type(call);
116 if (get_method_variadicity(mtp) == variadicity_non_variadic) {
117 n_params = get_method_first_variadic_param_index(mtp);
120 /* In this for loop we collect the calls, that have
121 an constant parameter. */
122 for (i = n_params - 1; i >= 0; i--) {
123 call_param = get_Call_param(call, i);
124 if (is_Const(call_param)) {
125 /* we have found a Call to collect and we save the informations,
127 key.t.ent = call_ent;
129 key.t.tv = get_Const_tarval(call_param);
132 /* We insert our information in the set, where we collect the calls.*/
133 entry = set_insert(entrys, &key, sizeof(key), hash_entry(&key));
135 /* we found one more */
136 entry->weight += 1.0f;
142 * Do the procedure cloning. Evaluate a heuristic weight for every
143 * call(..., Const, ...). If the weight is bigger than threshold,
144 * clone the entity and fix the calls.
146 void proc_cloning(float threshold)
149 entry_t *entry, *p, *heavy_uses = NULL;
153 set_entrys = new_set(entry_cmp, 8);
156 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
157 irg = get_irp_irg(i);
158 irg_walk_graph(irg, collect_irg_calls, NULL, set_entrys);
161 /* We iterate the set and arrange the element of the set in a plist'
162 The elements are arranged dependent of their value descending.*/
163 ITERATE_SET(set_entrys, entry) {
164 entry->weight *= (get_method_param_weight(entry->t.ent, entry->t.pos) + 1);
167 * Do not put entry with a weight < threshold in the list
169 if (entry->weight < threshold)
172 /* put entry in the heavy uses list */
177 if (entry->weight >= heavy_uses->weight) {
178 entry->next = heavy_uses;
182 for (p = heavy_uses; p->next; p = p->next) {
183 if (entry->weight >= p->next->weight) {
184 entry->next = p->next;
195 /* Print some informations about the list. */
196 for (entry = heavy_uses; entry; entry = entry->next) {
197 printf("\nweight: is %f\n", entry->weight);
198 ir_printf("Call for Method %E\n", entry->t.ent);
199 printf("Position %i\n", entry->t.pos);
200 ir_printf("Value %T\n", entry->t.tv);