belower.c 19.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Author:      Christian Wuerdig
 * Date:        2005/12/14
 * Copyright:   (c) Universitaet Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 * CVS-Id:      $Id$
 *
 * Performs lowering of perm nodes and spill/reload optimization.
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

Christian Würdig's avatar
Christian Würdig committed
14
15
16
#include <stdlib.h>

#include "ircons.h"
Christian Würdig's avatar
Christian Würdig committed
17
#include "debug.h"
Christian Würdig's avatar
Christian Würdig committed
18

19
20
21
22
#include "bearch.h"
#include "belower.h"
#include "benode_t.h"
#include "bechordal_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
23
#include "besched_t.h"
24
25

#include "irgmod.h"
Daniel Grund's avatar
Daniel Grund committed
26
#include "iredges_t.h"
27
28
#include "irgwalk.h"

Michael Beck's avatar
Michael Beck committed
29
30
31
32
33
#ifdef HAVE_MALLOC_H
 #include <malloc.h>
#endif
#ifdef HAVE_ALLOCA_H
 #include <alloca.h>
Christian Würdig's avatar
Christian Würdig committed
34
35
#endif

36
37
38
#undef is_Perm
#define is_Perm(arch_env, irn) (arch_irn_classify(arch_env, irn) == arch_irn_class_perm)

Christian Würdig's avatar
Christian Würdig committed
39
40
41
#undef is_Call
#define is_Call(arch_env, irn) (arch_irn_classify(arch_env, irn) == arch_irn_class_call)

42
43
/* lowering walker environment */
typedef struct _lower_env_t {
Christian Würdig's avatar
Christian Würdig committed
44
45
	be_chordal_env_t  *chord_env;
	int                do_copy;
46
	DEBUG_ONLY(firm_dbg_module_t *dbg_module;)
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
} lower_env_t;

/* holds a perm register pair */
typedef struct _reg_pair_t {
	const arch_register_t *in_reg;    /**< a perm IN register */
	ir_node               *in_node;   /**< the in node to which the register belongs */

	const arch_register_t *out_reg;   /**< a perm OUT register */
	ir_node               *out_node;  /**< the out node to which the register belongs */

	int                    checked;   /**< indicates whether the pair was check for cycle or not */
} reg_pair_t;

typedef enum _perm_type_t {
	PERM_CYCLE,
	PERM_CHAIN,
	PERM_SWAP,
	PERM_COPY
} perm_type_t;

Christian Würdig's avatar
Christian Würdig committed
67
/* structure to represent cycles or chains in a perm */
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
typedef struct _perm_cycle_t {
	const arch_register_t **elems;       /**< the registers in the cycle */
	int                     n_elems;     /**< number of elements in the cycle */
	perm_type_t             type;        /**< type (CHAIN or CYCLE) */
} perm_cycle_t;

/* Compare the in registers of two register pairs */
static int compare_reg_pair(const void *a, const void *b) {
	const reg_pair_t *pair_a = a;
	const reg_pair_t *pair_b = b;

	if (pair_a->in_reg->index > pair_b->in_reg->index)
		return 1;
	else
		return -1;
}

Christian Würdig's avatar
Christian Würdig committed
85
/* returns the number register pairs marked as checked */
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
static int get_n_checked_pairs(reg_pair_t *pairs, int n) {
	int i, n_checked = 0;

	for (i = 0; i < n; i++) {
		if (pairs[i].checked)
			n_checked++;
	}

	return n_checked;
}

/**
 * Gets the node corresponding to a register from an array of register pairs.
 * NOTE: The given registers pairs and the register to look for must belong
 *       to the same register class.
 *
 * @param pairs  The array of register pairs
 * @param n      The number of pairs
 * @param reg    The register to look for
 * @param in_out 0 == look for IN register, 1 == look for OUT register
 * @return The corresponding node or NULL if not found
 */
