x86_address_mode.c 14.3 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
8
 */

/**
 * @file
 * @brief       This file contains functions for matching firm graphs for
9
 *              nodes that can be used as address mode for x86 instructions
10
11
 * @author      Matthias Braun
 */
Matthias Braun's avatar
Matthias Braun committed
12
13
#include "x86_address_mode.h"

14
15
#include <inttypes.h>
#include "bearch.h"
16
#include "bediagnostic.h"
17
#include "beemitter.h"
18
#include "beirg.h"
Matthias Braun's avatar
Matthias Braun committed
19
20
#include "belive.h"
#include "benode.h"
21
#include "betranshlp.h"
Matthias Braun's avatar
Matthias Braun committed
22
#include "beutil.h"
23
#include "iredges_t.h"
24
#include "irgwalk.h"
Matthias Braun's avatar
Matthias Braun committed
25
26
#include "irnode_t.h"
#include "irprintf.h"
27

28
29
static bitset_t *non_address_mode_nodes;

Matthias Braun's avatar
Matthias Braun committed
30
31
static bool tarval_possible(ir_tarval *tv)
{
32
33
34
35
36
37
	ir_mode *mode = get_tarval_mode(tv);
	if (get_mode_size_bits(mode) <= 32) {
		assert(tarval_is_long(tv));
		return true;
	}

Matthias Braun's avatar
Matthias Braun committed
38
39
	if (!tarval_is_long(tv))
		return false;
40
	/* immediates on x86_64 are at most 32bit and get sign extended */
Matthias Braun's avatar
Matthias Braun committed
41
42
43
44
45
	long    val   = get_tarval_long(tv);
	int32_t val32 = (long)val;
	return val == (long)val32;
}

46
47
static bool eat_imm(x86_address_t *const addr, ir_node const *const node,
                    bool basereg_usable)
48
{
Michael Beck's avatar
Michael Beck committed
49
	switch (get_irn_opcode(node)) {
50
51
52
53
	case iro_Add:
		/* Add is supported as long as both operands are immediates. */
		return
			!x86_is_non_address_mode_node(node) &&
54
55
			eat_imm(addr, get_Add_left(node), basereg_usable) &&
			eat_imm(addr, get_Add_right(node), basereg_usable);
56

57
	case iro_Address:
58
		/* The first Address of a DAG can be folded into an immediate. */
59
		if (addr->imm.entity)
60
			return false;
61
		addr->imm.entity = get_Address_entity(node);
62
		addr->imm.kind = X86_IMM_ADDR;
63
		if (is_tls_entity(addr->imm.entity))
64
65
66
67
68
69
70
			addr->tls_segment = true;
		return true;

	case iro_Const: {
		/* Add the value to the offset. */
		ir_tarval *const tv = get_Const_tarval(node);
		if (!tarval_possible(tv))
71
			return false;
72
		addr->imm.offset += get_tarval_long(tv);
73
		return true;
74
	}
75

76
	case iro_Unknown:
77
		/* Use '0' for Unknowns. */
78
		return true;
79
80

	default:
Matthias Braun's avatar
Matthias Braun committed
81
82
83
84
		if (be_is_Relocation(node)) {
			if (addr->imm.entity)
				return false;
			addr->imm.entity = be_get_Relocation_entity(node);
85
86
87
88
89
90
91
92
			x86_immediate_kind_t const kind
				= (x86_immediate_kind_t)be_get_Relocation_kind(node);
			addr->imm.kind = kind;
			if (kind == X86_IMM_GOTPCREL || kind == X86_IMM_PCREL) {
				if (!basereg_usable)
					return false;
				addr->ip_base = true;
			}
Matthias Braun's avatar
Matthias Braun committed
93
94
			return true;
		}
95
		/* All other nodes are no immediates. */
96
		return false;
97
98
99
	}
}

Michael Beck's avatar
Michael Beck committed
100
/**
101
 * Place a DAG with root @p node into an address mode.
Michael Beck's avatar
Michael Beck committed
102
 *
103
 * @param addr    the address mode data so far (only modified on success)
Michael Beck's avatar
Michael Beck committed
104
 * @param node    the node
105
106
 *
 * @return Whether the whole DAG at @p node could be matched as immediate.
Michael Beck's avatar
Michael Beck committed
107
 */
108
109
static bool eat_immediate(x86_address_t *const addr, ir_node const *const node,
                          bool basereg_usable)
