x86_address_mode.c 12.6 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
#include "bediagnostic.h"
15
#include "beirg.h"
Matthias Braun's avatar
Matthias Braun committed
16
17
#include "belive.h"
#include "benode.h"
18
#include "betranshlp.h"
Matthias Braun's avatar
Matthias Braun committed
19
#include "beutil.h"
20
#include "iredges_t.h"
21
#include "irgwalk.h"
Matthias Braun's avatar
Matthias Braun committed
22
23
#include "irnode_t.h"
#include "irprintf.h"
24

25
26
static bitset_t *non_address_mode_nodes;

Matthias Braun's avatar
Matthias Braun committed
27
28
static bool tarval_possible(ir_tarval *tv)
{
29
30
31
32
33
34
	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
35
36
	if (!tarval_is_long(tv))
		return false;
37
	/* immediates on x86_64 are at most 32bit and get sign extended */
Matthias Braun's avatar
Matthias Braun committed
38
39
40
41
42
	long    val   = get_tarval_long(tv);
	int32_t val32 = (long)val;
	return val == (long)val32;
}

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

54
	case iro_Address:
55
		/* The first Address of a DAG can be folded into an immediate. */
56
		if (addr->imm.entity)
57
			return false;
58
		addr->imm.entity = get_Address_entity(node);
59
		addr->imm.kind = X86_IMM_ADDR;
60
		if (is_tls_entity(addr->imm.entity))
61
62
63
64
65
66
67
			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))
68
			return false;
69
		addr->imm.offset += get_tarval_long(tv);
70
		return true;
71
	}
72

73
	case iro_Unknown:
74
		/* Use '0' for Unknowns. */
75
		return true;
76
77

	default:
Matthias Braun's avatar
Matthias Braun committed
78
79
80
81
		if (be_is_Relocation(node)) {
			if (addr->imm.entity)
				return false;
			addr->imm.entity = be_get_Relocation_entity(node);
82
83
84
85
86
87
88
89
			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
90
91
			return true;
		}
92
		/* All other nodes are no immediates. */
93
		return false;
94
95
96
	}
}

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

Michael Beck's avatar
Michael Beck committed
116
117
118
119
120
/**
 * Place operands of node into an address mode.
 *
 * @param addr    the address mode data so far
 * @param node    the node
121
 * @param flags   the flags
Michael Beck's avatar
Michael Beck committed
122
123
124
 *
 * @return the folded node
 */
125
static ir_node *eat_immediates(x86_address_t *addr, ir_node *node,
126
127
                               x86_create_am_flags_t flags,
                               bool basereg_usable)
128
{
129
130
131
	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))
132
133
		return node;

Christoph Mallon's avatar
Christoph Mallon committed
134
	if (is_Add(node)) {
135
136
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
137
138
139
140
141
142
		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);
143
	} else if (is_Member(node)) {
144
145
146
		assert(addr->imm.entity == NULL);
		addr->imm.entity = get_Member_entity(node);
		addr->imm.kind   = X86_IMM_FRAMEOFFSET;
147
		ir_node *ptr = get_Member_ptr(node);
148
		assert(is_Start(get_Proj_pred(ptr)));
149
		return ptr;
150
151
152
153
154
	}

	return node;
}

Michael Beck's avatar
Michael Beck committed
155
156
157
158
159
/**
 * Try to place a Shl into an address mode.
 *
 * @param addr    the address mode data so far
 * @param node   the node to place
160
 * @return true on success
Michael Beck's avatar
Michael Beck committed
161
 */