static ir_node *get_node_for_register(reg_pair_t *pairs, int n, const arch_register_t *reg, int in_out) {
	int i;

Christian Würdig's avatar
Christian Würdig committed
111
112
	if (in_out) {
		for (i = 0; i < n; i++) {
113
114
115
116
			/* out register matches */
			if (pairs[i].out_reg->index == reg->index)
				return pairs[i].out_node;
		}
Christian Würdig's avatar
Christian Würdig committed
117
118
119
	}
	else {
		for (i = 0; i < n; i++) {
120
121
122
123
124
125
126
127
128
			/* in register matches */
			if (pairs[i].in_reg->index == reg->index)
				return pairs[i].in_node;
		}
	}

	return NULL;
}

Christian Würdig's avatar
Christian Würdig committed
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
 * Gets the index in the register pair array where the in/out register
 * corresponds to reg_idx.
 *
 * @param pairs  The array of register pairs
 * @param n      The number of pairs
 * @param reg    The register index to look for
 * @param in_out 0 == look for IN register, 1 == look for OUT register
 * @return The corresponding index in pairs or -1 if not found
 */
static int get_pairidx_for_regidx(reg_pair_t *pairs, int n, int reg_idx, int in_out) {
	int i;

	if (in_out) {
		for (i = 0; i < n; i++) {
			/* out register matches */
			if (pairs[i].out_reg->index == reg_idx)
				return i;
		}
	}
	else {
		for (i = 0; i < n; i++) {
			/* in register matches */
			if (pairs[i].in_reg->index == reg_idx)
				return i;
		}
	}

	return -1;
}

160
161
162
163
164
165
166
167
168
169
170
171
/**
 * Gets an array of register pairs and tries to identify a cycle or chain starting
 * at position start.
 *
 * @param cycle Variable to hold the cycle
 * @param pairs Array of register pairs
 * @param start Index to start
 * @return The cycle or chain
 */
static perm_cycle_t *get_perm_cycle(perm_cycle_t *cycle, reg_pair_t *pairs, int n, int start) {
	int head         = pairs[start].in_reg->index;
	int cur_idx      = pairs[start].out_reg->index;
Christian Würdig's avatar
Christian Würdig committed
172
	int cur_pair_idx = start;
173
	int n_pairs_done = get_n_checked_pairs(pairs, n);
Christian Würdig's avatar
Christian Würdig committed
174
	int idx;
Christian Würdig's avatar
Christian Würdig committed
175
176
177
	perm_type_t cycle_tp = PERM_CYCLE;

	/* We could be right in the middle of a chain, so we need to find the start */
Christian Würdig's avatar
Christian Würdig committed
178
	while (head != cur_idx) {
Christian Würdig's avatar
Christian Würdig committed
179
180
181
182
183
		/* goto previous register in cycle or chain */
		cur_pair_idx = get_pairidx_for_regidx(pairs, n, head, 1);

		if (cur_pair_idx < 0) {
			cycle_tp = PERM_CHAIN;
Christian Würdig's avatar
Christian Würdig committed
184
			break;
Christian Würdig's avatar
Christian Würdig committed
185
186
187
188
189
190
		}
		else {
			head  = pairs[cur_pair_idx].in_reg->index;
			start = cur_pair_idx;
		}
	}
191
192

	/* assume worst case: all remaining pairs build a cycle or chain */
193
	cycle->elems    = xcalloc((n - n_pairs_done) * 2, sizeof(cycle->elems[0]));
194
195
196
	cycle->n_elems  = 2;  /* initial number of elements is 2 */
	cycle->elems[0] = pairs[start].in_reg;
	cycle->elems[1] = pairs[start].out_reg;
Christian Würdig's avatar
Christian Würdig committed
197
	cycle->type     = cycle_tp;
Christian Würdig's avatar
Christian Würdig committed
198
	cur_idx         = pairs[start].out_reg->index;
199
200
201

	idx = 2;
	/* check for cycle or end of a chain */
Christian Würdig's avatar
Christian Würdig committed
202
	while (cur_idx != head) {
203
		/* goto next register in cycle or chain */
Christian Würdig's avatar
Christian Würdig committed
204
205
206
207
208
209
		cur_pair_idx = get_pairidx_for_regidx(pairs, n, cur_idx, 0);

		if (cur_pair_idx < 0)
			break;

		cur_idx = pairs[cur_pair_idx].out_reg->index;
210
211
212

		/* it's not the first element: insert it */
		if (cur_idx != head) {
Christian Würdig's avatar
Christian Würdig committed
213
			cycle->elems[idx++] = pairs[cur_pair_idx].out_reg;
214
215
216
217
218
219
			cycle->n_elems++;
		}
		else {
			/* we are there where we started -> CYCLE */
			cycle->type = PERM_CYCLE;
		}
Christian Würdig's avatar
Christian Würdig committed
220
	}
221

Christian Würdig's avatar
Christian Würdig committed
222
223
224
225
226
227
228
229
230
231
232
	/* mark all pairs having one in/out register with cycle in common as checked */
	for (idx = 0; idx < cycle->n_elems; idx++) {
		cur_pair_idx = get_pairidx_for_regidx(pairs, n, cycle->elems[idx]->index, 0);

		if (cur_pair_idx >= 0)
			pairs[cur_pair_idx].checked = 1;

		cur_pair_idx = get_pairidx_for_regidx(pairs, n, cycle->elems[idx]->index, 1);

		if (cur_pair_idx >= 0)
			pairs[cur_pair_idx].checked = 1;
233
234
235
236
237
238
239
240
	}

	return cycle;
}

