2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief More experiments on coalescing with Java implementation.
23 * @author Sebastian Hack
39 #include "bitfiddle.h"
41 #include "raw_bitset.h"
43 #include "irgraph_t.h"
51 #include "becopyopt.h"
52 #include "becopyopt_t.h"
53 #include "bechordal_t.h"
54 #include "bejavacoal.h"
61 #define DUMP_ALL 2 * DUMP_AFTER - 1
63 static unsigned dump_flags = 0;
64 static int dbg_level = 0;
67 #include <libcore/lc_opts.h>
68 #include <libcore/lc_opts_enum.h>
70 static const lc_opt_enum_mask_items_t dump_items[] = {
71 { "before", DUMP_BEFORE },
72 { "after", DUMP_AFTER },
77 static lc_opt_enum_mask_var_t dump_var = {
78 &dump_flags, dump_items
81 static const lc_opt_table_entry_t options[] = {
82 LC_OPT_ENT_ENUM_MASK("dump", "dump ifg cloud", &dump_var),
83 LC_OPT_ENT_INT ("dbg", "debug level for the Java coalescer", &dbg_level),
86 #endif /* WITH_LIBCORE */
88 void be_init_copyheur3(void)
91 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
92 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
93 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
94 lc_opt_entry_t *co3_grp = lc_opt_get_grp(chordal_grp, "co3");
96 lc_opt_add_table(co3_grp, options);
100 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur3);
102 static void set_admissible_regs(be_java_coal_t *coal, copy_opt_t *co, ir_node *irn, int t_idx, int *col_map)
104 const arch_register_req_t *req;
106 req = arch_get_register_req(co->aenv, irn, BE_OUT_POS(0));
108 // ir_printf("%+F\n", irn);
109 if(arch_register_req_is(req, limited)) {
111 unsigned n_regs = co->cls->n_regs;
113 for(i = 0; i < n_regs; ++i) {
114 if(!rbitset_is_set(req->limited, i) && col_map[i] >= 0) {
115 be_java_coal_forbid_color(coal, t_idx, col_map[i]);
121 int co_solve_heuristic_java(copy_opt_t *co)
123 be_ifg_t *ifg = co->cenv->ifg;
124 void *nodes_it = be_ifg_nodes_iter_alloca(ifg);
125 void *neigh_it = be_ifg_neighbours_iter_alloca(ifg);
126 bitset_t *nodes = bitset_malloc(get_irg_last_idx(co->irg));
127 unsigned n_regs = co->cenv->cls->n_regs;
130 unsigned i, j, curr_idx;
137 be_java_coal_t *coal;
140 col_map = alloca(n_regs * sizeof(col_map[0]));
141 inv_col_map = alloca(n_regs * sizeof(inv_col_map[0]));
143 memset(inv_col_map, -1, sizeof(inv_col_map[0]) * n_regs);
145 for(i = 0, j = 0; i < n_regs; ++i) {
146 const arch_register_t *reg = &co->cls->regs[i];
148 if(!arch_register_type_is(reg, ignore)) {
155 node_map = xmalloc((get_irg_last_idx(co->irg) + 1) * sizeof(node_map[0]));
156 inv_node_map = xmalloc((get_irg_last_idx(co->irg) + 1) * sizeof(inv_node_map[0]));
159 be_ifg_foreach_node(ifg, nodes_it, n) {
160 if(!arch_irn_is(co->aenv, n, ignore)) {
161 int idx = get_irn_idx(n);
162 bitset_set(nodes, idx);
163 node_map[idx] = curr_idx;
164 inv_node_map[curr_idx] = idx;
176 coal = be_java_coal_init("test", curr_idx, j, dbg_level);
178 /* Check, if all neighbours are indeed connected to the node. */
179 be_ifg_foreach_node(ifg, nodes_it, n) {
180 int n_idx = get_irn_idx(n);
181 int t_idx = node_map[n_idx];
183 if(bitset_is_set(nodes, n_idx)) {
184 affinity_node_t *an = get_affinity_info(co, n);
186 ir_snprintf(dbg, sizeof(dbg), "%+F", n);
187 be_java_coal_set_debug(coal, t_idx, dbg);
188 be_java_coal_set_color(coal, t_idx, col_map[arch_get_irn_register(co->aenv, n)->index]);
189 set_admissible_regs(coal, co, n, t_idx, col_map);
190 be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
191 int m_idx = get_irn_idx(m);
192 int s_idx = node_map[m_idx];
194 if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
195 be_java_coal_add_int_edge(coal, s_idx, t_idx);
201 co_gs_foreach_neighb(an, neigh) {
202 int m_idx = get_irn_idx(neigh->irn);
203 int s_idx = node_map[m_idx];
205 if(n_idx < m_idx && bitset_is_set(nodes, m_idx)) {
206 be_java_coal_add_aff_edge(coal, s_idx, t_idx, neigh->costs);
213 if(dump_flags & DUMP_BEFORE) {
215 ir_snprintf(fn, sizeof(fn), "%F-%s-before.dot", co->cenv->irg, co->cenv->cls->name);
216 be_java_coal_dump(coal, fn);
219 be_java_coal_coalesce(coal);
221 be_ifg_foreach_node(ifg, nodes_it, n) {
222 unsigned idx = get_irn_idx(n);
223 if(bitset_is_set(nodes, idx)) {
224 unsigned t_idx = node_map[idx];
225 unsigned col = inv_col_map[be_java_coal_get_color(coal, t_idx)];
226 const arch_register_t *reg;
228 assert(col < n_regs);
229 reg = &co->cls->regs[col];
230 arch_set_irn_register(co->aenv, n, reg);
234 if(dump_flags & DUMP_AFTER) {
236 ir_snprintf(fn, sizeof(fn), "%F-%s-after.dot", co->cenv->irg, co->cenv->cls->name);
237 be_java_coal_dump(coal, fn);
240 be_java_coal_destroy(coal);