belower.c 30.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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
63
typedef struct {
	be_irg_t       *birg;
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
	be_irg_t         *birg;
	unsigned          do_copy : 1;
72
73
} lower_env_t;

Michael Beck's avatar
Michael Beck committed
74
/** Holds a Perm register pair. */
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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;

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

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
static ir_node *get_node_for_in_register(reg_pair_t *pairs, int n, const arch_register_t *reg) {
124
125
	int i;

126
127
128
129
	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
130
	}
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

	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
 */
static ir_node *get_node_for_out_register(reg_pair_t *pairs, int n, const arch_register_t *reg) {
	int i;

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

	return NULL;
}

Christian Würdig's avatar
Christian Würdig committed
157
/**
158
 * Gets the index in the register pair array where the in register
Christian Würdig's avatar
Christian Würdig committed
159
160
161
162
163
 * 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
164
 *
Christian Würdig's avatar
Christian Würdig committed
165
166
 * @return The corresponding index in pairs or -1 if not found
 */
167
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
168
169
	int i;

170
171
172
173
	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
174
	}
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
	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
 */
static int get_pairidx_for_out_regidx(reg_pair_t *pairs, int n, unsigned reg_idx) {
	int i;
Christian Würdig's avatar
Christian Würdig committed
190

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

199
/**
200
201
 * Gets an array of register pairs and tries to identify a cycle or chain
 * starting at position start.
202
 *
Michael Beck's avatar
Michael Beck committed
203
204
205
206
207
 * @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
 *
208
209
 * @return The cycle or chain
 */
210
211
212
213
static void get_perm_cycle(perm_cycle_t *const cycle,
                           reg_pair_t   *const pairs,
                           int           const n,
                           int                 start)
214
215
216
{
	int         head         = pairs[start].in_reg->index;
	int         cur_idx      = pairs[start].out_reg->index;
217
	int   const n_pairs_todo = get_n_unchecked_pairs(pairs, n);
218
219
	perm_type_t cycle_tp     = PERM_CYCLE;
	int         idx;
Christian Würdig's avatar
Christian Würdig committed
220
221

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

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

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

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

		if (cur_pair_idx < 0)
			break;

		cur_idx = pairs[cur_pair_idx].out_reg->index;
253
254
255

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

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

268
		cur_pair_idx = get_pairidx_for_in_regidx(pairs, n, cycle->elems[idx]->index);
Christian Würdig's avatar
Christian Würdig committed
269
270
271
		if (cur_pair_idx >= 0)
			pairs[cur_pair_idx].checked = 1;

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

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

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

308
	assert(arity == get_irn_n_edges(irn) && "perm's in and out numbers different");
309
310

	/* build the list of register pairs (in, out) */
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
	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;
		}
326

327
		pair           = &pairs[n++];
328
		pair->in_node  = in;
329
		pair->in_reg   = in_reg;
330
		pair->out_node = out;
331
		pair->out_reg  = out_reg;
332
		pair->checked  = 0;
333
334
	}

335
	DBG((dbg, LEVEL_1, "%+F has %d unresolved constraints\n", irn, n));
336
337

	/* Set do_copy to 0 if it's on but we have no free register */
338
	/* TODO check for free register */
339
340
341
342
343
	if (do_copy) {
		do_copy = 0;
	}

	/* check for cycles and chains */
344
	while (get_n_unchecked_pairs(pairs, n) > 0) {
345
346
		perm_cycle_t cycle;
		int          j;
347
348

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

352
353
354
		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
355
		}
356
		DB((dbg, LEVEL_1, "\n"));
Christian Würdig's avatar
Christian Würdig committed
357

358
		if (cycle.type == PERM_CYCLE && arity == 2) {
359
360
361
			/* 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 */
362
			keep_perm = 1;
363
364
365
366
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
		} 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));

420
					cpyxchg = be_new_Perm(reg_class, block, 2, in);
421
422
423
424
425
426

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

						/* create intermediate proj */
427
						res1 = new_r_Proj(block, cpyxchg, get_irn_mode(res1), 0);
428
429
430
431
432
433
434
435
436
437
438
439
440
441

						/* 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) */
442
					sched_add_after(skip_Proj(sched_point), cpyxchg);
443