/**
 * Lowers a perm node.  Resolves cycles and creates a bunch of
 * copy and swap operations to permute registers.
Christian Würdig's avatar
Christian Würdig committed
241
242
 * Note: The caller of this function has to make sure, that irn
 *       is a Perm node.
243
244
 *
 * @param irn      The perm node
245
 * @param block    The block the perm node belongs to
246
247
 * @param walk_env The environment
 */
248
static void lower_perm_node(ir_node *irn, void *walk_env) {
249
250
251
252
253
254
	const arch_register_class_t *reg_class;
	const arch_env_t            *arch_env;
	lower_env_t     *env = walk_env;
	reg_pair_t      *pairs;
	const ir_edge_t *edge;
	perm_cycle_t    *cycle;
Christian Würdig's avatar
Christian Würdig committed
255
	int              n, i, pn, do_copy, j;
256
257
	ir_node         *sched_point, *block, *in[2];
	ir_node         *arg1, *arg2, *res1, *res2;
258
	ir_node         *cpyxchg = NULL;
259
	DEBUG_ONLY(firm_dbg_module_t *mod;)
260

Sebastian Hack's avatar
Sebastian Hack committed
261
	arch_env = env->chord_env->birg->main_env->arch_env;
262
	do_copy  = env->do_copy;
263
	DEBUG_ONLY(mod = env->dbg_module;)
264
	block    = get_nodes_block(irn);
265
266
267
268
269
270
271
272

	/*
		Get the schedule predecessor node to the perm
		NOTE: This works with auto-magic. If we insert the
			new copy/exchange nodes after this node, everything
			should be ok.
	*/
	sched_point = sched_prev(irn);
273
	DBG((mod, LEVEL_1, "sched point is %+F\n", sched_point));
274
275
276
277
278
279
	assert(sched_point && "Perm is not scheduled or has no predecessor");

	n = get_irn_arity(irn);
	assert(n == get_irn_n_edges(irn) && "perm's in and out numbers different");

	reg_class = arch_get_irn_register(arch_env, get_irn_n(irn, 0))->reg_class;
Christian Würdig's avatar
Christian Würdig committed
280
	pairs     = alloca(n * sizeof(pairs[0]));
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300

	/* build the list of register pairs (in, out) */
	i = 0;
	foreach_out_edge(irn, edge) {
		pairs[i].out_node = get_edge_src_irn(edge);
		pn                = get_Proj_proj(pairs[i].out_node);
		pairs[i].in_node  = get_irn_n(irn, pn);

		pairs[i].in_reg  = arch_get_irn_register(arch_env, pairs[i].in_node);
		pairs[i].out_reg = arch_get_irn_register(arch_env, pairs[i].out_node);

		pairs[i].checked = 0;
		i++;
	}

	/* sort the register pairs by the indices of the in registers */
	qsort(pairs, n, sizeof(pairs[0]), compare_reg_pair);

	/* Mark all equal pairs as checked, and exchange the OUT proj with
		the IN node. */
Christian Würdig's avatar
Christian Würdig committed
301
302
	for (i = 0; i < n; i++) {
		if (pairs[i].in_reg->index == pairs[i].out_reg->index) {
303
304
305
306
307
308
309
310
			DBG((mod, LEVEL_1, "%+F removing equal perm register pair (%+F, %+F, %s)\n",
				irn, pairs[i].in_node, pairs[i].out_node, pairs[i].out_reg->name));

			/* We have to check for a special case:
				The in-node could be a Proj from a Perm. In this case,
				we need to correct the projnum */
			if (is_Perm(arch_env, pairs[i].in_node) && is_Proj(pairs[i].in_node)) {
				set_Proj_proj(pairs[i].out_node, get_Proj_proj(pairs[i].in_node));
Christian Würdig's avatar
Christian Würdig committed
311
312
313
314
			}

			/* remove the proj from the schedule */
			sched_remove(pairs[i].out_node);
315

Christian Würdig's avatar
Christian Würdig committed
316
			/* reroute the edges from the proj to the argument */
317
			edges_reroute(pairs[i].out_node, pairs[i].in_node, env->chord_env->irg);
318

Christian Würdig's avatar
Christian Würdig committed
319
320
			pairs[i].checked = 1;
		}
321
322
323
324
325
326
327
328
329
330
331
332
333
	}

	/* Set do_copy to 0 if it's on but we have no free register */
	if (do_copy) {
		do_copy = 0;
	}

	/* check for cycles and chains */
	while (get_n_checked_pairs(pairs, n) < n) {
		i = 0;

		/* go to the first not-checked pair */
		while (pairs[i].checked) i++;
334
		cycle = xcalloc(1, sizeof(*cycle));
335
336
		cycle = get_perm_cycle(cycle, pairs, n, i);

Christian Würdig's avatar
Christian Würdig committed
337
338
339
340
341
342
		DB((mod, LEVEL_1, "%+F: following %s created:\n  ", irn, cycle->type == PERM_CHAIN ? "chain" : "cycle"));
		for (j = 0; j < cycle->n_elems; j++) {
			DB((mod, LEVEL_1, " %s", cycle->elems[j]->name));
		}
		DB((mod, LEVEL_1, "\n"));

343
344
345
346
347
348
349
350
		/* We don't need to do anything if we have a Perm with two
			elements which represents a cycle, because those nodes
			already represent exchange nodes */
		if (n == 2 && cycle->type == PERM_CYCLE) {
			free(cycle);
			continue;
		}

Christian Würdig's avatar
Christian Würdig committed
351
//TODO: - iff PERM_CYCLE && do_copy -> determine free temp reg and insert copy to/from it before/after
352
353
//        the copy cascade (this reduces the cycle into a chain)

Christian Würdig's avatar
Christian Würdig committed
354
355
		/* build copy/swap nodes from back to front */
		for (i = cycle->n_elems - 2; i >= 0; i--) {
356
357
358
359
360
			arg1 = get_node_for_register(pairs, n, cycle->elems[i], 0);
			arg2 = get_node_for_register(pairs, n, cycle->elems[i + 1], 0);

			res1 = get_node_for_register(pairs, n, cycle->elems[i], 1);
			res2 = get_node_for_register(pairs, n, cycle->elems[i + 1], 1);
361
362
363
364
365
366
367
368
369
370

			/*
				If we have a cycle and don't copy: we need to create exchange nodes
				NOTE: An exchange node is a perm node with 2 INs and 2 OUTs
				IN_1  = in node with register i
				IN_2  = in node with register i + 1
				OUT_1 = out node with register i + 1
				OUT_2 = out node with register i
			*/
			if (cycle->type == PERM_CYCLE && !do_copy) {
371
372
				in[0] = arg1;
				in[1] = arg2;
373

Christian Würdig's avatar
Christian Würdig committed
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
				/* At this point we have to handle the following problem:     */
				/*                                                            */
				/* If we have a cycle with more than two elements, then       */
				/* this could correspond to the following Perm node:          */
				/*                                                            */
				/*   +----+   +----+   +----+                                 */
				/*   | r1 |   | r2 |   | r3 |                                 */
				/*   +-+--+   +-+--+   +--+-+                                 */
				/*     |        |         |                                   */
				/*     |        |         |                                   */
				/*   +-+--------+---------+-+                                 */
				/*   |         Perm         |                                 */
				/*   +-+--------+---------+-+                                 */
				/*     |        |         |                                   */
				/*     |        |         |                                   */
				/*   +-+--+   +-+--+   +--+-+                                 */
				/*   |Proj|   |Proj|   |Proj|                                 */
				/*   | r2 |   | r3 |   | r1 |                                 */
				/*   +----+   +----+   +----+                                 */
				/*                                                            */
				/* This node is about to be split up into two 2x Perm's       */
				/* for which we need 4 Proj's and the one additional Proj     */
				/* of the first Perm has to be one IN of the second. So in    */
				/* general we need to create one additional Proj for each     */
				/* "middle" Perm and set this to one in node of the successor */
				/* Perm.                                                      */

401
402
403
404
				DBG((mod, LEVEL_1, "%+F creating exchange node (%+F, %s) and (%+F, %s) with\n",
					irn, arg1, cycle->elems[i]->name, arg2, cycle->elems[i + 1]->name));
				DBG((mod, LEVEL_1, "%+F                        (%+F, %s) and (%+F, %s)\n",
					irn, res1, cycle->elems[i]->name, res2, cycle->elems[i + 1]->name));
Christian Würdig's avatar
Christian Würdig committed
405

Sebastian Hack's avatar
Sebastian Hack committed
406
				cpyxchg = be_new_Perm(reg_class, env->chord_env->irg, block, 2, in);
407

Christian Würdig's avatar
Christian Würdig committed
408
409
410
411
412
				if (i > 0) {
					/* cycle is not done yet */
					int pidx = get_pairidx_for_regidx(pairs, n, cycle->elems[i]->index, 0);

					/* create intermediate proj */
Christian Würdig's avatar
Christian Würdig committed
413
					res1 = new_r_Proj(get_irn_irg(irn), block, cpyxchg, get_irn_mode(res1), 0);
Christian Würdig's avatar
Christian Würdig committed
414
415

					/* set as in for next Perm */
Christian Würdig's avatar
Christian Würdig committed
416
					pairs[pidx].in_node = res1;
Christian Würdig's avatar
Christian Würdig committed
417
418
				}
				else {
Christian Würdig's avatar
Christian Würdig committed
419
					sched_remove(res1);
Christian Würdig's avatar
Christian Würdig committed
420
421
				}

Christian Würdig's avatar
Christian Würdig committed
422
				sched_remove(res2);
423
424
425
426
427
428
429
430
431
432
433

				set_Proj_pred(res2, cpyxchg);
				set_Proj_proj(res2, 0);
				set_Proj_pred(res1, cpyxchg);
				set_Proj_proj(res1, 1);

				sched_add_after(sched_point, res1);
				sched_add_after(sched_point, res2);

				arch_set_irn_register(arch_env, res2, cycle->elems[i + 1]);
				arch_set_irn_register(arch_env, res1, cycle->elems[i]);
Christian Würdig's avatar
Christian Würdig committed
434
435
436
437
438
439
440
441

				/* insert the copy/exchange node in schedule after the magic schedule node (see above) */
				sched_add_after(sched_point, cpyxchg);

				DBG((mod, LEVEL_1, "replacing %+F with %+F, placed new node after %+F\n", irn, cpyxchg, sched_point));

				/* set the new scheduling point */
				sched_point = res1;
442
443
			}
			else {
444
445
				DBG((mod, LEVEL_1, "%+F creating copy node (%+F, %s) -> (%+F, %s)\n",
					irn, arg1, cycle->elems[i]->name, res2, cycle->elems[i + 1]->name));
Christian Würdig's avatar
Christian Würdig committed
446

Sebastian Hack's avatar
Sebastian Hack committed
447
				cpyxchg = be_new_Copy(reg_class, env->chord_env->irg, block, arg1);
448
449
450
				arch_set_irn_register(arch_env, cpyxchg, cycle->elems[i + 1]);

				/* remove the proj from the schedule */
451
				sched_remove(res2);
452
453

				/* exchange copy node and proj */
454
				exchange(res2, cpyxchg);
455

Christian Würdig's avatar
Christian Würdig committed
456
457
				/* insert the copy/exchange node in schedule after the magic schedule node (see above) */
				sched_add_after(sched_point, cpyxchg);
458

Christian Würdig's avatar
Christian Würdig committed
459
460
461
				/* set the new scheduling point */
				sched_point = cpyxchg;
			}
462
463
		}

Sebastian Hack's avatar
Sebastian Hack committed
464
		free((void *) cycle->elems);
465
466
467
468
469
470
471
		free(cycle);
	}

	/* remove the perm from schedule */
	sched_remove(irn);
}