110
{
111
	x86_address_t try_addr = *addr;
112
	if (eat_imm(&try_addr, node, basereg_usable)) {
113
114
		*addr = try_addr;
		return true;
115
	}
116
	return false;
117
118
}

Michael Beck's avatar
Michael Beck committed
119
120
121
122
123
/**
 * Place operands of node into an address mode.
 *
 * @param addr    the address mode data so far
 * @param node    the node
124
 * @param flags   the flags
Michael Beck's avatar
Michael Beck committed
125
126
127
 *
 * @return the folded node
 */
128
static ir_node *eat_immediates(x86_address_t *addr, ir_node *node,
129
130
                               x86_create_am_flags_t flags,
                               bool basereg_usable)
131
{
132
133
134
	if (!(flags & x86_create_am_force)
	    && x86_is_non_address_mode_node(node)
	    && (!(flags & x86_create_am_double_use) || get_irn_n_edges(node) > 2))
135
136
		return node;

Christoph Mallon's avatar
Christoph Mallon committed
137
	if (is_Add(node)) {
138
139
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
140
141
142
143
144
145
		if (eat_immediate(addr, left, basereg_usable))
			return eat_immediates(addr, right, x86_create_am_normal,
			                      basereg_usable);
		if (eat_immediate(addr, right, basereg_usable))
			return eat_immediates(addr, left, x86_create_am_normal,
			                      basereg_usable);
146
	} else if (is_Member(node)) {
147
148
		assert(addr->imm.entity == NULL);
		addr->imm.entity = get_Member_entity(node);
149
		addr->imm.kind   = X86_IMM_FRAMEENT;
150
		ir_node *ptr = get_Member_ptr(node);
151
		assert(is_Start(get_Proj_pred(ptr)));
152
		return ptr;
153
154
155
156
157
	}

	return node;
}

Michael Beck's avatar
Michael Beck committed
158
159
160
161
162
/**
 * Try to place a Shl into an address mode.
 *
 * @param addr    the address mode data so far
 * @param node   the node to place
163
 * @return true on success
Michael Beck's avatar
Michael Beck committed
164
 */
165
static bool eat_shl(x86_address_t *addr, ir_node *node)
166
{
Matthias Braun's avatar
Matthias Braun committed
167
168
169
170
	/* we can only eat a shl if we don't have a scale or index set yet */
	if (addr->scale != 0 || addr->index != NULL)
		return false;

171
	ir_node *shifted_val;
172
	long     val;
Christoph Mallon's avatar
Christoph Mallon committed
173
	if (is_Shl(node)) {
Matthias Braun's avatar
Matthias Braun committed
174
		/* we can use shl with 0,1,2 or 3 shift */
175
		ir_node *right = get_Shl_right(node);
Christoph Mallon's avatar
Christoph Mallon committed
176
		if (!is_Const(right))
177
178
			return false;
		ir_tarval *tv = get_Const_tarval(right);
Christoph Mallon's avatar
Christoph Mallon committed
179
		if (!tarval_is_long(tv))
180
			return false;
181
182

		val = get_tarval_long(tv);
Christoph Mallon's avatar
Christoph Mallon committed
183
		if (val < 0 || val > 3)
184
185
			return false;
		if (val == 0)
186
			be_warningf(node, "found unoptimized Shl x,0");
187
188

		shifted_val = get_Shl_left(node);
Christoph Mallon's avatar
Christoph Mallon committed
189
	} else if (is_Add(node)) {
190
191
192
		/* might be an add x, x */
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
Christoph Mallon's avatar
Christoph Mallon committed
193
		if (left != right)
194
			return false;
Christoph Mallon's avatar
Christoph Mallon committed
195
		if (is_Const(left))
196
			return false;
197
198
199
200

		val         = 1;
		shifted_val = left;
	} else {
201
		return false;
202
	}
203

204
	if (x86_is_non_address_mode_node(node))
205
		return false;
206
207

	addr->scale = val;
208
	addr->index = shifted_val;
209
	return true;
210
211
}

212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
static void add_addr_operand(x86_address_t *const addr, ir_node *const op)
{
	if (!op)
		return;
	ir_node *const base = addr->base;
	if (base) {
		addr->variant = X86_ADDR_BASE_INDEX;
		assert(!addr->index && addr->scale == 0);
		/* esp must be used as base */
		if (is_Proj(op) && is_Start(get_Proj_pred(op))) {
			addr->base  = op;
			addr->index = base;
		} else {
			addr->index = op;
		}
	} else {
		addr->variant = addr->index ? X86_ADDR_BASE_INDEX : X86_ADDR_BASE;
		addr->base    = op;
	}
}