Matthias Braun's avatar
Matthias Braun committed
444
					DB((dbg, LEVEL_1, "replacing %+F with %+F, placed new node after %+F\n", irn, cpyxchg, sched_point));
445
446
447
448
449
450

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

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

454
					cpyxchg = be_new_Copy(reg_class, block, arg1);
455
456
457
458
459
460
					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) */
461
					sched_add_after(skip_Proj(sched_point), cpyxchg);
462
463
464

					/* set the new scheduling point */
					sched_point = cpyxchg;
Christian Würdig's avatar
Christian Würdig committed
465
				}
Christian Würdig's avatar
Christian Würdig committed
466
			}
Christian Würdig's avatar
Christian Würdig committed
467
		}
468

469
		free((void*)cycle.elems);
470
471
472
	}

	/* remove the perm from schedule */
473
	if (!keep_perm) {
474
		sched_remove(irn);
475
		kill_node(irn);
476
	}
477
478
}

479
480


Michael Beck's avatar
Michael Beck committed
481
482
static int has_irn_users(const ir_node *irn) {
	return get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL) != 0;
Christian Würdig's avatar
Christian Würdig committed
483
484
}

485
486
487
static ir_node *find_copy(ir_node *irn, ir_node *op)
{
	ir_node *cur_node;
Christian Würdig's avatar
Christian Würdig committed
488

489
490
491
492
	for (cur_node = irn;;) {
		cur_node = sched_prev(cur_node);
		if (! be_is_Copy(cur_node))
			return NULL;
493
		if (be_get_Copy_op(cur_node) == op && arch_irn_is(cur_node, dont_spill))
Christian Würdig's avatar
Christian Würdig committed
494
495
496
497
			return cur_node;
	}
}

498
static void gen_assure_different_pattern(ir_node *irn, ir_node *other_different, constraint_env_t *env) {
499
500
501
502
503
	ir_graph                    *irg;
	ir_nodemap_t                *op_set;
	ir_node                     *block;
	const arch_register_class_t *cls;
	ir_node                     *keep, *cpy;
504
	op_copy_assoc_t             *entry;
Christian Würdig's avatar
Christian Würdig committed
505

506
	if (arch_irn_is_ignore(other_different) ||
507
			!mode_is_datab(get_irn_mode(other_different))) {
Matthias Braun's avatar
Matthias Braun committed
508
		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
509
510
511
		return;
	}

512
513
514
	irg    = be_get_birg_irg(env->birg);
	op_set = &env->op_set;
	block  = get_nodes_block(irn);
515
	cls    = arch_get_irn_reg_class_out(other_different);
516

Christian Würdig's avatar
Christian Würdig committed
517
518
519
520
521
	/* 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
522
	/* check if already exists such a copy in the schedule immediately before */
523
	cpy = find_copy(skip_Proj(irn), other_different);
Christian Würdig's avatar
Christian Würdig committed
524
	if (! cpy) {
525
		cpy = be_new_Copy(cls, block, other_different);
526
		arch_irn_set_flags(cpy, arch_irn_flags_dont_spill);
Matthias Braun's avatar
Matthias Braun committed
527
		DB((dbg_constr, LEVEL_1, "created non-spillable %+F for value %+F\n", cpy, other_different));
528
	} else {
Matthias Braun's avatar
Matthias Braun committed
529
		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
530
	}
Christian Würdig's avatar
Christian Würdig committed
531
532
533

	/* 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
534
	if (has_irn_users(other_different)) {
535
		keep = be_new_CopyKeep_single(cls, block, cpy, irn, get_irn_mode(other_different));
536
		be_node_set_reg_class_in(keep, 1, cls);
537
538
539
540
541
	} else {
		ir_node *in[2];

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

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

547
548
	/* 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
549
	if (! sched_is_scheduled(cpy))
550
		sched_add_before(skip_Proj(irn), cpy);
551
	sched_add_after(skip_Proj(irn), keep);
552

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

		ir_nodemap_insert(op_set, other_different, entry);
561
562
563
	}

	/* insert copy */
564
	ir_nodeset_insert(&entry->copies, cpy);
565
566

	/* insert keep in case of CopyKeep */
567
	if (be_is_CopyKeep(keep))
568
		ir_nodeset_insert(&entry->copies, keep);
Christian Würdig's avatar
Christian Würdig committed
569
570
}

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