472
473


Christian Würdig's avatar
Christian Würdig committed
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
static int get_n_out_edges(const ir_node *irn) {
	const ir_edge_t *edge;
	int cnt = 0;

	foreach_out_edge(irn, edge) {
		cnt++;
	}

	return cnt;
}

static ir_node *belower_skip_proj(ir_node *irn) {
	while(is_Proj(irn))
		irn = get_Proj_pred(irn);
	return irn;
}

static void fix_in(ir_node *irn, ir_node *old, ir_node *nw) {
Christian Würdig's avatar
Christian Würdig committed
492
	int i, n;
Christian Würdig's avatar
Christian Würdig committed
493
494

	irn = belower_skip_proj(irn);
Christian Würdig's avatar
Christian Würdig committed
495
	n   = get_irn_arity(irn);
Christian Würdig's avatar
Christian Würdig committed
496
497
498
499
500
501
502
503
504
505
506

	for (i = 0; i < n; i++) {
		if (get_irn_n(irn, i) == old) {
			set_irn_n(irn, i, nw);
			break;
		}
	}
}

static void gen_assure_different_pattern(ir_node *irn, be_irg_t *birg, ir_node *other_different) {
	const arch_env_t          *arch_env = birg->main_env->arch_env;
Christian Würdig's avatar
Christian Würdig committed
507
	ir_node                   *in[2], *keep, *cpy, *temp;
Christian Würdig's avatar
Christian Würdig committed
508
509
	ir_node                   *block = get_nodes_block(irn);
	const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, other_different, -1);