162
static bool eat_shl(x86_address_t *addr, ir_node *node)
163
{
Matthias Braun's avatar
Matthias Braun committed
164
165
166
167
	/* 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;

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

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

		shifted_val = get_Shl_left(node);
Christoph Mallon's avatar
Christoph Mallon committed
186
	} else if (is_Add(node)) {
187
188
189
		/* 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
190
		if (left != right)
191
			return false;
Christoph Mallon's avatar
Christoph Mallon committed
192
		if (is_Const(left))
193
			return false;
194
195
196
197

		val         = 1;
		shifted_val = left;
	} else {
198
		return false;
199
	}
200

201
	if (x86_is_non_address_mode_node(node))
202
		return false;
203
204

	addr->scale = val;
205
	addr->index = shifted_val;
206
	return true;
207
208
}

209
210
void x86_create_address_mode(x86_address_t *addr, ir_node *node,
                             x86_create_am_flags_t flags)
211
{
212
	addr->imm.kind = X86_IMM_VALUE;
213
214
	if (eat_immediate(addr, node, true)) {
		addr->variant = addr->ip_base ? X86_ADDR_RIP : X86_ADDR_JUST_IMM;
215
		return;
216
	}
217

218
	assert(!addr->ip_base);
219
	if (!(flags & x86_create_am_force) && x86_is_non_address_mode_node(node)
220
	    && (!(flags & x86_create_am_double_use) || get_irn_n_edges(node) > 2)) {
221
222
	    addr->variant = X86_ADDR_BASE;
		addr->base    = node;
223
224
225
		return;
	}

226
	ir_node *eat_imms = eat_immediates(addr, node, flags, false);
Christoph Mallon's avatar
Christoph Mallon committed
227
	if (eat_imms != node) {
228
		if (flags & x86_create_am_force)
229
			eat_imms = be_skip_downconv(eat_imms, true);
230

231
		node = eat_imms;
232
		if (x86_is_non_address_mode_node(node)) {
233
234
			addr->variant = X86_ADDR_BASE;
			addr->base    = node;
235
236
			return;
		}
237
238
239
	}

	/* starting point Add, Sub or Shl, FrameAddr */
Christoph Mallon's avatar
Christoph Mallon committed
240
	if (is_Shl(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
241
242
		/* 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 */
243
244
		if (eat_shl(addr, node)) {
			addr->variant = X86_ADDR_INDEX;
245
			return;
246
		}
247
	} else if (eat_immediate(addr, node, true)) {
Matthias Braun's avatar
Matthias Braun committed
248
		/* we can hit this case in x86_create_am_force mode */
249
		addr->variant = addr->ip_base ? X86_ADDR_RIP : X86_ADDR_JUST_IMM;
250
		return;
Christoph Mallon's avatar
Christoph Mallon committed
251
	} else if (is_Add(node)) {
252
253
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
254

255
		if (flags & x86_create_am_force) {
256
257
			left  = be_skip_downconv(left, true);
			right = be_skip_downconv(right, true);
258
		}
259
260
		left  = eat_immediates(addr, left, flags, false);
		right = eat_immediates(addr, right, flags, false);
261

Christoph Mallon's avatar
Christoph Mallon committed
262
		if (eat_shl(addr, left)) {
263
			left = NULL;
Christoph Mallon's avatar
Christoph Mallon committed
264
		} else if (eat_shl(addr, right)) {
265
266
267
			right = NULL;
		}

268
269
		/* (x & 0xFFFFFFFC) + (x >> 2) -> lea(x >> 2, x >> 2, 4) */
		if (left != NULL && right != NULL) {
270
271
			ir_node *and;
			ir_node *shr;
272
273
274
			if (is_And(left) && (is_Shr(right) || is_Shrs(right))) {
				and = left;
				shr = right;
275
276
277
				goto tryit;
			}
			if (is_And(right) && (is_Shr(left) || is_Shrs(left))) {
278
279
				and = right;
				shr = left;
280
281
282
283
284
285
286
287
288
289
290
291
292
293
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) {
294
295
296
297
							addr->variant = X86_ADDR_BASE_INDEX;
							addr->base    = shr;
							addr->index   = shr;
							addr->scale   = val;
298
299
							return;
						}
300
301
302
303
304
					}
				}
			}
		}

Christoph Mallon's avatar
Christoph Mallon committed
305
		if (left != NULL) {
306
307
			ir_node *base = addr->base;
			if (base == NULL) {
308
309
310
				addr->variant = addr->index != NULL ? X86_ADDR_BASE_INDEX
				                                    : X86_ADDR_BASE;
				addr->base    = left;
311
			} else {
312
				addr->variant = X86_ADDR_BASE_INDEX;
313
314
				assert(addr->index == NULL && addr->scale == 0);
				assert(right == NULL);
315
				/* esp must be used as base */
316
				if (is_Proj(left) && is_Start(get_Proj_pred(left))) {
317
318
319
320
321
					addr->index = base;
					addr->base  = left;
				} else {
					addr->index = left;
				}
322
323
			}
		}
Christoph Mallon's avatar
Christoph Mallon committed
324
		if (right != NULL) {
325
326
			ir_node *base = addr->base;
			if (base == NULL) {
327
328
329
				addr->variant = addr->index != NULL ? X86_ADDR_BASE_INDEX
				                                    : X86_ADDR_BASE;
				addr->base    = right;
330
			} else {
331
				addr->variant = X86_ADDR_BASE_INDEX;
332
				assert(addr->index == NULL && addr->scale == 0);
333
				/* esp must be used as base */
334
				if (is_Proj(right) && is_Start(get_Proj_pred(right))) {
335
336
337
338
339
				    addr->index = base;
				    addr->base  = right;
				} else {
					addr->index = right;
				}
340
341
342
343
344
			}
		}
		return;
	}

