belower.c 29.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
 * @file
Christian Würdig's avatar
Christian Würdig committed
22
 * @brief       Performs lowering of perm nodes. Inserts copies to assure register constraints.
Christian Würdig's avatar
Christian Würdig committed
23
24
25
 * @author      Christian Wuerdig
 * @date        14.12.2005
 * @version     $Id$
26
 */
27
#include "config.h"
28

Christian Würdig's avatar
Christian Würdig committed
29
30
31
#include <stdlib.h>

#include "ircons.h"
Christian Würdig's avatar
Christian Würdig committed
32
#include "debug.h"
33
#include "xmalloc.h"
Christian Würdig's avatar
Christian Würdig committed
34
#include "irnodeset.h"
35
#include "irnodemap.h"
Christian Würdig's avatar
Christian Würdig committed
36
37
38
#include "irgmod.h"
#include "iredges_t.h"
#include "irgwalk.h"
39
#include "array_t.h"
Christian Würdig's avatar
Christian Würdig committed
40

41
#include "bearch.h"
42
#include "belower.h"
43
#include "benode.h"
44
#include "besched.h"
Christian Würdig's avatar
Christian Würdig committed
45
#include "bestat.h"
46
#include "bessaconstr.h"
47
#include "beintlive_t.h"
48

Christian Würdig's avatar
Christian Würdig committed
49
50
#undef KEEP_ALIVE_COPYKEEP_HACK

51
52
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
DEBUG_ONLY(static firm_dbg_module_t *dbg_constr;)
Michael Beck's avatar
Michael Beck committed
53
DEBUG_ONLY(static firm_dbg_module_t *dbg_permmove;)
54

55
/** Associates an ir_node with it's copy and CopyKeep. */
56
typedef struct {
Michael Beck's avatar
Michael Beck committed
57
	ir_nodeset_t copies; /**< all non-spillable copies of this irn */
Christian Würdig's avatar
Christian Würdig committed
58
	const arch_register_class_t *cls;
59
60
} op_copy_assoc_t;

Michael Beck's avatar
Michael Beck committed
61
/** Environment for constraints. */
62
typedef struct {
63
	ir_graph      *irg;
64
	ir_nodemap_t   op_set;
65
66
67
	struct obstack obst;
} constraint_env_t;

Michael Beck's avatar
Michael Beck committed
68
/** Lowering walker environment. */
69
typedef struct lower_env_t {
70
71
	ir_graph *irg;
	unsigned  do_copy : 1;
72
73
} lower_env_t;