233
234
void x86_create_address_mode(x86_address_t *addr, ir_node *node,
                             x86_create_am_flags_t flags)
235
{
236
	addr->imm.kind = X86_IMM_VALUE;
237
238
	if (eat_immediate(addr, node, true)) {
		addr->variant = addr->ip_base ? X86_ADDR_RIP : X86_ADDR_JUST_IMM;
239
		return;
240
	}
241

242
	assert(!addr->ip_base);
243
	if (!(flags & x86_create_am_force) && x86_is_non_address_mode_node(node)
244
	    && (!(flags & x86_create_am_double_use) || get_irn_n_edges(node) > 2)) {
245
		addr->variant = X86_ADDR_BASE;
246
		addr->base    = node;
247
248
249
		return;
	}

250
	ir_node *eat_imms = eat_immediates(addr, node, flags, false);
Christoph Mallon's avatar
Christoph Mallon committed
251
	if (eat_imms != node) {
252
		if (flags & x86_create_am_force)
253
			eat_imms = be_skip_downconv(eat_imms, true);
254

255
		node = eat_imms;
256
		if (x86_is_non_address_mode_node(node)) {
257
258
			addr->variant = X86_ADDR_BASE;
			addr->base    = node;
259
260
			return;
		}
261
262
263
	}

	/* starting point Add, Sub or Shl, FrameAddr */
Christoph Mallon's avatar
Christoph Mallon committed
264
	if (is_Shl(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
265
266
		/* We don't want to eat add x, x as shl here, so only test for real Shl
		 * instructions, because we want the former as Lea x, x, not Shl x, 1 */
267
268
		if (eat_shl(addr, node)) {
			addr->variant = X86_ADDR_INDEX;
269
			return;
270
		}
271
	} else if (eat_immediate(addr, node, true)) {
Matthias Braun's avatar
Matthias Braun committed
272
		/* we can hit this case in x86_create_am_force mode */
273
		addr->variant = addr->ip_base ? X86_ADDR_RIP : X86_ADDR_JUST_IMM;
274
		return;
Christoph Mallon's avatar
Christoph Mallon committed
275
	} else if (is_Add(node)) {
276
277
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
278

279
		if (flags & x86_create_am_force) {
280
281
			left  = be_skip_downconv(left, true);
			right = be_skip_downconv(right, true);
282
		}
283
284
		left  = eat_immediates(addr, left, flags, false);
		right = eat_immediates(addr, right, flags, false);
285

Christoph Mallon's avatar
Christoph Mallon committed
286
		if (eat_shl(addr, left)) {
287
			left = NULL;
Christoph Mallon's avatar
Christoph Mallon committed
288
		} else if (eat_shl(addr, right)) {
289
290
291
			right = NULL;
		}

292
293
		/* (x & 0xFFFFFFFC) + (x >> 2) -> lea(x >> 2, x >> 2, 4) */
		if (left != NULL && right != NULL) {
294
295
			ir_node *and;
			ir_node *shr;
296
297
298
			if (is_And(left) && (is_Shr(right) || is_Shrs(right))) {
				and = left;
				shr = right;
299
300
301
				goto tryit;
			}
			if (is_And(right) && (is_Shr(left) || is_Shrs(left))) {
302
303
				and = right;
				shr = left;
304
305
306
307
308
309
310
311
312
313
314
315
316
317
tryit:
				if (get_And_left(and) == get_binop_left(shr)) {
					ir_node *and_right = get_And_right(and);
					ir_node *shr_right = get_binop_right(shr);

					if (is_Const(and_right) && is_Const(shr_right)) {
						ir_tarval *and_mask     = get_Const_tarval(and_right);
						ir_tarval *shift_amount = get_Const_tarval(shr_right);
						ir_mode   *mode         = get_irn_mode(and);
						ir_tarval *all_one      = get_mode_all_one(mode);
						ir_tarval *shift_mask   = tarval_shl(tarval_shr(all_one, shift_amount), shift_amount);
						long       val          = get_tarval_long(shift_amount);

						if (and_mask == shift_mask && val >= 0 && val <= 3) {
318
319
320
321
							addr->variant = X86_ADDR_BASE_INDEX;
							addr->base    = shr;
							addr->index   = shr;
							addr->scale   = val;
322
323
							return;
						}
324
325
326
327
328
					}
				}
			}
		}

329
330
		add_addr_operand(addr, left);
		add_addr_operand(addr, right);
331
332
333
		return;
	}

334
335
	addr->variant = X86_ADDR_BASE;
	addr->base    = node;
336
337
}

338
void x86_mark_non_am(ir_node *node)
339
340
341
{
	bitset_set(non_address_mode_nodes, get_irn_idx(node));
}
342

343
bool x86_is_non_address_mode_node(ir_node const *node)
344
345
346
347
{
	return bitset_is_set(non_address_mode_nodes, get_irn_idx(node));
}

348
/**
349
350
 * Check if a given value is last used (i.e. die after) the block of some
 * other node.
351
 */
Matthias Braun's avatar
Matthias Braun committed
352
static bool value_last_used_here(be_lv_t *lv, ir_node *here, ir_node *value)
353
{
354
	ir_node *block = get_nodes_block(here);
355
356

	/* If the value is live end it is for sure it does not die here */
Matthias Braun's avatar
Matthias Braun committed
357
358
	if (be_is_live_end(lv, block, value))
		return false;
359
360
361
362
363
364
365

	/* if multiple nodes in this block use the value, then we cannot decide
	 * whether the value will die here (because there is no schedule yet).
	 * Assume it does not die in this case. */
	foreach_out_edge(value, edge) {
		ir_node *user = get_edge_src_irn(edge);
		if (user != here && get_nodes_block(user) == block) {
Matthias Braun's avatar
Matthias Braun committed
366
			return false;
367
368
369
		}
	}

Matthias Braun's avatar
Matthias Braun committed
370
	return true;
371
372
}

Michael Beck's avatar
Michael Beck committed
373
374
/**
 * Walker: mark those nodes that cannot be part of an address mode because
Christoph Mallon's avatar
Christoph Mallon committed
375
 * their value must be accessed through a register
Michael Beck's avatar
Michael Beck committed
376
 */
377
static void mark_non_address_nodes(ir_node *node, void *env)
378
{
379
	be_lv_t *lv = (be_lv_t*)env;
Matthias Braun's avatar
Matthias Braun committed
380
381

	ir_mode *mode = get_irn_mode(node);
Christoph Mallon's avatar
Christoph Mallon committed
382
	if (!mode_is_int(mode) && !mode_is_reference(mode) && mode != mode_b)
383
384
		return;

Christoph Mallon's avatar
Christoph Mallon committed
385
	switch (get_irn_opcode(node)) {
386
	case iro_Load:
387
388
		/* Nothing to do. especially do not mark the pointer, because we want to
		 * turn it into AM. */
389
390
		break;

Matthias Braun's avatar
Matthias Braun committed
391
	case iro_Store: {
392
		/* Do not mark the pointer, because we want to turn it into AM. */
Matthias Braun's avatar
Matthias Braun committed
393
		ir_node *val = get_Store_value(node);
394
		x86_mark_non_am(val);
395
		break;
Matthias Braun's avatar
Matthias Braun committed
396
	}
397

398
	case iro_Shl:
Matthias Braun's avatar
Matthias Braun committed
399
	case iro_Add: {
400
		/* only 1 user: AM folding is always beneficial */
Christoph Mallon's avatar
Christoph Mallon committed
401
		if (get_irn_n_edges(node) <= 1)
402
403
404
405
406
407
408
409
			break;

		/* for adds and shls with multiple users we use this heuristic:
		 * we do not fold them into address mode if their operands don't live
		 * out of the block, because in this case we will reduce register
		 * pressure. Otherwise we fold them in aggressively in the hope, that
		 * the node itself doesn't exist anymore and we were able to save the
		 * register for the result */
Matthias Braun's avatar
Matthias Braun committed
410
411
		ir_node *left  = get_binop_left(node);
		ir_node *right = get_binop_right(node);
412

413
414
		/* if any of the operands is an immediate then this will not
		 * increase register pressure */
415
416
		x86_address_t addr;
		memset(&addr, 0, sizeof(addr));
417
418
		if (eat_immediate(&addr, left, false)
		 || eat_immediate(&addr, right, false))
419
420
421
			return;

		/* Fold AM if any of the two operands does not die here. This duplicates
422
423
424
		 * an addition and has the same register pressure for the case that only
		 * one operand dies, but is faster (on Pentium 4).
		 * && instead of || only folds AM if both operands do not die here */
Matthias Braun's avatar
Matthias Braun committed
425
426
		if (!value_last_used_here(lv, node, left)
		 || !value_last_used_here(lv, node, right)) {
427
			return;
428
		}
429

430
431
432
		/* At least one of left and right are not used by anyone else, so it is
		 * beneficial for the register pressure (if both are unused otherwise,
		 * else neutral) and ALU use to not fold AM. */
433
		x86_mark_non_am(node);
434
		break;
Matthias Braun's avatar
Matthias Braun committed
435
	}
436
437

	default:
438
		foreach_irn_in(node, i, in) {
439
			x86_mark_non_am(in);
440
		}
441
		break;
442
443
	}
}
444

445
void x86_calculate_non_address_mode_nodes(ir_graph *irg)
446
{
447
	be_assure_live_chk(irg);
Matthias Braun's avatar
Matthias Braun committed
448
	be_lv_t *lv = be_get_irg_liveness(irg);
449

450
451
	non_address_mode_nodes = bitset_malloc(get_irg_last_idx(irg));

452
	irg_walk_graph(irg, NULL, mark_non_address_nodes, lv);
453
454
}

455
void x86_free_non_address_mode_nodes(void)
456
{
457
	free(non_address_mode_nodes);
458
}
Christoph Mallon's avatar
Christoph Mallon committed
459
460
461
462

char const *x86_get_addr_variant_str(x86_addr_variant_t const variant)
{
	switch (variant) {
463
	case X86_ADDR_REG:        return "reg";
Christoph Mallon's avatar
Christoph Mallon committed
464
465
466
467
468
	case X86_ADDR_JUST_IMM:   return "immediate";
	case X86_ADDR_BASE:       return "base";
	case X86_ADDR_BASE_INDEX: return "base+index";
	case X86_ADDR_INDEX:      return "index";
	case X86_ADDR_RIP:        return "rip";
469
470
	case X86_ADDR_INVALID:
		break;
Christoph Mallon's avatar
Christoph Mallon committed
471
472
473
	}
	return "<BAD>";
}
474
475
476
477
478

static void emit_register(arch_register_t const *const reg)
{
	be_emit_char('%');
	be_emit_string(reg->name);
Christoph Mallon's avatar
Christoph Mallon committed
479
	assert(!reg->is_virtual);
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
}

void x86_emit_addr(ir_node const *const node, x86_addr_t const *const addr)
{
	switch (addr->segment) {
	case X86_SEGMENT_DEFAULT:
		break;
	case X86_SEGMENT_CS: be_emit_cstring("%cs:"); break;
	case X86_SEGMENT_SS: be_emit_cstring("%ss:"); break;
	case X86_SEGMENT_DS: be_emit_cstring("%ds:"); break;
	case X86_SEGMENT_ES: be_emit_cstring("%es:"); break;
	case X86_SEGMENT_FS: be_emit_cstring("%fs:"); break;
	case X86_SEGMENT_GS: be_emit_cstring("%gs:"); break;
	}


	/* emit offset */
	x86_addr_variant_t const variant = addr->variant;
	int32_t            const offset  = addr->immediate.offset;
	ir_entity   const *const entity  = addr->immediate.entity;
	assert(variant != X86_ADDR_INVALID);
	if (entity) {
		x86_emit_relocation_no_offset(addr->immediate.kind, entity);
		if (offset != 0)
			be_emit_irprintf("%+"PRId32, offset);
	} else if (offset != 0 || variant == X86_ADDR_JUST_IMM) {
		assert(addr->immediate.kind == X86_IMM_VALUE);
		/* also handle special case if nothing is set */
		be_emit_irprintf("%"PRId32, offset);
	}

	if (variant != X86_ADDR_JUST_IMM) {
		be_emit_char('(');

		if (variant == X86_ADDR_RIP) {
			be_emit_cstring("%rip");
		} else {
			if (x86_addr_variant_has_base(variant)) {
				arch_register_t const *const reg
					= arch_get_irn_register_in(node, addr->base_input);
				emit_register(reg);
			}

			if (x86_addr_variant_has_index(variant)) {
				be_emit_char(',');
				arch_register_t const *const reg
					= arch_get_irn_register_in(node, addr->index_input);
				emit_register(reg);

				unsigned const log_scale = addr->log_scale;
				if (log_scale > 0)
					be_emit_irprintf(",%u", 1u << log_scale);
			}
		}
		be_emit_char(')');
	}
}