becopyheur3.c 5.27 KB
Newer Older
1
2
3
4
5
6
/**
 * More experiments on coalescing.
 * @author Sebastian Hack
 * @date   25.07.2006
 */
#ifdef HAVE_CONFIG_H
7
#include "config.h"
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#endif

#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>

#include <stdlib.h>
#include <limits.h>

#include "list.h"
#include "pdeq.h"
#include "bitset.h"

#include "debug.h"
#include "bitfiddle.h"
#include "bitset.h"
Matthias Braun's avatar
Matthias Braun committed
23
#include "raw_bitset.h"
24
25
26
27
28
29

#include "irgraph_t.h"
#include "irnode_t.h"
#include "irprintf.h"
#include "irtools.h"

30
#include "bemodule.h"
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "beabi.h"
#include "benode_t.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
#include "bejavacoal.h"

#include <stdlib.h>
#include <stdio.h>

#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_ALL    2 * DUMP_AFTER - 1

Matthias Braun's avatar
Matthias Braun committed
45
46
static unsigned dump_flags = 0;
static int      dbg_level  = 0;
47
48
49
50
51
52
53
54
55
56
57
58
59

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
	{ "after",   DUMP_AFTER  },
	{ "all",     DUMP_ALL    },
	{ NULL,      0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
60
	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud",                              &dump_var),
61
62
63
64
	LC_OPT_ENT_INT      ("dbg",  "debug level for the Java coalescer",          &dbg_level),
	{ NULL }
};

65
void be_init_copyheur3(void)
66
{
67
68
69
70
71
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
	lc_opt_entry_t *co3_grp = lc_opt_get_grp(chordal_grp, "co3");

72
73
74
	lc_opt_add_table(co3_grp, options);
}

75
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur3);
76

