betranshlp.c 13.9 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       be transform helper extracted from the ia32 backend.
Michael Beck's avatar
Michael Beck committed
9
 * @author      Matthias Braun, Michael Beck
10
11
12
13
14
15
16
 * @date        14.06.2007
 */
#include "pdeq.h"
#include "irop_t.h"
#include "iropt_t.h"
#include "irnode_t.h"
#include "irgraph_t.h"
17
#include "ircons_t.h"
18
19
20
21
22
23
#include "irhooks.h"
#include "iredges.h"
#include "irouts.h"
#include "trouts.h"
#include "cgana.h"
#include "debug.h"
24
#include "execfreq_t.h"
25

26
#include "beirg.h"
27
#include "beabi.h"
28
#include "betranshlp.h"
29
#include "belive.h"
30
#include "benode.h"
31
32
33
34
35

typedef struct be_transform_env_t {
	ir_graph *irg;         /**< The irg, the node should be created in */
	waitq    *worklist;    /**< worklist of nodes that still need to be
	                            transformed */
36
	ir_node  *old_anchor;  /**< the old anchor node in the old irg */
37
38
39
40
41
} be_transform_env_t;


static be_transform_env_t env;

42
43
void be_set_transformed_node(ir_node *old_node, ir_node *new_node)
{
44
	set_irn_link(old_node, new_node);
45
	mark_irn_visited(old_node);
46
47
}

48
49
int be_is_transformed(const ir_node *node)
{
50
51
52
	return irn_visited(node);
}

53
54
static inline ir_node *be_get_transformed_node(ir_node *old_node)
{
55
	if (irn_visited(old_node)) {
56
		ir_node *new_node = (ir_node*)get_irn_link(old_node);
57
58
59
60
		assert(new_node != NULL);
		return new_node;
	}
	return NULL;
61
62
}

63
64
void be_duplicate_deps(ir_node *old_node, ir_node *new_node)
{
65
	int deps = get_irn_deps(old_node);
Matthias Braun's avatar
Matthias Braun committed
66
	for (int i = 0; i < deps; ++i) {
67
68
69
70
71
72
73
		ir_node *dep     = get_irn_dep(old_node, i);
		ir_node *new_dep = be_transform_node(dep);

		add_irn_dep(new_node, new_dep);
	}
}

74
75
76
ir_node *be_transform_phi(ir_node *node, const arch_register_req_t *req)
{
	ir_node  *block = be_transform_node(get_nodes_block(node));
77
	ir_graph *irg   = get_Block_irg(block);
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
	dbg_info *dbgi  = get_irn_dbg_info(node);

	/* phi nodes allow loops, so we use the old arguments for now
	 * and fix this later */
	ir_node **ins   = get_irn_in(node)+1;
	int       arity = get_irn_arity(node);
	ir_mode  *mode  = req->cls != NULL ? req->cls->mode : get_irn_mode(node);
	ir_node  *phi   = new_ir_node(dbgi, irg, block, op_Phi, mode, arity, ins);
	copy_node_attr(irg, node, phi);
	be_duplicate_deps(node, phi);

	backend_info_t *info = be_get_info(phi);
	struct obstack *obst = be_get_be_obst(irg);
	info->in_reqs = OALLOCN(obst, const arch_register_req_t*, arity);
	for (int i = 0; i < arity; ++i) {
		info->in_reqs[i] = req;
	}

	arch_set_irn_register_req_out(phi, 0, req);
	be_enqueue_preds(node);

	return phi;
}

102
103
104
105
106
107
108
109
110
void be_set_transform_function(ir_op *op, be_transform_func func)
{
	/* shouldn't be assigned twice (except for exchanging the default
	 * be_duplicate_node entries) */
	assert(op->ops.generic == NULL
			|| op->ops.generic == (op_func) be_duplicate_node);
	op->ops.generic = (op_func) func;
}

111
112
113
114
115
/**
 * Transform helper for blocks.
 */