510
	FIRM_DBG_REGISTER(firm_dbg_module_t *mod, "firm.be.lower");
Christian Würdig's avatar
Christian Würdig committed
511

512
	if (arch_irn_is(arch_env, other_different, ignore) || ! mode_is_datab(get_irn_mode(other_different))) {
Christian Würdig's avatar
Christian Würdig committed
513
		DBG((mod, LEVEL_1, "ignore constraint for %+F because other_irn is ignore or not a datab node\n", irn));
Christian Würdig's avatar
Christian Würdig committed
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
		return;
	}

	/* Make a not spillable copy of the different node   */
	/* this is needed because the different irn could be */
	/* in block far far away                             */
	/* The copy is optimized later if not needed         */

	temp = new_rd_Unknown(birg->irg, get_irn_mode(other_different));
	cpy = be_new_Copy(cls, birg->irg, block, temp);
	be_node_set_flags(cpy, BE_OUT_POS(0), arch_irn_flags_dont_spill);

	in[0] = irn;
	in[1] = cpy;

Christian Würdig's avatar
Christian Würdig committed
529
530
531
	/* Let the irn use the copy instead of the old other_different */
	fix_in(irn, other_different, cpy);

Christian Würdig's avatar
Christian Würdig committed
532
533
	/* Add the Keep resp. CopyKeep and reroute the users */
	/* of the other_different irn in case of CopyKeep.   */