582
	if (arch_register_req_is(req, must_be_different)) {
583
584
585
		const unsigned other = req->other_different;
		int i;

Michael Beck's avatar
Michael Beck committed
586
587
588
589
590
591
592
593
		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);

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

/**
612
 * Calls the functions to assure register constraints.
613
 *
614
 * @param block    The block to be checked
615
616
 * @param walk_env The walker environment
 */
617
618
619
620
621
622
623
624
static void assure_constraints_walker(ir_node *block, void *walk_env) {
	ir_node *irn;

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

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

626
627
628
629
630
631
632
633
634
635
636
			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);

				mode = get_irn_mode(proj);
				if (mode_is_datab(mode))
					assure_different_constraints(proj, irn, walk_env);
			}
		} else if (mode_is_datab(mode)) {
			assure_different_constraints(irn, irn, walk_env);
		}
	}
637
638
}

Christian Würdig's avatar
Christian Würdig committed
639
640
641
642
643
/**
 * Melt all copykeeps pointing to the same node
 * (or Projs of the same node), copying the same operand.
 */
static void melt_copykeeps(constraint_env_t *cenv) {
644
645
	ir_nodemap_iterator_t map_iter;
	ir_nodemap_entry_t    map_entry;
Christian Würdig's avatar
Christian Würdig committed
646
647

	/* for all */
648
649
	foreach_ir_nodemap(&cenv->op_set, map_entry, map_iter) {
		op_copy_assoc_t *entry = map_entry.data;
Christian Würdig's avatar
Christian Würdig committed
650
651
652
		int     idx, num_ck;
		ir_node *cp;
		struct obstack obst;
653
		ir_nodeset_iterator_t iter;
Christian Würdig's avatar
Christian Würdig committed
654
		ir_node **ck_arr, **melt_arr;
655

Christian Würdig's avatar
Christian Würdig committed
656
657
658
659
		obstack_init(&obst);

		/* collect all copykeeps */
		num_ck = idx = 0;
660
		foreach_ir_nodeset(&entry->copies, cp, iter) {
Christian Würdig's avatar
Christian Würdig committed
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
			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
689
				DB((dbg_constr, LEVEL_1, "Trying to melt %+F:\n", ref));
Christian Würdig's avatar
Christian Würdig committed
690
691
692
693
694
695
696

				/* 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));
697
						ir_nodeset_remove(&entry->copies, cur_ck);
Matthias Braun's avatar
Matthias Braun committed
698
						DB((dbg_constr, LEVEL_1, "\t%+F\n", cur_ck));
Christian Würdig's avatar
Christian Würdig committed
699
700
701
702
703
704
705
706
707
						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
708
					DB((dbg_constr, LEVEL_1, "\tno candidate found\n"));
Christian Würdig's avatar
Christian Würdig committed
709
710
711
					continue;
				}

712
				ir_nodeset_remove(&entry->copies, ref);
Christian Würdig's avatar
Christian Würdig committed
713
714
715
716
717
718
719
720
721
722
723
				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)
724
						kill_node(melt_arr[j]);
Christian Würdig's avatar
Christian Würdig committed
725
726
727
				}

#ifdef KEEP_ALIVE_COPYKEEP_HACK
728
				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
729
730
				keep_alive(new_ck);
#else
731
				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
732
733
#endif /* KEEP_ALIVE_COPYKEEP_HACK */

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

738
				ir_nodeset_insert(&entry->copies, new_ck);
Christian Würdig's avatar
Christian Würdig committed
739
740

				/* find scheduling point */
741
				sched_pt = ref_mode_T;
742
				do {
743
					/* just walk along the schedule until a non-Keep/CopyKeep node is found */
744
					sched_pt = sched_next(sched_pt);
745
				} while (be_is_Keep(sched_pt) || be_is_CopyKeep(sched_pt));
Christian Würdig's avatar
Christian Würdig committed
746
747

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

				/* finally: kill the reference copykeep */
751
				kill_node(ref);
Christian Würdig's avatar
Christian Würdig committed
752
753
754
755
756
757
			}
		}

		obstack_free(&obst, NULL);
	}
}
758

