betranshlp.c 14.4 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
void be_set_transform_proj_function(ir_op *op, be_transform_func func)
{
	op->ops.generic1 = (op_func) func;
}

116
117
118
119
120
/**
 * Transform helper for blocks.
 */
static ir_node *transform_block(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
121
122
123
124
125
	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);
126
127
128
	copy_node_attr(irg, node, block);
	block->node_nr = node->node_nr;

129
130
131
132
	/* transfer execfreq value */
	double execfreq = get_block_execfreq(node);
	set_block_execfreq(block, execfreq);

133
134
135
136
137
138
139
140
141
	/* 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
142
143
144
145
	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);
146
147
148
149
150
151
152
	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
153
154
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
155
156
157
158
159
160
161
162
		ir_node *in = get_irn_n(node, i);
		add_End_keepalive(new_end, in);
	}
	be_enqueue_preds(node);

	return new_end;
}

163
164
165
166
167
168
169
170
171
172
173
static ir_node *transform_proj(ir_node *node)
{
	ir_node *pred    = get_Proj_pred(node);
	ir_op   *pred_op = get_irn_op(pred);
	be_transform_func *proj_transform
		= (be_transform_func*)pred_op->ops.generic1;
	/* we should have a Proj transformer registered */
	assert(proj_transform != NULL);
	return proj_transform(node);
}