static ir_node *transform_block(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
116
117
118
119
120
	ir_graph *irg   = get_irn_irg(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_mode  *mode  = get_irn_mode(node);
	ir_node  *block = new_ir_node(dbgi, irg, NULL, get_irn_op(node), mode,
	                              get_irn_arity(node), get_irn_in(node) + 1);
121
122
123
	copy_node_attr(irg, node, block);
	block->node_nr = node->node_nr;

124
125
126
127
	/* transfer execfreq value */
	double execfreq = get_block_execfreq(node);
	set_block_execfreq(block, execfreq);

128
129
130
131
132
133
134
135
136
	/* put the preds in the worklist */
	be_enqueue_preds(node);

	return block;
}

static ir_node *transform_end(ir_node *node)
{
	/* end has to be duplicated manually because we need a dynamic in array */
Matthias Braun's avatar
Matthias Braun committed
137
138
139
140
	ir_graph *irg     = get_irn_irg(node);
	dbg_info *dbgi    = get_irn_dbg_info(node);
	ir_node  *block   = be_transform_node(get_nodes_block(node));
	ir_node  *new_end = new_ir_node(dbgi, irg, block, op_End, mode_X, -1, NULL);
141
142
143
144
145
146
147
	copy_node_attr(irg, node, new_end);
	be_duplicate_deps(node, new_end);

	set_irg_end(irg, new_end);

	/* do not transform predecessors yet to keep the pre-transform
	 * phase from visiting all the graph */
Matthias Braun's avatar
Matthias Braun committed
148
149
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
150
151
152
153
154
155
156
157
		ir_node *in = get_irn_n(node, i);
		add_End_keepalive(new_end, in);
	}
	be_enqueue_preds(node);

	return new_end;
}

158
159
ir_node *be_duplicate_node(ir_node *node)
{
160
161
162
163
164
165
	ir_node  *block = be_transform_node(get_nodes_block(node));
	ir_graph *irg   = env.irg;
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_mode  *mode  = get_irn_mode(node);
	ir_op    *op    = get_irn_op(node);

Matthias Braun's avatar
Matthias Braun committed
166
167
	ir_node *new_node;
	int      arity = get_irn_arity(node);
168
169
	if (op->opar == oparity_dynamic) {
		new_node = new_ir_node(dbgi, irg, block, op, mode, -1, NULL);
Matthias Braun's avatar
Matthias Braun committed
170
		for (int i = 0; i < arity; ++i) {
171
172
173
174
175
			ir_node *in = get_irn_n(node, i);
			in = be_transform_node(in);
			add_irn_n(new_node, in);
		}
	} else {
176
		ir_node **ins = ALLOCAN(ir_node*, arity);
Matthias Braun's avatar
Matthias Braun committed
177
		for (int i = 0; i < arity; ++i) {
178
179
180
181
182
183
184
			ir_node *in = get_irn_n(node, i);
			ins[i] = be_transform_node(in);
		}

		new_node = new_ir_node(dbgi, irg, block, op, mode, arity, ins);
	}

185
	copy_node_attr(irg, node, new_node);
186
187
188
189
190
191
	be_duplicate_deps(node, new_node);

	new_node->node_nr = node->node_nr;
	return new_node;
}

192
193
ir_node *be_transform_node(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
194
	ir_node *new_node = be_get_transformed_node(node);
195
	if (new_node != NULL)
196
197
		return new_node;

198
	DEBUG_ONLY(be_set_transformed_node(node, NULL);)
199

Matthias Braun's avatar
Matthias Braun committed
200
201
	ir_op *op = get_irn_op(node);
	be_transform_func *transform = (be_transform_func *)op->ops.generic;
202
203
204

	new_node = transform(node);
	assert(new_node != NULL);
205
206
207
208
209

	be_set_transformed_node(node, new_node);
	return new_node;
}

210
211
void be_enqueue_preds(ir_node *node)
{
212
	/* put the preds in the worklist */
Matthias Braun's avatar
Matthias Braun committed
213
214
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
215
216
217
218
219
220
221
222
		ir_node *pred = get_irn_n(node, i);
		pdeq_putr(env.worklist, pred);
	}
}

/**
 * Rewire nodes which are potential loops (like Phis) to avoid endless loops.
 */
223
224
static void fix_loops(ir_node *node)
{
225
	if (irn_visited_else_mark(node))
226
227
		return;

228
229
	assert(node_is_in_irgs_storage(env.irg, node));

Matthias Braun's avatar
Matthias Braun committed
230
	bool changed = false;
231
232
	if (! is_Block(node)) {
		ir_node *block     = get_nodes_block(node);
233
		ir_node *new_block = (ir_node*)get_irn_link(block);
234
235
236
237

		if (new_block != NULL) {
			set_nodes_block(node, new_block);
			block = new_block;
Matthias Braun's avatar
Matthias Braun committed
238
			changed = true;
239
240
241
242
243
		}

		fix_loops(block);
	}

Matthias Braun's avatar
Matthias Braun committed
244
245
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
246
		ir_node *in = get_irn_n(node, i);
247
		ir_node *nw = (ir_node*)get_irn_link(in);
248
249
250
251

		if (nw != NULL && nw != in) {
			set_irn_n(node, i, nw);
			in = nw;
Matthias Braun's avatar
Matthias Braun committed
252
			changed = true;
253
254
255
256
		}

		fix_loops(in);
	}