Michael Beck's avatar
Michael Beck committed
74
/** Holds a Perm register pair. */
75
typedef struct reg_pair_t {
76
77
78
79
80
81
82
83
84
	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;

85
typedef enum perm_type_t {
86
87
88
89
90
91
	PERM_CYCLE,
	PERM_CHAIN,
	PERM_SWAP,
	PERM_COPY
} perm_type_t;

Michael Beck's avatar
Michael Beck committed
92
/** Structure to represent cycles or chains in a Perm. */
93
typedef struct perm_cycle_t {
94
95
96
97
98
	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;

Michael Beck's avatar
Michael Beck committed
99
/** returns the number register pairs marked as checked. */
100
101
102
103
static int get_n_unchecked_pairs(reg_pair_t const *const pairs, int const n)
{
	int n_unchecked = 0;
	int i;
104
105

	for (i = 0; i < n; i++) {
106
107
		if (!pairs[i].checked)
			n_unchecked++;
108
109
	}

110
	return n_unchecked;
111
112
113
}

/**
114
 * Gets the node corresponding to an IN register from an array of register pairs.
115
116
117
118
119
120
121
122
 * 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
 * @return The corresponding node or NULL if not found
 */
123
124
static ir_node *get_node_for_in_register(reg_pair_t *pairs, int n, const arch_register_t *reg)
{
125
126
	int i;

127
128
129
130
	for (i = 0; i < n; i++) {
		/* in register matches */
		if (pairs[i].in_reg->index == reg->index)
			return pairs[i].in_node;
Christian Würdig's avatar
Christian Würdig committed
131
	}
132
133
134
135
136
137
138
139
140
141
142
143
144
145

	return NULL;
}

/**
 * Gets the node corresponding to an OUT 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
 * @return The corresponding node or NULL if not found
 */
146
147
static ir_node *get_node_for_out_register(reg_pair_t *pairs, int n, const arch_register_t *reg)
{
148
149
150
151
152
153
	int i;

	for (i = 0; i < n; i++) {
		/* out register matches */
		if (pairs[i].out_reg->index == reg->index)
			return pairs[i].out_node;
154
155
156
157
158
	}

	return NULL;
}

Christian Würdig's avatar
Christian Würdig committed
159
/**
160
 * Gets the index in the register pair array where the in register
Christian Würdig's avatar
Christian Würdig committed
161
162
163
164
165
 * 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
166
 *
Christian Würdig's avatar
Christian Würdig committed
167
168
 * @return The corresponding index in pairs or -1 if not found
 */
169
170
static int get_pairidx_for_in_regidx(reg_pair_t *pairs, int n, unsigned reg_idx)
{
Christian Würdig's avatar
Christian Würdig committed
171
172
	int i;

173
174
175
176
	for (i = 0; i < n; i++) {
		/* in register matches */
		if (pairs[i].in_reg->index == reg_idx)
			return i;
Christian Würdig's avatar
Christian Würdig committed
177
	}
178
179
180
181
182
183
184
185
186
187
188
189
190
	return -1;
}

/**
 * Gets the index in the register pair array where the 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
 *
 * @return The corresponding index in pairs or -1 if not found
 */
191
192
static int get_pairidx_for_out_regidx(reg_pair_t *pairs, int n, unsigned reg_idx)
{
193
	int i;
Christian Würdig's avatar
Christian Würdig committed
194

195
196
	for (i = 0; i < n; i++) {
		/* out register matches */
Michael Beck's avatar
Michael Beck committed
197
		if (pairs[i].out_reg->index == reg_idx)
198
199
			return i;
	}
Christian Würdig's avatar
Christian Würdig committed
200
201
202
	return -1;
}

203
/**
204
205
 * Gets an array of register pairs and tries to identify a cycle or chain
 * starting at position start.
206
 *
Michael Beck's avatar
Michael Beck committed
207
208
209
210
211
 * @param cycle  Variable to hold the cycle
 * @param pairs  Array of register pairs
 * @param n      length of the pairs array
 * @param start  Index to start
 *
212
213
 * @return The cycle or chain
 */
214
215
216
217
static void get_perm_cycle(perm_cycle_t *const cycle,
                           reg_pair_t   *const pairs,
                           int           const n,
                           int                 start)
218
219
220
{
	int         head         = pairs[start].in_reg->index;
	int         cur_idx      = pairs[start].out_reg->index;
221
	int   const n_pairs_todo = get_n_unchecked_pairs(pairs, n);
222
223
	perm_type_t cycle_tp     = PERM_CYCLE;
	int         idx;
Christian Würdig's avatar
Christian Würdig committed
224
225

	/* 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
226
	while (head != cur_idx) {
Christian Würdig's avatar
Christian Würdig committed
227
		/* goto previous register in cycle or chain */
228
		int const cur_pair_idx = get_pairidx_for_out_regidx(pairs, n, head);
Christian Würdig's avatar
Christian Würdig committed
229
230
231

		if (cur_pair_idx < 0) {
			cycle_tp = PERM_CHAIN;
Christian Würdig's avatar
Christian Würdig committed
232
			break;
233
		} else {
Christian Würdig's avatar
Christian Würdig committed
234
235
236
237
			head  = pairs[cur_pair_idx].in_reg->index;
			start = cur_pair_idx;
		}
	}
238
239

	/* assume worst case: all remaining pairs build a cycle or chain */
240
	cycle->elems    = XMALLOCNZ(const arch_register_t*, n_pairs_todo * 2);
241
242
243
	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
244
	cycle->type     = cycle_tp;
Christian Würdig's avatar
Christian Würdig committed
245
	cur_idx         = pairs[start].out_reg->index;
246
247
248

	idx = 2;
	/* check for cycle or end of a chain */
Christian Würdig's avatar
Christian Würdig committed
249
	while (cur_idx != head) {
250
		/* goto next register in cycle or chain */
251
		int const cur_pair_idx = get_pairidx_for_in_regidx(pairs, n, cur_idx);
Christian Würdig's avatar
Christian Würdig committed
252
253
254
255
256

		if (cur_pair_idx < 0)
			break;

		cur_idx = pairs[cur_pair_idx].out_reg->index;
257
258
259

		/* it's not the first element: insert it */
		if (cur_idx != head) {
Christian Würdig's avatar
Christian Würdig committed
260
			cycle->elems[idx++] = pairs[cur_pair_idx].out_reg;
261
			cycle->n_elems++;
262
		} else {
263
264
265
			/* we are there where we started -> CYCLE */
			cycle->type = PERM_CYCLE;
		}
Christian Würdig's avatar
Christian Würdig committed
266
	}
267

Christian Würdig's avatar
Christian Würdig committed
268
269
	/* mark all pairs having one in/out register with cycle in common as checked */
	for (idx = 0; idx < cycle->n_elems; idx++) {
270
		int cur_pair_idx;
Christian Würdig's avatar
Christian Würdig committed
271

272
		cur_pair_idx = get_pairidx_for_in_regidx(pairs, n, cycle->elems[idx]->index);
Christian Würdig's avatar
Christian Würdig committed
273
274
275
		if (cur_pair_idx >= 0)
			pairs[cur_pair_idx].checked = 1;

276
		cur_pair_idx = get_pairidx_for_out_regidx(pairs, n, cycle->elems[idx]->index);
Christian Würdig's avatar
Christian Würdig committed
277
278
		if (cur_pair_idx >= 0)
			pairs[cur_pair_idx].checked = 1;
279
280
281
282
283
284
	}
}

/**
 * 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
285
286
 * Note: The caller of this function has to make sure, that irn
 *       is a Perm node.
287
288
 *
 * @param irn      The perm node
289
 * @param block    The block the perm node belongs to
Michael Beck's avatar
Michael Beck committed
290
 * @param env      The lowerer environment
291
 */
Michael Beck's avatar
Michael Beck committed
292
static void lower_perm_node(ir_node *irn, lower_env_t *env)
293
294
295
{
	const arch_register_class_t *const reg_class   = arch_get_irn_register(get_irn_n(irn, 0))->reg_class;
	ir_node                     *const block       = get_nodes_block(irn);
296
	int                          const arity       = get_irn_arity(irn);
297
	reg_pair_t                  *const pairs       = ALLOCAN(reg_pair_t, arity);
298
299
300
301
302
303
304
	int                                keep_perm   = 0;
	int                                do_copy     = env->do_copy;
	/* 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. */
	ir_node                     *      sched_point = sched_prev(irn);
	const ir_edge_t             *      edge;
305
306
	const ir_edge_t             *      next;
	int                                n;
307
308
309
	int                                i;

	DBG((dbg, LEVEL_1, "perm: %+F, sched point is %+F\n", irn, sched_point));
310
311
	assert(sched_point && "Perm is not scheduled or has no predecessor");

312
	assert(arity == get_irn_n_edges(irn) && "perm's in and out numbers different");
313
314

	/* build the list of register pairs (in, out) */
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
	n = 0;
	foreach_out_edge_safe(irn, edge, next) {
		ir_node               *const out     = get_edge_src_irn(edge);
		long                   const pn      = get_Proj_proj(out);
		ir_node               *const in      = get_irn_n(irn, pn);
		arch_register_t const *const in_reg  = arch_get_irn_register(in);
		arch_register_t const *const out_reg = arch_get_irn_register(out);
		reg_pair_t            *      pair;

		if (in_reg == out_reg) {
			DBG((dbg, LEVEL_1, "%+F removing equal perm register pair (%+F, %+F, %s)\n",
						irn, in, out, out_reg->name));
			exchange(out, in);
			continue;
		}
330

331
		pair           = &pairs[n++];
332
		pair->in_node  = in;
333
		pair->in_reg   = in_reg;
334
		pair->out_node = out;
335
		pair->out_reg  = out_reg;
336
		pair->checked  = 0;
337
338
	}

339
	DBG((dbg, LEVEL_1, "%+F has %d unresolved constraints\n", irn, n));
340
341

	/* Set do_copy to 0 if it's on but we have no free register */
342
	/* TODO check for free register */
343
344
345
346
347
	if (do_copy) {
		do_copy = 0;
	}

	/* check for cycles and chains */
348
	while (get_n_unchecked_pairs(pairs, n) > 0) {
349
350
		perm_cycle_t cycle;
		int          j;
351
352

		/* go to the first not-checked pair */
353
354
		for (i = 0; pairs[i].checked; ++i) {}
		get_perm_cycle(&cycle, pairs, n, i);
355

356
357
358
		DB((dbg, LEVEL_1, "%+F: following %s created:\n  ", irn, cycle.type == PERM_CHAIN ? "chain" : "cycle"));
		for (j = 0; j < cycle.n_elems; j++) {
			DB((dbg, LEVEL_1, " %s", cycle.elems[j]->name));
Christian Würdig's avatar
Christian Würdig committed
359
		}
360
		DB((dbg, LEVEL_1, "\n"));
Christian Würdig's avatar
Christian Würdig committed
361

362
		if (cycle.type == PERM_CYCLE && arity == 2) {
363
364
365
			/* 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 */
366
			keep_perm = 1;
367
368
369
370
371
372
373
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
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
		} else {
			/* TODO: - iff PERM_CYCLE && do_copy -> determine free temp reg and
			 * insert copy to/from it before/after the copy cascade (this
			 * reduces the cycle into a chain) */

			/* build copy/swap nodes from back to front */
			for (i = cycle.n_elems - 2; i >= 0; i--) {
				ir_node *arg1 = get_node_for_in_register(pairs, n, cycle.elems[i]);
				ir_node *arg2 = get_node_for_in_register(pairs, n, cycle.elems[i + 1]);

				ir_node *res1 = get_node_for_out_register(pairs, n, cycle.elems[i]);
				ir_node *res2 = get_node_for_out_register(pairs, n, cycle.elems[i + 1]);
				/* 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) {
					ir_node *in[2];
					ir_node *cpyxchg;

					in[0] = arg1;
					in[1] = arg2;

					/* 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. */

					DBG((dbg, 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((dbg, LEVEL_1, "%+F                        (%+F, %s) and (%+F, %s)\n",
								irn, res1, cycle.elems[i]->name, res2, cycle.elems[i + 1]->name));

424
					cpyxchg = be_new_Perm(reg_class, block, 2, in);
425
426
427
428
429
430

					if (i > 0) {
						/* cycle is not done yet */
						int pidx = get_pairidx_for_in_regidx(pairs, n, cycle.elems[i]->index);

						/* create intermediate proj */
431
						res1 = new_r_Proj(cpyxchg, get_irn_mode(res1), 0);
432
433
434
435
436
437
438
439
440
441
442
443
444
445

						/* set as in for next Perm */
						pairs[pidx].in_node = res1;
					}

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

					arch_set_irn_register(res2, cycle.elems[i + 1]);
					arch_set_irn_register(res1, cycle.elems[i]);

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

Matthias Braun's avatar
Matthias Braun committed
448
					DB((dbg, LEVEL_1, "replacing %+F with %+F, placed new node after %+F\n", irn, cpyxchg, sched_point));
449
450
451
452
453
454

					/* set the new scheduling point */
					sched_point = res1;
				} else {
					ir_node *cpyxchg;

Matthias Braun's avatar
Matthias Braun committed
455
					DB((dbg, LEVEL_1, "%+F creating copy node (%+F, %s) -> (%+F, %s)\n",
456
457
								irn, arg1, cycle.elems[i]->name, res2, cycle.elems[i + 1]->name));

458
					cpyxchg = be_new_Copy(reg_class, block, arg1);
459
460
461
462
463
464
					arch_set_irn_register(cpyxchg, cycle.elems[i + 1]);

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

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

					/* set the new scheduling point */
					sched_point = cpyxchg;
Christian Würdig's avatar
Christian Würdig committed
469
				}
Christian Würdig's avatar
Christian Würdig committed
470
			}
Christian Würdig's avatar
Christian Würdig committed
471
		}
472

473
		free((void*)cycle.elems);
474
475
476
	}

	/* remove the perm from schedule */
477
	if (!keep_perm) {
478
		sched_remove(irn);
479
		kill_node(irn);
480
	}
481
482
}

483
484


485
486
static int has_irn_users(const ir_node *irn)
{
Michael Beck's avatar
Michael Beck committed
487
	return get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL) != 0;
Christian Würdig's avatar
Christian Würdig committed
488
489
}

490
491
492
static ir_node *find_copy(ir_node *irn, ir_node *op)
{
	ir_node *cur_node;
Christian Würdig's avatar
Christian Würdig committed
493

494
495
496
497
	for (cur_node = irn;;) {
		cur_node = sched_prev(cur_node);
		if (! be_is_Copy(cur_node))
			return NULL;
498
		if (be_get_Copy_op(cur_node) == op && arch_irn_is(cur_node, dont_spill))
Christian Würdig's avatar
Christian Würdig committed
499
500
501
502
			return cur_node;
	}
}

503
504
static void gen_assure_different_pattern(ir_node *irn, ir_node *other_different, constraint_env_t *env)
{
505
506
507
508
	ir_nodemap_t                *op_set;
	ir_node                     *block;
	const arch_register_class_t *cls;
	ir_node                     *keep, *cpy;
509
	op_copy_assoc_t             *entry;
Christian Würdig's avatar
Christian Würdig committed
510

511
	if (arch_irn_is_ignore(other_different) ||
512
			!mode_is_datab(get_irn_mode(other_different))) {
Matthias Braun's avatar
Matthias Braun committed
513
		DB((dbg_constr, 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
		return;
	}

517
518
	op_set = &env->op_set;
	block  = get_nodes_block(irn);
519
	cls    = arch_get_irn_reg_class_out(other_different);
520

Christian Würdig's avatar
Christian Würdig committed
521
522
523
524
525
	/* 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         */

Michael Beck's avatar
Michael Beck committed
526
	/* check if already exists such a copy in the schedule immediately before */
527
	cpy = find_copy(skip_Proj(irn), other_different);
Christian Würdig's avatar
Christian Würdig committed
528
	if (! cpy) {
529
		cpy = be_new_Copy(cls, block, other_different);
530
		arch_irn_set_flags(cpy, arch_irn_flags_dont_spill);
Matthias Braun's avatar
Matthias Braun committed
531
		DB((dbg_constr, LEVEL_1, "created non-spillable %+F for value %+F\n", cpy, other_different));
532
	} else {
Matthias Braun's avatar
Matthias Braun committed
533
		DB((dbg_constr, LEVEL_1, "using already existing %+F for value %+F\n", cpy, other_different));
Christian Würdig's avatar
Christian Würdig committed
534
	}
Christian Würdig's avatar
Christian Würdig committed
535
536
537

	/* Add the Keep resp. CopyKeep and reroute the users */
	/* of the other_different irn in case of CopyKeep.   */
Michael Beck's avatar
Michael Beck committed
538
	if (has_irn_users(other_different)) {
539
		keep = be_new_CopyKeep_single(cls, block, cpy, irn, get_irn_mode(other_different));
540
		be_node_set_reg_class_in(keep, 1, cls);
541
542
543
544
545
	} else {
		ir_node *in[2];

		in[0] = irn;
		in[1] = cpy;
546
		keep = be_new_Keep(block, 2, in);
Michael Beck's avatar
Michael Beck committed
547
	}
Christian Würdig's avatar
Christian Würdig committed
548

Matthias Braun's avatar
Matthias Braun committed
549
	DB((dbg_constr, LEVEL_1, "created %+F(%+F, %+F)\n\n", keep, irn, cpy));
Christian Würdig's avatar
Christian Würdig committed
550

551
552
	/* insert copy and keep into schedule */
	assert(sched_is_scheduled(irn) && "need schedule to assure constraints");
Christian Würdig's avatar
Christian Würdig committed
553
	if (! sched_is_scheduled(cpy))
554
		sched_add_before(skip_Proj(irn), cpy);
555
	sched_add_after(skip_Proj(irn), keep);
556

557
	/* insert the other different and it's copies into the map */
558
	entry = (op_copy_assoc_t*)ir_nodemap_get(op_set, other_different);
559
	if (! entry) {
560
		entry      = OALLOC(&env->obst, op_copy_assoc_t);
561
		entry->cls = cls;
562
		ir_nodeset_init(&entry->copies);
563
564

		ir_nodemap_insert(op_set, other_different, entry);
565
566
567
	}

	/* insert copy */
568
	ir_nodeset_insert(&entry->copies, cpy);
569
570

	/* insert keep in case of CopyKeep */
571
	if (be_is_CopyKeep(keep))
572
		ir_nodeset_insert(&entry->copies, keep);
Christian Würdig's avatar
Christian Würdig committed
573
574
}

575
/**
576
577
 * Checks if node has a must_be_different constraint in output and adds a Keep
 * then to assure the constraint.
578
579
580
581
 *
 * @param irn          the node to check
 * @param skipped_irn  if irn is a Proj node, its predecessor, else irn
 * @param env          the constraint environment
582
 */
583
584
static void assure_different_constraints(ir_node *irn, ir_node *skipped_irn, constraint_env_t *env)
{
585
	const arch_register_req_t *req = arch_get_register_req_out(irn);
586

587
	if (arch_register_req_is(req, must_be_different)) {
588
589
590
		const unsigned other = req->other_different;
		int i;

Michael Beck's avatar
Michael Beck committed
591
592
593
594
595
596
597
598
		if (arch_register_req_is(req, should_be_same)) {
			const unsigned same = req->other_same;

			if (is_po2(other) && is_po2(same)) {
				int idx_other = ntz(other);
				int idx_same  = ntz(same);

				/*
599
				 * We can safely ignore a should_be_same x must_be_different y
Michael Beck's avatar
Michael Beck committed
600
				 * IFF both inputs are equal!
Michael Beck's avatar
Michael Beck committed
601
				 */
Christoph Mallon's avatar
Christoph Mallon committed
602
				if (get_irn_n(skipped_irn, idx_other) == get_irn_n(skipped_irn, idx_same)) {
Michael Beck's avatar
Michael Beck committed
603
604
605
606
					return;
				}
			}
		}
607
608
		for (i = 0; 1U << i <= other; ++i) {
			if (other & (1U << i)) {
Christoph Mallon's avatar
Christoph Mallon committed
609
				ir_node *different_from = get_irn_n(skipped_irn, i);
610
611
				gen_assure_different_pattern(irn, different_from, env);
			}
Christian Würdig's avatar
Christian Würdig committed
612
		}
613
614
615
616
	}
}

/**
617
 * Calls the functions to assure register constraints.
618
 *
619
 * @param block    The block to be checked
620
621
 * @param walk_env The walker environment
 */
622
623
static void assure_constraints_walker(ir_node *block, void *walk_env)
{
624
	ir_node *irn;
625
	constraint_env_t *env = (constraint_env_t*)walk_env;
626
627
628
629
630
631

	sched_foreach_reverse(block, irn) {
		ir_mode *mode = get_irn_mode(irn);

		if (mode == mode_T) {
			const ir_edge_t *edge;
632

633
634
635
636
637
			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);

				mode = get_irn_mode(proj);
				if (mode_is_datab(mode))
638
					assure_different_constraints(proj, irn, env);
639
640
			}
		} else if (mode_is_datab(mode)) {
641
			assure_different_constraints(irn, irn, env);
642
643
		}
	}
644
645
}

Christian Würdig's avatar
Christian Würdig committed
646
647
648
649
/**
 * Melt all copykeeps pointing to the same node
 * (or Projs of the same node), copying the same operand.
 */
650
651
static void melt_copykeeps(constraint_env_t *cenv)
{
652
653
	ir_nodemap_iterator_t map_iter;
	ir_nodemap_entry_t    map_entry;
Christian Würdig's avatar
Christian Würdig committed
654
655

	/* for all */
656
	foreach_ir_nodemap(&cenv->op_set, map_entry, map_iter) {
657
		op_copy_assoc_t *entry = (op_copy_assoc_t*)map_entry.data;
Christian Würdig's avatar
Christian Würdig committed
658
659
660
		int     idx, num_ck;
		ir_node *cp;
		struct obstack obst;
661
		ir_nodeset_iterator_t iter;
Christian Würdig's avatar
Christian Würdig committed
662
		ir_node **ck_arr, **melt_arr;
663

Christian Würdig's avatar
Christian Würdig committed
664
665
666
667
		obstack_init(&obst);

		/* collect all copykeeps */
		num_ck = idx = 0;
668
		foreach_ir_nodeset(&entry->copies, cp, iter) {
Christian Würdig's avatar
Christian Würdig committed
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
			if (be_is_CopyKeep(cp)) {
				obstack_grow(&obst, &cp, sizeof(cp));
				++num_ck;
			}
#ifdef KEEP_ALIVE_COPYKEEP_HACK
			else {
				set_irn_mode(cp, mode_ANY);
				keep_alive(cp);
			}
#endif /* KEEP_ALIVE_COPYKEEP_HACK */
		}

		/* compare each copykeep with all other copykeeps */
		ck_arr = (ir_node **)obstack_finish(&obst);
		for (idx = 0; idx < num_ck; ++idx) {
			ir_node *ref, *ref_mode_T;

			if (ck_arr[idx]) {
				int j, n_melt;
				ir_node **new_ck_in;
				ir_node *new_ck;
				ir_node *sched_pt = NULL;

				n_melt     = 1;
				ref        = ck_arr[idx];
				ref_mode_T = skip_Proj(get_irn_n(ref, 1));
				obstack_grow(&obst, &ref, sizeof(ref));

Matthias Braun's avatar
Matthias Braun committed
697
				DB((dbg_constr, LEVEL_1, "Trying to melt %+F:\n", ref));
Christian Würdig's avatar
Christian Würdig committed
698
699
700
701
702
703
704

				/* check for copykeeps pointing to the same mode_T node as the reference copykeep */
				for (j = 0; j < num_ck; ++j) {
					ir_node *cur_ck = ck_arr[j];

					if (j != idx && cur_ck && skip_Proj(get_irn_n(cur_ck, 1)) == ref_mode_T) {
						obstack_grow(&obst, &cur_ck, sizeof(cur_ck));
705
						ir_nodeset_remove(&entry->copies, cur_ck);
Matthias Braun's avatar
Matthias Braun committed
706
						DB((dbg_constr, LEVEL_1, "\t%+F\n", cur_ck));
Christian Würdig's avatar
Christian Würdig committed
707
708
709
710
711
712
713
714
715
						ck_arr[j] = NULL;
						++n_melt;
						sched_remove(cur_ck);
					}
				}
				ck_arr[idx] = NULL;

				/* check, if we found some candidates for melting */
				if (n_melt == 1) {
Matthias Braun's avatar
Matthias Braun committed
716
					DB((dbg_constr, LEVEL_1, "\tno candidate found\n"));
Christian Würdig's avatar
Christian Würdig committed
717
718
719
					continue;
				}

720
				ir_nodeset_remove(&entry->copies, ref);
Christian Würdig's avatar
Christian Würdig committed
721
722
723
724
725
726
727
728
729
730
731
				sched_remove(ref);

				melt_arr = (ir_node **)obstack_finish(&obst);
				/* melt all found copykeeps */
				NEW_ARR_A(ir_node *, new_ck_in, n_melt);
				for (j = 0; j < n_melt; ++j) {
					new_ck_in[j] = get_irn_n(melt_arr[j], 1);

					/* now, we can kill the melted keep, except the */
					/* ref one, we still need some information      */
					if (melt_arr[j] != ref)
732
						kill_node(melt_arr[j]);
Christian Würdig's avatar
Christian Würdig committed
733
734
735
				}

#ifdef KEEP_ALIVE_COPYKEEP_HACK
736
				new_ck = be_new_CopyKeep(entry->cls, get_nodes_block(ref), be_get_CopyKeep_op(ref), n_melt, new_ck_in, mode_ANY);
Christian Würdig's avatar
Christian Würdig committed
737
738
				keep_alive(new_ck);
#else
739
				new_ck = be_new_CopyKeep(entry->cls, get_nodes_block(ref), be_get_CopyKeep_op(ref), n_melt, new_ck_in, get_irn_mode(ref));
Christian Würdig's avatar
Christian Würdig committed
740
741
#endif /* KEEP_ALIVE_COPYKEEP_HACK */

742
				/* set register class for all kept inputs */
Christian Würdig's avatar
Christian Würdig committed
743
				for (j = 1; j <= n_melt; ++j)
744
					be_node_set_reg_class_in(new_ck, j, entry->cls);
Christian Würdig's avatar
Christian Würdig committed
745

746
				ir_nodeset_insert(&entry->copies, new_ck);
Christian Würdig's avatar
Christian Würdig committed
747
748

				/* find scheduling point */
749
				sched_pt = ref_mode_T;
750
				do {
751
					/* just walk along the schedule until a non-Keep/CopyKeep node is found */
752
					sched_pt = sched_next(sched_pt);
753
				} while (be_is_Keep(sched_pt) || be_is_CopyKeep(sched_pt));
Christian Würdig's avatar
Christian Würdig committed
754
755

				sched_add_before(sched_pt, new_ck);
Matthias Braun's avatar
Matthias Braun committed
756
				DB((dbg_constr, LEVEL_1, "created %+F, scheduled before %+F\n", new_ck, sched_pt));
Christian Würdig's avatar
Christian Würdig committed
757
758

				/* finally: kill the reference copykeep */
759
				kill_node(ref);
Christian Würdig's avatar
Christian Würdig committed
760
761
762
763
764
765
			}
		}

		obstack_free(&obst, NULL);
	}
}
766

767
void assure_constraints(ir_graph *irg)
768
{
769
770
771
	constraint_env_t      cenv;
	ir_nodemap_iterator_t map_iter;
	ir_nodemap_entry_t    map_entry;
772

773
774
	FIRM_DBG_REGISTER(dbg_constr, "firm.be.lower.constr");

775
	cenv.irg = irg;
776
	ir_nodemap_init(&cenv.op_set);
777
778
	obstack_init(&cenv.obst);

779
	irg_block_walk_graph(irg, NULL, assure_constraints_walker, &cenv);
780

Christian Würdig's avatar
Christian Würdig committed
781
782
783
784
785
	/* melt copykeeps, pointing to projs of */
	/* the same mode_T node and keeping the */
	/* same operand                         */
	melt_copykeeps(&cenv);

786
	/* for all */
787
	foreach_ir_nodemap(&cenv.op_set, map_entry, map_iter) {
788
		op_copy_assoc_t          *entry = (op_copy_assoc_t*)map_entry.data;
789
		size_t                    n     = ir_nodeset_size(&entry->copies);
790
791
792
		ir_node                 **nodes = ALLOCAN(ir_node*, n);
		ir_node                  *cp;
		ir_nodeset_iterator_t     iter;
793
		be_ssa_construction_env_t senv;
794
795

		/* put the node in an array */
796
		DBG((dbg_constr, LEVEL_1, "introduce copies for %+F ", map_entry.node));
797
798

		/* collect all copies */
799
800
		n = 0;
		foreach_ir_nodeset(&entry->copies, cp, iter) {
801
			nodes[n++] = cp;
802
			DB((dbg_constr, LEVEL_1, ", %+F ", cp));
803
804
		}

805
		DB((dbg_constr, LEVEL_1, "\n"));
806
807

		/* introduce the copies for the operand and it's copies */
808
		be_ssa_construction_init(&senv, irg);
809
		be_ssa_construction_add_copy(&senv, map_entry.node);
810
		be_ssa_construction_add_copies(&senv, nodes, n);
811
		be_ssa_construction_fix_users(&senv, map_entry.node);
812
		be_ssa_construction_destroy(&senv);
813
814
815

		/* Could be that not all CopyKeeps are really needed, */
		/* so we transform unnecessary ones into Keeps.       */
816
		foreach_ir_nodeset(&entry->copies, cp, iter) {
817
			if (be_is_CopyKeep(cp) && get_irn_n_edges(cp) < 1) {
818
819
				int      n   = get_irn_arity(cp);
				ir_node *keep;
820

821
				keep = be_new_Keep(get_nodes_block(cp), n, get_irn_in(cp) + 1);
822
823
824
				sched_add_before(cp, keep);

				/* Set all ins (including the block) of the CopyKeep BAD to keep the verifier happy. */
825
				sched_remove(cp);
826
				kill_node(cp);
827
828
829
			}
		}

830
		ir_nodeset_destroy(&entry->copies);
831
832
	}

833
	ir_nodemap_destroy(&cenv.op_set);
834
	obstack_free(&cenv.obst, NULL);
835
	be_liveness_invalidate(be_get_irg_liveness(irg));
836
837
838
}


839
840
841
842
843
844
/**
 * Push nodes that do not need to be permed through the Perm.
 * This is commonly a reload cascade at block ends.
 * @note This routine needs interference.
 * @note Probably, we can implement it a little more efficient.
 *       Especially searching the frontier lazily might be better.
Michael Beck's avatar
Michael Beck committed
845
846
847
848
 *
 * @param perm The perm
 * @param env  The lowerer environment
 *
849
850
851
 * @return     1, if there is something left to perm over.
 *             0, if removed the complete perm.
 */
852
static int push_through_perm(ir_node *perm)
853
854
855
{
	ir_graph *irg     = get_irn_irg(perm);
	ir_node *bl       = get_nodes_block(perm);
Michael Beck's avatar
Michael Beck committed
856
	ir_node *node;
857
858
859
860
861
862
	int  arity        = get_irn_arity(perm);
	int *map;
	int *proj_map;
	bitset_t *moved   = bitset_alloca(arity);
	int n_moved;
	int new_size;
Michael Beck's avatar
Michael Beck committed
863
	ir_node *frontier = bl;
864
	ir_node *irn;
865
	int i, n;
866

Michael Beck's avatar
Michael Beck committed
867
	/* get some Proj and find out the register class of that Proj. */
868
869
870
	const ir_edge_t             *edge     = get_irn_out_edge_first_kind(perm, EDGE_KIND_NORMAL);
	ir_node                     *one_proj = get_edge_src_irn(edge);
	const arch_register_class_t *cls      = arch_get_irn_reg_class_out(one_proj);
Michael Beck's avatar
Michael Beck committed
871
	assert(is_Proj(one_proj));
872

Matthias Braun's avatar
Matthias Braun committed
873
	DB((dbg_permmove, LEVEL_1, "perm move %+F irg %+F\n", perm, irg));
874

Michael Beck's avatar
Michael Beck committed
875
	/* Find the point in the schedule after which the
876
	 * potentially movable nodes must be defined.
Michael Beck's avatar
Michael Beck committed
877
878
879
880
881
882
	 * A Perm will only be pushed up to first instruction
	 * which lets an operand of itself die.
	 * If we would allow to move the Perm above this instruction,
	 * the former dead operand would be live now at the point of
	 * the Perm, increasing the register pressure by one.
	 */
Michael Beck's avatar
Michael Beck committed
883
	sched_foreach_reverse_from(sched_prev(perm), irn) {
Michael Beck's avatar
Michael Beck committed
884
		for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
885
			ir_node *op = get_irn_n(irn, i);
886
			be_lv_t *lv = be_get_irg_liveness(irg);
887
			if (arch_irn_consider_in_reg_alloc(cls, op) &&
888
			    !be_values_interfere(lv, op, one_proj)) {
889
				frontier = irn;
890
891
892
893
894
895
				goto found_front;
			}
		}
	}
found_front:

Matthias Braun's avatar
Matthias Braun committed
896
	DB((dbg_permmove, LEVEL_2, "\tfrontier: %+F\n", frontier));
897

Michael Beck's avatar
Michael Beck committed
898
	node = sched_prev(perm);
899
	n_moved = 0;
Michael Beck's avatar
Michael Beck committed
900
	while (!sched_is_begin(node)) {
901
902
903
		const arch_register_req_t *req;
		int                        input = -1;
		ir_node                   *proj;
904

Michael Beck's avatar
Michael Beck committed
905
		/* search if node is a INPUT of Perm */
906
907
908
909
		foreach_out_edge(perm, edge) {
			ir_node *out = get_edge_src_irn(edge);
			int      pn  = get_Proj_proj(out);
			ir_node *in  = get_irn_n(perm, pn);
Michael Beck's avatar
Michael Beck committed
910
			if (node == in) {
911
912
913
				proj  = out;
				input = pn;
				break;
914
			}
915
916
		}
		/* it wasn't an input to the perm, we can't do anything more */
Michael Beck's avatar
Michael Beck committed
917
		if (input < 0)
918
			break;
Michael Beck's avatar
Michael Beck committed
919
		if (!sched_comes_after(frontier, node))
920
			break;
921
		if (arch_irn_is(node, modify_flags))
922
			break;
923
		req = arch_get_register_req_out(node);
Michael Beck's avatar
Michael Beck committed
924
		if (req->type != arch_register_req_type_normal)
925
			break;
Michael Beck's avatar
Michael Beck committed
926
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
927
			ir_node *opop = get_irn_n(node, i);
928
			if (arch_irn_consider_in_reg_alloc(cls, opop)) {
929
				break;
930
931
			}
		}
Michael Beck's avatar
Michael Beck committed
932
		if (i >= 0)
933
			break;
934

Michael Beck's avatar
Michael Beck committed
935
		DBG((dbg_permmove, LEVEL_2, "\tmoving %+F after %+F, killing %+F\n", node, perm, proj));
936

937
938
939
		/* move the movable node in front of the Perm */
		sched_remove(node);
		sched_add_after(perm, node);
940

941
		/* give it the proj's register */
942
		arch_set_irn_register(node, arch_get_irn_register(proj));
943

944
		/* reroute all users of the proj to the moved node. */
945
		exchange(pr