174
175
ir_node *be_duplicate_node(ir_node *node)
{
176
177
178
179
180
181
	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
182
183
	ir_node *new_node;
	int      arity = get_irn_arity(node);
184
185
	if (op->opar == oparity_dynamic) {
		new_node = new_ir_node(dbgi, irg, block, op, mode, -1, NULL);
Matthias Braun's avatar
Matthias Braun committed
186
		for (int i = 0; i < arity; ++i) {
187
188
189
190
191
			ir_node *in = get_irn_n(node, i);
			in = be_transform_node(in);
			add_irn_n(new_node, in);
		}
	} else {
192
		ir_node **ins = ALLOCAN(ir_node*, arity);
Matthias Braun's avatar
Matthias Braun committed
193
		for (int i = 0; i < arity; ++i) {
194
195
196
197
198
199
200
			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);
	}

201
	copy_node_attr(irg, node, new_node);
202
203
204
205
206
207
	be_duplicate_deps(node, new_node);

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

208
209
ir_node *be_transform_node(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
210
	ir_node *new_node = be_get_transformed_node(node);
211
	if (new_node != NULL)
212
213
		return new_node;

214
	DEBUG_ONLY(be_set_transformed_node(node, NULL);)
215

Matthias Braun's avatar
Matthias Braun committed
216
217
	ir_op *op = get_irn_op(node);
	be_transform_func *transform = (be_transform_func *)op->ops.generic;
218
219
220

	new_node = transform(node);
	assert(new_node != NULL);
221
222
223
224
225

	be_set_transformed_node(node, new_node);
	return new_node;
}

226
227
void be_enqueue_preds(ir_node *node)
{
228
	/* put the preds in the worklist */
Matthias Braun's avatar
Matthias Braun committed
229
230
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
231
232
233
234
235
236
237
238
		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.
 */
239
240
static void fix_loops(ir_node *node)
{
241
	if (irn_visited_else_mark(node))
242
243
		return;

244
245
	assert(node_is_in_irgs_storage(env.irg, node));

Matthias Braun's avatar
Matthias Braun committed
246
	bool changed = false;
247
248
	if (! is_Block(node)) {
		ir_node *block     = get_nodes_block(node);
249
		ir_node *new_block = (ir_node*)get_irn_link(block);
250
251
252
253

		if (new_block != NULL) {
			set_nodes_block(node, new_block);
			block = new_block;
Matthias Braun's avatar
Matthias Braun committed
254
			changed = true;
255
256
257
258
259
		}

		fix_loops(block);
	}

Matthias Braun's avatar
Matthias Braun committed
260
261
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
262
		ir_node *in = get_irn_n(node, i);
263
		ir_node *nw = (ir_node*)get_irn_link(in);
264
265
266
267

		if (nw != NULL && nw != in) {
			set_irn_n(node, i, nw);
			in = nw;
Matthias Braun's avatar
Matthias Braun committed
268
			changed = true;
269
270
271
272
		}

		fix_loops(in);
	}
273
	/* fix proj block */
274
	if (is_Proj(node)) {
275
		set_nodes_block(node, get_nodes_block(get_Proj_pred(node)));
Matthias Braun's avatar
Matthias Braun committed
276
		changed = true;
277
	}
278
279

	arity = get_irn_deps(node);
Matthias Braun's avatar
Matthias Braun committed
280
	for (int i = 0; i < arity; ++i) {
281
		ir_node *in = get_irn_dep(node, i);
282
		ir_node *nw = (ir_node*)get_irn_link(in);
283
284
285
286

		if (nw != NULL && nw != in) {
			set_irn_dep(node, i, nw);
			in = nw;
Matthias Braun's avatar
Matthias Braun committed
287
			changed = true;
288
289
290
291
		}

		fix_loops(in);
	}
292

293
	if (changed) {
294
		identify_remember(node);
295
	}
296
297
}

298
299
ir_node *be_pre_transform_node(ir_node *place)
{
300
301
302
303
304
305
	if (place == NULL)
		return NULL;

	return be_transform_node(place);
}

306
static void pre_transform_anchor(ir_graph *irg, int anchor)
307
308
309
{
	ir_node *old_anchor_node = get_irn_n(env.old_anchor, anchor);
	ir_node *transformed     = be_transform_node(old_anchor_node);
310
	set_irg_anchor(irg, anchor, transformed);
311
312
}

313
314
315
/**
 * Transforms all nodes. Deletes the old obstack and creates a new one.
 */
316
static void transform_nodes(ir_graph *irg, arch_pretrans_nodes *pre_transform)
317
{
318
319
320
321
	hook_dead_node_elim(irg, 1);

	inc_irg_visited(irg);

322
323
324
	env.irg        = irg;
	env.worklist   = new_waitq();
	env.old_anchor = irg->anchor;
325

Matthias Braun's avatar
Matthias Braun committed
326
	ir_node *old_end = get_irg_end(irg);
327
328

	/* put all anchor nodes in the worklist */
Matthias Braun's avatar
Matthias Braun committed
329
	for (int i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
330
		ir_node *anchor = get_irg_anchor(irg, i);
331
332
333
334
335
336

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

Matthias Braun's avatar
Matthias Braun committed
337
	ir_node *new_anchor  = new_r_Anchor(irg);
338
	irg->anchor = new_anchor;
339

340
341
	/* pre transform some anchors (so they are available in the other transform
	 * functions) */
342
343
344
345
346
347
	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);
348
349

	if (pre_transform)
350
		pre_transform();
351
352
353

	/* process worklist (this should transform all nodes in the graph) */
	while (! waitq_empty(env.worklist)) {
354
		ir_node *node = (ir_node*)waitq_get(env.worklist);
355
356
357
358
359
		be_transform_node(node);
	}

	/* fix loops and set new anchors*/
	inc_irg_visited(irg);
Matthias Braun's avatar
Matthias Braun committed
360
	for (int i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
361
		ir_node *anchor = get_irn_n(env.old_anchor, i);
362
363
364
365

		if (anchor == NULL)
			continue;

366
		anchor = (ir_node*)get_irn_link(anchor);
367
		fix_loops(anchor);
368
		set_irn_n(new_anchor, i, anchor);
369
370
371
372
373
374
375
	}

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

376
void be_transform_graph(ir_graph *irg, arch_pretrans_nodes *func)
377
378
379
380
381
{
	ir_graph *old_current_ir_graph = current_ir_graph;
	current_ir_graph = irg;

	/* create a new obstack */
382
383
	struct obstack old_obst = irg->obst;
	obstack_init(&irg->obst);
384
385
	irg->last_node_idx = 0;

386
	free_vrp_data(irg);
387

388
	/* create new value table for CSE */
389
	new_identities(irg);
390
391

	/* do the main transformation */
392
	transform_nodes(irg, func);
393
394

	/* free the old obstack */
395
	obstack_free(&old_obst, 0);
396
397
398
399

	/* restore state */
	current_ir_graph = old_current_ir_graph;

400
	/* most analysis info is wrong after transformation */
401
	be_invalidate_live_chk(irg);
Matthias Braun's avatar
Matthias Braun committed
402
	confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
403

404
405
406
	/* recalculate edges */
	edges_activate(irg);
}
407
408
409
410

bool be_upper_bits_clean(const ir_node *node, ir_mode *mode)
{
	ir_op *op = get_irn_op(node);
411
	if (op->ops.generic2 == NULL)
412
		return false;
413
	upper_bits_clean_func func = (upper_bits_clean_func)op->ops.generic2;
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
	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)
{
516
	op->ops.generic2 = (op_func)func;
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
}

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);
533
	be_set_transform_function(op_Proj,        transform_proj);
534
535
536
537
538
539
540
541
542
543
544
545
546
	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);
}