257
	/* fix proj block */
258
	if (is_Proj(node)) {
259
		set_nodes_block(node, get_nodes_block(get_Proj_pred(node)));
Matthias Braun's avatar
Matthias Braun committed
260
		changed = true;
261
	}
262
263

	arity = get_irn_deps(node);
Matthias Braun's avatar
Matthias Braun committed
264
	for (int i = 0; i < arity; ++i) {
265
		ir_node *in = get_irn_dep(node, i);
266
		ir_node *nw = (ir_node*)get_irn_link(in);
267
268
269
270

		if (nw != NULL && nw != in) {
			set_irn_dep(node, i, nw);
			in = nw;
Matthias Braun's avatar
Matthias Braun committed
271
			changed = true;
272
273
274
275
		}

		fix_loops(in);
	}
276

277
	if (changed) {
278
		identify_remember(node);
279
	}
280
281
}

282
283
ir_node *be_pre_transform_node(ir_node *place)
{
284
285
286
287
288
289
	if (place == NULL)
		return NULL;

	return be_transform_node(place);
}

290
static void pre_transform_anchor(ir_graph *irg, int anchor)
291
292
293
{
	ir_node *old_anchor_node = get_irn_n(env.old_anchor, anchor);
	ir_node *transformed     = be_transform_node(old_anchor_node);
294
	set_irg_anchor(irg, anchor, transformed);
295
296
}

297
298
299
/**
 * Transforms all nodes. Deletes the old obstack and creates a new one.
 */
300
static void transform_nodes(ir_graph *irg, arch_pretrans_nodes *pre_transform)
301
{
302
303
304
305
	hook_dead_node_elim(irg, 1);

	inc_irg_visited(irg);

306
307
308
	env.irg        = irg;
	env.worklist   = new_waitq();
	env.old_anchor = irg->anchor;
309

Matthias Braun's avatar
Matthias Braun committed
310
	ir_node *old_end = get_irg_end(irg);
311
312

	/* put all anchor nodes in the worklist */
Matthias Braun's avatar
Matthias Braun committed
313
	for (int i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
314
		ir_node *anchor = get_irg_anchor(irg, i);
315
316
317
318
319
320

		if (anchor == NULL)
			continue;
		waitq_put(env.worklist, anchor);
	}

Matthias Braun's avatar
Matthias Braun committed
321
	ir_node *new_anchor  = new_r_Anchor(irg);
322
	irg->anchor = new_anchor;
323

324
325
	/* pre transform some anchors (so they are available in the other transform
	 * functions) */
326
327
328
329
330
331
	pre_transform_anchor(irg, anchor_no_mem);
	pre_transform_anchor(irg, anchor_end_block);
	pre_transform_anchor(irg, anchor_end);
	pre_transform_anchor(irg, anchor_start_block);
	pre_transform_anchor(irg, anchor_start);
	pre_transform_anchor(irg, anchor_frame);
332
333

	if (pre_transform)
334
		pre_transform();
335
336
337

	/* process worklist (this should transform all nodes in the graph) */
	while (! waitq_empty(env.worklist)) {
338
		ir_node *node = (ir_node*)waitq_get(env.worklist);
339
340
341
342
343
		be_transform_node(node);
	}

	/* fix loops and set new anchors*/
	inc_irg_visited(irg);
Matthias Braun's avatar
Matthias Braun committed
344
	for (int i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
345
		ir_node *anchor = get_irn_n(env.old_anchor, i);
346
347
348
349

		if (anchor == NULL)
			continue;

350
		anchor = (ir_node*)get_irn_link(anchor);
351
		fix_loops(anchor);
352
		set_irn_n(new_anchor, i, anchor);
353
354
355
356
357
358
359
	}

	del_waitq(env.worklist);
	free_End(old_end);
	hook_dead_node_elim(irg, 0);
}

360
void be_transform_graph(ir_graph *irg, arch_pretrans_nodes *func)
361
362
363
364
365
{
	ir_graph *old_current_ir_graph = current_ir_graph;
	current_ir_graph = irg;

	/* create a new obstack */
366
367
	struct obstack old_obst = irg->obst;
	obstack_init(&irg->obst);
368
369
	irg->last_node_idx = 0;

370
	free_vrp_data(irg);
371

372
	/* create new value table for CSE */
373
	new_identities(irg);
374
375

	/* do the main transformation */
376
	transform_nodes(irg, func);
377
378

	/* free the old obstack */
379
	obstack_free(&old_obst, 0);
380
381
382
383

	/* restore state */
	current_ir_graph = old_current_ir_graph;

384
	/* most analysis info is wrong after transformation */
385
	be_invalidate_live_chk(irg);
Matthias Braun's avatar
Matthias Braun committed
386
	confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
387

388
389
390
	/* recalculate edges */
	edges_activate(irg);
}
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
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