Christian Würdig's avatar
Christian Würdig committed
534
	if (get_n_out_edges(other_different) == 0) {
Christian Würdig's avatar
Christian Würdig committed
535
536
537
		keep = be_new_Keep(cls, birg->irg, block, 2, in);
	}
	else {
Christian Würdig's avatar
Christian Würdig committed
538
		keep = be_new_CopyKeep_single(cls, birg->irg, block, cpy, irn, get_irn_mode(other_different));
539
		be_node_set_reg_class(keep, 1, cls);
Christian Würdig's avatar
Christian Würdig committed
540
541
542
543
544
545
546
547
548
		edges_reroute(other_different, keep, birg->irg);
	}

	/* after rerouting: let the copy point to the other_different irn */
	set_irn_n(cpy, 0, other_different);

	DBG((mod, LEVEL_1, "created %+F for %+F to assure should_be_different\n", keep, irn));
}

549
550
551
552
/**
 * Checks if node has a should_be_different constraint in output
 * and adds a Keep then to assure the constraint.
 */
Christian Würdig's avatar
Christian Würdig committed
553
static void assure_different_constraints(ir_node *irn, be_irg_t *birg) {
554
	const arch_env_t          *arch_env = birg->main_env->arch_env;
555
556
	const arch_register_req_t *req;
	arch_register_req_t        req_temp;
Christian Würdig's avatar
Christian Würdig committed
557
	int i, n;
558
559
560

	req = arch_get_register_req(arch_env, &req_temp, irn, -1);

Christian Würdig's avatar
Christian Würdig committed
561
562
563
564
565
566
567
568
569
570
	if (req) {
		if (arch_register_req_is(req, should_be_different)) {
			gen_assure_different_pattern(irn, birg, req->other_different);
		}
		else if (arch_register_req_is(req, should_be_different_from_all)) {
			n = get_irn_arity(belower_skip_proj(irn));
			for (i = 0; i < n; i++) {
				gen_assure_different_pattern(irn, birg, get_irn_n(belower_skip_proj(irn), i));
			}
		}
571
572
573
574
575
576
	}
}



