bechordal_common.c 4.71 KB
Newer Older
Thomas Bersch's avatar
Thomas Bersch committed
1
/*
2
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
8
9
10
 */

/**
 * @file
 * @brief       Common functions for chordal register allocation.
 * @author      Sebastian Hack
 * @date        08.12.2004
Thomas Bersch's avatar
Thomas Bersch committed
11
 */
12
13
#include "bechordal_common.h"

Thomas Bersch's avatar
Thomas Bersch committed
14
15
16
17
18
#include "debug.h"

#include "iredges.h"
#include "bechordal.h"
#include "bechordal_t.h"
19
#include "beirg.h"
Thomas Bersch's avatar
Thomas Bersch committed
20
21
#include "beinsn_t.h"
#include "besched.h"
22
#include "beutil.h"
Matthias Braun's avatar
Matthias Braun committed
23
#include "statev_t.h"
Thomas Bersch's avatar
Thomas Bersch committed
24
25
26
#include "benode.h"
#include "bemodule.h"
#include "belive.h"
Matthias Braun's avatar
Matthias Braun committed
27
#include "belive.h"
Thomas Bersch's avatar
Thomas Bersch committed
28
29
30

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

31
static inline border_t *border_add(be_chordal_env_t *const env, struct list_head *const head, ir_node *const irn, unsigned const step, unsigned const is_def, unsigned const is_real)
Thomas Bersch's avatar
Thomas Bersch committed
32
{
33
34
	border_t *const b = OALLOC(&env->obst, border_t);
	b->is_def  = is_def;
Thomas Bersch's avatar
Thomas Bersch committed
35
	b->is_real = is_real;
36
37
	b->irn     = irn;
	b->step    = step;
Thomas Bersch's avatar
Thomas Bersch committed
38
39
40
41
42
43
	list_add_tail(&b->list, head);
	DBG((dbg, LEVEL_5, "\t\t%s adding %+F, step: %d\n", is_def ? "def" : "use", irn, step));

	return b;
}

44
void create_borders(ir_node *block, void *env_ptr)
Thomas Bersch's avatar
Thomas Bersch committed
45
46
47
{
/* Convenience macro for a def */
#define border_def(irn, step, real) \
48
	border_add(env, head, irn, step, 1, real)
Thomas Bersch's avatar
Thomas Bersch committed
49
50
51

/* Convenience macro for a use */
#define border_use(irn, step, real) \
52
	border_add(env, head, irn, step, 0, real)
Thomas Bersch's avatar
Thomas Bersch committed
53

54
	be_chordal_env_t *const env = (be_chordal_env_t*)env_ptr;
Thomas Bersch's avatar
Thomas Bersch committed
55
56
57
58
59

	unsigned step = 0;
	struct list_head *head;

	/* Set up the border list in the block info */
60
	head = OALLOC(&env->obst, struct list_head);
Thomas Bersch's avatar
Thomas Bersch committed
61
	INIT_LIST_HEAD(head);
62
	assert(pmap_get(struct list_head, env->border_heads, block) == NULL);
Thomas Bersch's avatar
Thomas Bersch committed
63
64
	pmap_insert(env->border_heads, block, head);

65
66
67
68
69
	ir_nodeset_t live;
	ir_nodeset_init(&live);

	be_lv_t *const lv = be_get_irg_liveness(env->irg);

Thomas Bersch's avatar
Thomas Bersch committed
70
71
72
73
	/*
	 * Make final uses of all values live out of the block.
	 * They are necessary to build up real intervals.
	 */
74
	be_lv_foreach_cls(lv, block, be_lv_state_end, env->cls, irn) {
75
76
		DB((dbg, LEVEL_3, "\tMaking live: %+F\n", irn));
		ir_nodeset_insert(&live, irn);
77
		border_use(irn, step, 0);
Thomas Bersch's avatar
Thomas Bersch committed
78
79
80
81
82
83
84
85
	}
	++step;

	/*
	 * Determine the last uses of a value inside the block, since they are
	 * relevant for the interval borders.
	 */
	sched_foreach_reverse(block, irn) {
86
		DB((dbg, LEVEL_1, "\tinsn: %+F\n", irn));
87

88
		be_foreach_definition(irn, env->cls, def, req,
Thomas Bersch's avatar
Thomas Bersch committed
89
90
91
92
			/*
			 * If the node defines some value, which can put into a
			 * register of the current class, make a border for it.
			 */
93
			ir_nodeset_remove(&live, def);
94
95
			border_def(def, step, 1);
		);
Thomas Bersch's avatar
Thomas Bersch committed
96

97
98
99
		/* If the node is no phi node we can examine the uses. */
		if (!is_Phi(irn)) {
			be_foreach_use(irn, env->cls, in_req_, op, op_req_,
yb9976's avatar
yb9976 committed
100
				DEBUG_ONLY(char msg = '-';)
101

102
103
				if (ir_nodeset_insert(&live, op)) {
					border_use(op, step, 1);
yb9976's avatar
yb9976 committed
104
					DEBUG_ONLY(msg = 'X';)
105
				}
106

yb9976's avatar
yb9976 committed
107
				DB((dbg, LEVEL_4, "\t\t%c pos: %d, use: %+F\n", msg, i_, op));
108
109
			);
		}
Thomas Bersch's avatar
Thomas Bersch committed
110
111
112
		++step;
	}

113
114
	/* Process live-ins last. In particular all Phis are handled before, so when
	 * iterating the borders the live-ins come before all Phis ("live-start"). */
115
	foreach_ir_nodeset(&live, irn, iter) {
116
117
		assert(be_is_live_in(lv, block, irn));
		border_def(irn, step, 0);
Thomas Bersch's avatar
Thomas Bersch committed
118
119
	}

120
	ir_nodeset_destroy(&live);
Thomas Bersch's avatar
Thomas Bersch committed
121
122
123
124
}