759
760
761
762
763
764
/**
 * Walks over all nodes to assure register constraints.
 *
 * @param birg  The birg structure containing the irg
 */
void assure_constraints(be_irg_t *birg) {
765
766
767
768
	ir_graph              *irg = be_get_birg_irg(birg);
	constraint_env_t      cenv;
	ir_nodemap_iterator_t map_iter;
	ir_nodemap_entry_t    map_entry;
769

770
771
772
	FIRM_DBG_REGISTER(dbg_constr, "firm.be.lower.constr");

	cenv.birg = birg;
773
	ir_nodemap_init(&cenv.op_set);
774
775
	obstack_init(&cenv.obst);

776
	irg_block_walk_graph(irg, NULL, assure_constraints_walker, &cenv);
777

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

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

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

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

802
		DB((dbg_constr, LEVEL_1, "\n"));
803
804

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

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

818
				keep = be_new_Keep(get_nodes_block(cp), n, get_irn_in(cp) + 1);
819
820
821
				sched_add_before(cp, keep);

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

827
		ir_nodeset_destroy(&entry->copies);
828
829
	}

830
	ir_nodemap_destroy(&cenv.op_set);
831
	obstack_free(&cenv.obst, NULL);
Sebastian Hack's avatar
Sebastian Hack committed
832
	be_liveness_invalidate(be_get_birg_liveness(birg));
833
834
835
}


836
837
838
839
840
841
/**
 * 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
842
843
844
845
 *
 * @param perm The perm
 * @param env  The lowerer environment
 *
846
847
848
 * @return     1, if there is something left to perm over.
 *             0, if removed the complete perm.
 */
Michael Beck's avatar
Michael Beck committed
849
static int push_through_perm(ir_node *perm, lower_env_t *env)
850
851
852
{
	ir_graph *irg     = get_irn_irg(perm);
	ir_node *bl       = get_nodes_block(perm);
Michael Beck's avatar
Michael Beck committed
853
	ir_node *node;
854
855
856
857
858
859
	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
860
	ir_node *frontier = bl;
861
	ir_node *irn;
862
	int i, n;
863

Michael Beck's avatar
Michael Beck committed
864
	/* get some Proj and find out the register class of that Proj. */
865
866
867
	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
868
	assert(is_Proj(one_proj));
869

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

Michael Beck's avatar
Michael Beck committed
872
	/* Find the point in the schedule after which the
873
	 * potentially movable nodes must be defined.
Michael Beck's avatar
Michael Beck committed
874
875
876
877
878
879
	 * 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
880
	sched_foreach_reverse_from(sched_prev(perm), irn) {
Michael Beck's avatar
Michael Beck committed
881
		for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
882
			ir_node *op = get_irn_n(irn, i);
883
			if (arch_irn_consider_in_reg_alloc(cls, op) &&
884
			    !be_values_interfere(env->birg->lv, op, one_proj)) {
885
				frontier = irn;
886
887
888
889
890
891
				goto found_front;
			}
		}
	}
found_front:

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

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

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

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

933
934
935
		/* move the movable node in front of the Perm */
		sched_remove(node);
		sched_add_after(perm, node);
936

937
		/* give it the proj's register */
938
		arch_set_irn_register(node, arch_get_irn_register(proj));
939

940
941
		/* reroute all users of the proj to the moved node. */
		edges_reroute(proj, node, irg);
942

943
944
		/* and kill it */
		set_Proj_pred(proj, new_Bad());
945
		kill_node(proj);
946

947
948
		bitset_set(moved, input);
		n_moved++;
949

950
951
		node = sched_prev(node);
	}
952

953
954
955
	/* well, we could not push anything through the perm */
	if(n_moved == 0)
		return 1;
956

957
958
	new_size = arity - n_moved;
	if(new_size == 0) {
959
960
		sched_remove(perm);
		kill_node(perm);
961
		return 0;
962
963
	}

964
965
	map      = ALLOCAN(int, new_size);
	proj_map = ALLOCAN(int, arity);
966
967
	memset(proj_map, -1, sizeof(proj_map[0]));
	n   = 0;
Michael Beck's avatar
Michael Beck committed
968
969
	for (i = 0; i < arity; ++i) {
		if (bitset_is_set(moved, i))
970
971
972
973
974
975
976
977
978
979
980
981