345
346
	addr->variant = X86_ADDR_BASE;
	addr->base    = node;
347
348
}

349
void x86_mark_non_am(ir_node *node)
350
351
352
{
	bitset_set(non_address_mode_nodes, get_irn_idx(node));
}
353

354
bool x86_is_non_address_mode_node(ir_node const *node)
355
356
357
358
{
	return bitset_is_set(non_address_mode_nodes, get_irn_idx(node));
}

359
/**
360
361
 * Check if a given value is last used (i.e. die after) the block of some
 * other node.
362
 */
Matthias Braun's avatar
Matthias Braun committed
363
static bool value_last_used_here(be_lv_t *lv, ir_node *here, ir_node *value)
364
{
365
	ir_node *block = get_nodes_block(here);
366
367

	/* If the value is live end it is for sure it does not die here */
Matthias Braun's avatar
Matthias Braun committed
368
369
	if (be_is_live_end(lv, block, value))
		return false;
370
371
372
373
374
375
376

	/* 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
377
			return false;
378
379
380
		}
	}

Matthias Braun's avatar
Matthias Braun committed
381
	return true;
382
383
}

Michael Beck's avatar
Michael Beck committed
384
385
/**
 * Walker: mark those nodes that cannot be part of an address mode because
Christoph Mallon's avatar
Christoph Mallon committed
386
 * their value must be accessed through a register
Michael Beck's avatar
Michael Beck committed
387
 */
388
static void mark_non_address_nodes(ir_node *node, void *env)
389
{
390
	be_lv_t *lv = (be_lv_t*)env;
Matthias Braun's avatar
Matthias Braun committed
391
392

	ir_mode *mode = get_irn_mode(node);
Christoph Mallon's avatar
Christoph Mallon committed
393
	if (!mode_is_int(mode) && !mode_is_reference(mode) && mode != mode_b)
394
395
		return;

Christoph Mallon's avatar
Christoph Mallon committed
396
	switch (get_irn_opcode(node)) {
397
	case iro_Load:
398
399
		/* Nothing to do. especially do not mark the pointer, because we want to
		 * turn it into AM. */
400
401
		break;

Matthias Braun's avatar
Matthias Braun committed
402
	case iro_Store: {
403
		/* Do not mark the pointer, because we want to turn it into AM. */
Matthias Braun's avatar
Matthias Braun committed
404
		ir_node *val = get_Store_value(node);
405
		x86_mark_non_am(val);
406
		break;
Matthias Braun's avatar
Matthias Braun committed
407
	}
408

409
	case iro_Shl:
Matthias Braun's avatar
Matthias Braun committed
410
	case iro_Add: {
411
		/* only 1 user: AM folding is always beneficial */
Christoph Mallon's avatar
Christoph Mallon committed
412
		if (get_irn_n_edges(node) <= 1)
413
414
415
416
417
418
419
420
			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
421
422
		ir_node *left  = get_binop_left(node);
		ir_node *right = get_binop_right(node);
423

424
425
		/* if any of the operands is an immediate then this will not
		 * increase register pressure */
426
427
		x86_address_t addr;
		memset(&addr, 0, sizeof(addr));
428
429
		if (eat_immediate(&addr, left, false)
		 || eat_immediate(&addr, right, false))
430
431
432
			return;

		/* Fold AM if any of the two operands does not die here. This duplicates
433
434
435
		 * 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
436
437
		if (!value_last_used_here(lv, node, left)
		 || !value_last_used_here(lv, node, right)) {
438
			return;
439
		}
440

441
442
443
		/* 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. */
444
		x86_mark_non_am(node);
445
		break;
Matthias Braun's avatar
Matthias Braun committed
446
	}
447
448

	default:
449
		foreach_irn_in(node, i, in) {
450
			x86_mark_non_am(in);
451
		}
452
		break;
453
454
	}
}
455

456
void x86_calculate_non_address_mode_nodes(ir_graph *irg)
457
{
458
	be_assure_live_chk(irg);
Matthias Braun's avatar
Matthias Braun committed
459
	be_lv_t *lv = be_get_irg_liveness(irg);
460

461
462
	non_address_mode_nodes = bitset_malloc(get_irg_last_idx(irg));

463
	irg_walk_graph(irg, NULL, mark_non_address_nodes, lv);
464
465
}

466
void x86_free_non_address_mode_nodes(void)
467
{
468
	free(non_address_mode_nodes);
469
}