ir_node *pre_process_constraints(be_chordal_env_t *env, be_insn_t **the_insn)
{
125
	be_insn_t *insn = *the_insn;
Thomas Bersch's avatar
Thomas Bersch committed
126
127
128
129
130

	/*
	 * Make the Perm, recompute liveness and re-scan the insn since the
	 * in operands are now the Projs of the Perm.
	 */
131
132
	ir_node *const irn  = insn->irn;
	ir_node *const perm = insert_Perm_before(env->irg, env->cls, irn);
Thomas Bersch's avatar
Thomas Bersch committed
133

134
	/* Registers are propagated by insert_Perm_before(). Clean them here! */
Thomas Bersch's avatar
Thomas Bersch committed
135
136
137
138
139
140
141
142
	if (perm == NULL)
		return NULL;

	/*
	 * We also have to re-build the insn since the input operands are now the Projs of
	 * the Perm. Recomputing liveness is also a good idea if a Perm is inserted, since
	 * the live sets may change.
	 */
143
	obstack_free(&env->obst, insn);
144
	*the_insn = insn = be_scan_insn(env, irn);
Thomas Bersch's avatar
Thomas Bersch committed
145

146
147
	/* Copy the input constraints of the irn to the Perm as output
	 * constraints. Succeeding phases (coalescing) will need that. */
148
	foreach_irn_in(irn, i, proj) {
149
150
		/* Note that the predecessor is not necessarily a Proj of the Perm,
		 * since ignore-nodes are not Perm'ed. */
151
152
		if (!is_Proj(proj) || get_Proj_pred(proj) != perm)
			continue;
153
154
155
		/* FIXME: Only setting the constraints, when the register requirement is
		 * limited, is a hack.  It will break when multiple differently constrained
		 * inputs use the same value. */
156
157
158
		arch_register_req_t const *const req = arch_get_irn_register_req_in(irn, i);
		if (!arch_register_req_is(req, limited))
			continue;
Matthias Braun's avatar
Matthias Braun committed
159
		arch_set_irn_register_req_out(perm, get_Proj_num(proj), req);
Thomas Bersch's avatar
Thomas Bersch committed
160
161
162
163
164
	}

	return perm;
}

Matthias Braun's avatar
Matthias Braun committed
165
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal_common)
Thomas Bersch's avatar
Thomas Bersch committed
166
167
168
169
void be_init_chordal_common(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.chordal_common");
}