bool be_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	ir_op *op = get_irn_op(node);
	if (op->ops.generic1 == NULL)
		return false;
	upper_bits_clean_func func = (upper_bits_clean_func)op->ops.generic1;
	return func(node, mode);
}

static bool bit_binop_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	return be_upper_bits_clean(get_binop_left(node), mode)
	    && be_upper_bits_clean(get_binop_right(node), mode);
}

static bool mux_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	return be_upper_bits_clean(get_Mux_true(node), mode)
	    && be_upper_bits_clean(get_Mux_false(node), mode);
}

static bool and_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	if (!mode_is_signed(mode)) {
		return be_upper_bits_clean(get_And_left(node), mode)
		    || be_upper_bits_clean(get_And_right(node), mode);
	} else {
		return bit_binop_upper_bits_clean(node, mode);
	}
}

static bool shr_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	if (mode_is_signed(mode)) {
		return false;
	} else {
		const ir_node *right = get_Shr_right(node);
		if (is_Const(right)) {
			ir_tarval *tv  = get_Const_tarval(right);
			long       val = get_tarval_long(tv);
			if (val >= 32 - (long)get_mode_size_bits(mode))
				return true;
		}
		return be_upper_bits_clean(get_Shr_left(node), mode);
	}
}

static bool shrs_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	return be_upper_bits_clean(get_Shrs_left(node), mode);
}

static bool const_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	ir_tarval *tv  = get_Const_tarval(node);
	long       val = get_tarval_long(tv);
	if (mode_is_signed(mode)) {
		long    shifted = val >> (get_mode_size_bits(mode)-1);
		return shifted == 0 || shifted == -1;
	} else {
		unsigned long shifted = (unsigned long)val;
		shifted >>= get_mode_size_bits(mode)-1;
		shifted >>= 1;
		return shifted == 0;
	}
}

static bool conv_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	ir_mode       *dest_mode = get_irn_mode(node);
	const ir_node *op        = get_Conv_op(node);
	ir_mode       *src_mode  = get_irn_mode(op);
	if (mode_is_float(src_mode))
		return true;

	unsigned src_bits  = get_mode_size_bits(src_mode);
	unsigned dest_bits = get_mode_size_bits(dest_mode);
	/* downconvs are a nop */
	if (src_bits >= dest_bits)
		return be_upper_bits_clean(op, mode);
	/* upconvs are fine if src is big enough or if sign matches */
	if (src_bits <= get_mode_size_bits(mode)
		&& mode_is_signed(src_mode) == mode_is_signed(mode))
		return true;
	return false;
}

static bool proj_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	const ir_node *pred = get_Proj_pred(node);
	switch (get_irn_opcode(pred)) {
	case iro_Load: {
		ir_mode *load_mode = get_Load_mode(pred);
		unsigned load_bits = get_mode_size_bits(load_mode);
		if (load_bits > get_mode_size_bits(mode))
			return false;
		if (mode_is_signed(load_mode) != mode_is_signed(mode))
			return false;
		return true;
	}
	default:
		break;
	}
	return false;
}

void be_set_upper_bits_clean_function(ir_op *op, upper_bits_clean_func func)
{
	op->ops.generic1 = (op_func)func;
}

void be_start_transform_setup(void)
{
	ir_clear_opcodes_generic_func();

	be_set_transform_function(op_Bad,         be_duplicate_node);
	be_set_transform_function(op_be_CopyKeep, be_duplicate_node);
	be_set_transform_function(op_be_IncSP,    be_duplicate_node);
	be_set_transform_function(op_be_Keep,     be_duplicate_node);
	be_set_transform_function(op_be_Return,   be_duplicate_node);
	be_set_transform_function(op_be_Start,    be_duplicate_node);
	be_set_transform_function(op_Block,       transform_block);
	be_set_transform_function(op_End,         transform_end);
	be_set_transform_function(op_NoMem,       be_duplicate_node);
	be_set_transform_function(op_Pin,         be_duplicate_node);
	be_set_transform_function(op_Start,       be_duplicate_node);
	be_set_transform_function(op_Sync,        be_duplicate_node);

	be_set_upper_bits_clean_function(op_And,   and_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Const, const_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Conv,  conv_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Eor,   bit_binop_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Mux,   mux_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Or,    bit_binop_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Proj,  proj_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Shr,   shr_upper_bits_clean);
	be_set_upper_bits_clean_function(op_Shrs,  shrs_upper_bits_clean);
}