/**
577
 * Calls the functions to assure register constraints.
578
579
580
581
 *
 * @param irn      The node to be checked for lowering
 * @param walk_env The walker environment
 */
582
static void assure_constraints_walker(ir_node *irn, void *walk_env) {
583
584
585
586
	if (is_Block(irn))
		return;

	if (mode_is_datab(get_irn_mode(irn)))
Christian Würdig's avatar
Christian Würdig committed
587
		assure_different_constraints(irn, walk_env);
588
589
590
591
592
593

	return;
}



594
595
596
597
598
599
600
601
602
603
604
/**
 * Walks over all nodes to assure register constraints.
 *
 * @param birg  The birg structure containing the irg
 */
void assure_constraints(be_irg_t *birg) {
	irg_walk_blkwise_graph(birg->irg, NULL, assure_constraints_walker, birg);
}



Christian Würdig's avatar
Christian Würdig committed
605
606
607
608
609
610
/**
 * Calls the corresponding lowering function for the node.
 *
 * @param irn      The node to be checked for lowering
 * @param walk_env The walker environment
 */
611
static void lower_nodes_after_ra_walker(ir_node *irn, void *walk_env) {
Christian Würdig's avatar
Christian Würdig committed
612
	lower_env_t      *env      = walk_env;
Sebastian Hack's avatar
Sebastian Hack committed
613
	const arch_env_t *arch_env = env->chord_env->birg->main_env->arch_env;
Christian Würdig's avatar
Christian Würdig committed
614

Sebastian Hack's avatar
Sebastian Hack committed
615
616
617
618
	if (!is_Block(irn) && !is_Proj(irn)) {
		if (is_Perm(arch_env, irn)) {
			lower_perm_node(irn, walk_env);
		}
Christian Würdig's avatar
Christian Würdig committed
619
620
621
622
623
	}

	return;
}

Christian Würdig's avatar
Christian Würdig committed
624
625


626
627
/**
 * Walks over all blocks in an irg and performs lowering need to be
628
 * done after register allocation (e.g. perm lowering).
629
630
631
632
 *
 * @param chord_env The chordal environment containing the irg
 * @param do_copy   1 == resolve cycles with a free reg if available
 */
633
void lower_nodes_after_ra(be_chordal_env_t *chord_env, int do_copy) {
634
635
	lower_env_t env;

Christian Würdig's avatar
Christian Würdig committed
636
637
	env.chord_env  = chord_env;
	env.do_copy    = do_copy;
638
	FIRM_DBG_REGISTER(env.dbg_module, "firm.be.lower");
639

640
	irg_walk_blkwise_graph(chord_env->irg, NULL, lower_nodes_after_ra_walker, &env);
641
}
Christian Würdig's avatar
Christian Würdig committed
642
643
644

#undef is_Perm
#undef is_Call