betranshlp.c 14 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
17
18
 * @date        14.06.2007
 */
#include "config.h"

#include "pdeq.h"
#include "irop_t.h"
#include "iropt_t.h"
#include "irnode_t.h"
#include "irgraph_t.h"
19
#include "ircons_t.h"
20
21
22
23
24
25
#include "irhooks.h"
#include "iredges.h"
#include "irouts.h"
#include "trouts.h"
#include "cgana.h"
#include "debug.h"
26
#include "execfreq_t.h"
27

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

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 */
38
	ir_node  *old_anchor;  /**< the old anchor node in the old irg */
39
40
41
42
43
} be_transform_env_t;


static be_transform_env_t env;

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

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

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

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

		add_irn_dep(new_node, new_dep);
	}
}

76
77
78
ir_node *be_transform_phi(ir_node *node, const arch_register_req_t *req)
{
	ir_node  *block = be_transform_node(get_nodes_block(node));
79
	ir_graph *irg   = get_Block_irg(block);
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
	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;
}

104
105
106
107
108
109
110
111
112
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;
}

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

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

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

	return new_end;
}

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

187
	copy_node_attr(irg, node, new_node);
188
189
190
191
192
193
	be_duplicate_deps(node, new_node);

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

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

200
	DEBUG_ONLY(be_set_transformed_node(node, NULL);)
201

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

	new_node = transform(node);
	assert(new_node != NULL);
207
208
209
210
211

	be_set_transformed_node(node, new_node);
	return new_node;
}

212
213
void be_enqueue_preds(ir_node *node)
{
214
	/* put the preds in the worklist */
Matthias Braun's avatar
Matthias Braun committed
215
216
	int arity = get_irn_arity(node);
	for (int i = 0; i < arity; ++i) {
217
218
219
220
221
222
223
224
		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.
 */
225
226
static void fix_loops(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
227
228
	assert(node_is_in_irgs_storage(env.irg, node));

229
	if (irn_visited_else_mark(node))
230
231
		return;

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

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

		fix_loops(block);
	}

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

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

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

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

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

		fix_loops(in);
	}
278

279
	if (changed) {
280
		identify_remember(node);
281
	}
282
283
}

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

	return be_transform_node(place);
}

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

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

	inc_irg_visited(irg);

308
309
310
	env.irg        = irg;
	env.worklist   = new_waitq();
	env.old_anchor = irg->anchor;
311

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

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

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

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

326
327
	/* pre transform some anchors (so they are available in the other transform
	 * functions) */
328
329
330
331
332
333
	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);
334
335

	if (pre_transform)
336
		pre_transform();
337
338
339

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

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

		if (anchor == NULL)
			continue;

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

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

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

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

372
	free_vrp_data(irg);
373

374
	/* create new value table for CSE */
375
	new_identities(irg);
376
377

	/* do the main transformation */
378
	transform_nodes(irg, func);
379
380

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

	/* restore state */
	current_ir_graph = old_current_ir_graph;

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

390
391
392
	/* recalculate edges */
	edges_activate(irg);
}
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
530
531
532

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_Copy,     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);
}