77
static void set_admissible_regs(be_java_coal_t *coal, copy_opt_t *co, ir_node *irn, int t_idx, int *col_map)
78
{
Matthias Braun's avatar
Matthias Braun committed
79
80
81
	const arch_register_req_t *req;

	req = arch_get_register_req(co->aenv, irn, BE_OUT_POS(0));
82

Sebastian Hack's avatar
Sebastian Hack committed
83
	// ir_printf("%+F\n", irn);
Matthias Braun's avatar
Matthias Braun committed
84
85
86
87
88
89
	if(arch_register_req_is(req, limited)) {
		unsigned i;
		unsigned n_regs = co->cls->n_regs;

		for(i = 0; i < n_regs; ++i) {
			if(!rbitset_is_set(req->limited, i) && col_map[i] >= 0) {
90
				be_java_coal_forbid_color(coal, t_idx, col_map[i]);
Sebastian Hack's avatar
Sebastian Hack committed
91
			}
Matthias Braun's avatar
Matthias Braun committed
92
		}
93
94
95
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
96
int co_solve_heuristic_java(copy_opt_t *co)
97
98
99
100
101
102
103
{
	be_ifg_t *ifg   = co->cenv->ifg;
	void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
	void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
	bitset_t *nodes = bitset_malloc(get_irg_last_idx(co->irg));
	unsigned n_regs = co->cenv->cls->n_regs;

Sebastian Hack's avatar
Sebastian Hack committed
104
	char dbg[256];
105
106
107
108
109
110
111
	unsigned i, j, curr_idx;
	int *col_map;
	int *inv_col_map;

	int *node_map;
	int *inv_node_map;

112
	be_java_coal_t *coal;
113
114
115
116
117
	ir_node *n, *m;

	col_map     = alloca(n_regs * sizeof(col_map[0]));
	inv_col_map = alloca(n_regs * sizeof(inv_col_map[0]));

Sebastian Hack's avatar
Sebastian Hack committed
118
	memset(inv_col_map, -1, sizeof(inv_col_map[0]) * n_regs);
119
120
121

	for(i = 0, j = 0; i < n_regs; ++i) {
		const arch_register_t *reg = &co->cls->regs[i];
Sebastian Hack's avatar
Sebastian Hack committed
122
		col_map[i] = -1;
123
		if(!arch_register_type_is(reg, ignore)) {
Sebastian Hack's avatar
Sebastian Hack committed
124
125
			col_map[i] = j;
			inv_col_map[j] = i;
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
			++j;
		}
	}

	node_map     = malloc((get_irg_last_idx(co->irg) + 1) * sizeof(node_map[0]));
	inv_node_map = malloc((get_irg_last_idx(co->irg) + 1) * sizeof(inv_node_map[0]));

	curr_idx = 0;
	be_ifg_foreach_node(ifg, nodes_it, n) {
		if(!arch_irn_is(co->aenv, n, ignore)) {
			int idx = get_irn_idx(n);
			bitset_set(nodes, idx);
			node_map[idx] = curr_idx;
			inv_node_map[curr_idx] = idx;
			curr_idx++;
		}
	}

	if(curr_idx == 0) {
		free(node_map);
		free(inv_node_map);
		bitset_free(nodes);
148
		return 0;
149
150
	}

151
	coal = be_java_coal_init("test", curr_idx, j, dbg_level);
152
153
154
155
156
157
158
159
160

	/* Check, if all neighbours are indeed connected to the node. */
	be_ifg_foreach_node(ifg, nodes_it, n) {
		int n_idx = get_irn_idx(n);
		int t_idx = node_map[n_idx];

		if(bitset_is_set(nodes, n_idx)) {
			affinity_node_t *an = get_affinity_info(co, n);

Sebastian Hack's avatar
Sebastian Hack committed
161
162
			ir_snprintf(dbg, sizeof(dbg), "%+F", n);
			be_java_coal_set_debug(coal, t_idx, dbg);
163
			be_java_coal_set_color(coal, t_idx, col_map[arch_get_irn_register(co->aenv, n)->index]);
164
165
166
167
168
169
			set_admissible_regs(coal, co, n, t_idx, col_map);
			be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
				int m_idx = get_irn_idx(m);
				int s_idx = node_map[m_idx];

				if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
170
					be_java_coal_add_int_edge(coal, s_idx, t_idx);
171
172
173
174
175
176
177
178
179
180
				}
			}

			if(an != NULL) {
				neighb_t *neigh;
				co_gs_foreach_neighb(an, neigh) {
					int m_idx = get_irn_idx(neigh->irn);
					int s_idx = node_map[m_idx];

					if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
181
						be_java_coal_add_aff_edge(coal, s_idx, t_idx, neigh->costs);
182
183
184
185
186
187
					}
				}
			}
		}
	}

Sebastian Hack's avatar
Sebastian Hack committed
188
189
190
	if(dump_flags & DUMP_BEFORE) {
		char fn[512];
		ir_snprintf(fn, sizeof(fn), "%F-%s-before.dot", co->cenv->irg, co->cenv->cls->name);
191
		be_java_coal_dump(coal, fn);
Sebastian Hack's avatar
Sebastian Hack committed
192
193
	}

194
	be_java_coal_coalesce(coal);
195
196
197
198
199

	be_ifg_foreach_node(ifg, nodes_it, n) {
		unsigned idx = get_irn_idx(n);
		if(bitset_is_set(nodes, idx)) {
			unsigned t_idx             = node_map[idx];
200
			unsigned col               = inv_col_map[be_java_coal_get_color(coal, t_idx)];
201
202
203
204
			const arch_register_t *reg;

			assert(col < n_regs);
			reg	= &co->cls->regs[col];
205
206
207
208
			arch_set_irn_register(co->aenv, n, reg);
		}
	}

Sebastian Hack's avatar
Sebastian Hack committed
209
210
211
	if(dump_flags & DUMP_AFTER) {
		char fn[512];
		ir_snprintf(fn, sizeof(fn), "%F-%s-after.dot", co->cenv->irg, co->cenv->cls->name);
212
		be_java_coal_dump(coal, fn);
Sebastian Hack's avatar
Sebastian Hack committed
213
214
	}

215
	be_java_coal_destroy(coal);
216
	bitset_free(nodes);
Sebastian Hack's avatar
Sebastian Hack committed
217
	return 0;
218
}