4 * @author Sebastian Hack
5 * @brief Machine dependent firm optimizations.
14 #include "irgraph_t.h"
21 #include "dbginfo_t.h"
22 #include "iropt_dbg.h"
33 /** The params got from the factory in arch_dep_init(...). */
34 static const arch_dep_params_t *params = NULL;
36 /** The bit mask, which optimizations to apply. */
37 static arch_dep_opts_t opts;
39 void arch_dep_init(arch_dep_params_factory_t factory)
47 void arch_dep_set_opts(arch_dep_opts_t the_opts) {
51 ir_node *arch_dep_replace_mul_with_shifts(ir_node *irn)
53 ir_node *block = get_nodes_block(irn);
55 ir_node *operand = NULL;
56 ir_node *left, *right;
57 ir_mode *mode = get_irn_mode(irn);
60 /* If the architecture dependent optimizations were not initialized
61 or this optimization was not enabled. */
62 if(params == NULL || (opts & arch_dep_mul_to_shift) == 0)
66 && get_irn_opcode(irn) == iro_Mul
67 && mode_is_int(mode)) {
69 left = get_binop_left(irn);
70 right = get_binop_right(irn);
72 /* Look, if one operand is a constant. */
73 if(get_irn_opcode(left) == iro_Const) {
74 tv = get_Const_tarval(left);
76 } else if(get_irn_opcode(right) == iro_Const) {
77 tv = get_Const_tarval(right);
82 int maximum_shifts = params->maximum_shifts;
83 int also_use_subs = params->also_use_subs;
84 int highest_shift_amount = params->highest_shift_amount;
86 char *bitstr = get_tarval_bitpattern(tv);
92 char compr[MAX_BITSTR];
96 int shift_with_sub[MAX_BITSTR] = { 0 };
97 int shift_without_sub[MAX_BITSTR] = { 0 };
98 int shift_with_sub_pos = 0;
99 int shift_without_sub_pos = 0;
103 int val = (int) get_tarval_long(tv);
104 fprintf(stderr, "Found mul with %d(%x) = ", val, val);
105 for(p = bitstr; *p != '\0'; p++)
111 for(p = bitstr; *p != '\0'; p++) {
115 case -1: // The last was 1 we are now at 0
116 case 1: // The last was 0 and we are now at 1
117 compr[compr_len++] = counter;
126 compr[compr_len++] = counter;
131 const char *prefix = "";
132 for(i = 0; i < compr_len; i++, prefix = ",")
133 fprintf(stderr, "%s%d", prefix, compr[i]);
138 // Go over all recorded one groups.
141 for(i = 1; i < compr_len; i = end_of_group + 2) {
142 int j, zeros_in_group, ones_in_group;
144 ones_in_group = compr[i];
147 // Scan for singular 0s in a sequence
148 for(j = i + 1; j < compr_len && compr[j] == 1; j += 2) {
150 ones_in_group += (j + 1 < compr_len ? compr[j + 1] : 0);
152 end_of_group = j - 1;
154 if(zeros_in_group >= ones_in_group - 1)
158 fprintf(stderr, " i:%d, eg:%d\n", i, end_of_group);
161 singleton = compr[i] == 1 && i == end_of_group;
162 for(j = i; j <= end_of_group; j += 2) {
163 int curr_ones = compr[j];
164 int biased_curr_bit = curr_bit + 1;
168 fprintf(stderr, " j:%d, ones:%d\n", j, curr_ones);
171 // If this ones group is a singleton group (it has no
172 // singleton zeros inside
174 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
176 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
178 for(k = 0; k < curr_ones; k++)
179 shift_without_sub[shift_without_sub_pos++] = biased_curr_bit + k;
181 curr_bit += curr_ones;
182 biased_curr_bit = curr_bit + 1;
184 if(!singleton && j == end_of_group)
185 shift_with_sub[shift_with_sub_pos++] = biased_curr_bit;
186 else if(j != end_of_group)
187 shift_with_sub[shift_with_sub_pos++] = -biased_curr_bit;
189 curr_bit += compr[j + 1];
195 int *shifts = shift_with_sub;
196 int n = shift_with_sub_pos;
197 int highest_shift_wide = 0;
198 int highest_shift_seq = 0;
201 /* If we may not use subs, or we can achive the same with adds,
203 if(!also_use_subs || shift_with_sub_pos >= shift_without_sub_pos) {
204 shifts = shift_without_sub;
205 n = shift_without_sub_pos;
208 /* If the number of needed shifts exceeds the given maximum,
209 use the Mul and exit. */
210 if(n > maximum_shifts) {
212 fprintf(stderr, "Only allowed %d shifts, but %d are needed\n",
218 /* Compute the highest shift needed for both, the
219 sequential and wide representations. */
220 for(i = 0; i < n; i++) {
221 int curr = abs(shifts[i]);
222 int curr_seq = curr - last;
224 highest_shift_wide = curr > highest_shift_wide ? curr
225 : highest_shift_wide;
226 highest_shift_seq = curr_seq > highest_shift_seq ? curr_seq
232 /* If the highest shift amount is greater than the given limit,
234 if(highest_shift_seq > highest_shift_amount) {
236 fprintf(stderr, "Shift argument %d exceeds maximum %d\n",
237 highest_shift_seq, highest_shift_amount);
242 /* If we have subs, we cannot do sequential. */
243 if(1 /* also_use_subs */) {
245 ir_node *curr = NULL;
250 int curr_shift = shifts[i];
251 int sub = curr_shift < 0;
252 int amount = abs(curr_shift) - 1;
253 ir_node *aux = operand;
256 assert(amount >= 0 && "What is a negative shift??");
259 tarval *shift_amount = new_tarval_from_long(amount, mode_Iu);
260 ir_node *cnst = new_r_Const(current_ir_graph, block, mode_Iu, shift_amount);
261 aux = new_r_Shl(current_ir_graph, block, operand, cnst, mode);
266 curr = new_r_Sub(current_ir_graph, block, curr, aux, mode);
268 curr = new_r_Add(current_ir_graph, block, curr, aux, mode);
280 const char *prefix = "";
281 for(i = 0; i < n; i++) {
282 fprintf(stderr, "%s%d", prefix, shifts[i]);
285 fprintf(stderr, "\n");
298 stat_arch_dep_replace_mul_with_shifts(irn);
304 static const arch_dep_params_t default_params = {
305 1, /* also use subs */
306 4, /* maximum shifts */
307 31 /* maximum shift amount */
310 const arch_dep_params_t *arch_dep_default_factory(void) {
311 return &default_params;