+/*
+ * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ *
+ * 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.
+ */
+
/**
- * More experiments on coalescing.
- * @author Sebastian Hack
- * @date 14.04.2006
+ * @file
+ * @brief More experiments on coalescing.
+ * @author Sebastian Hack
+ * @date 14.04.2006
+ * @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
#include <stdlib.h>
#include <limits.h>
#include "bemodule.h"
#include "beabi.h"
-#include "benode_t.h"
+#include "benode.h"
#include "becopyopt.h"
#include "becopyopt_t.h"
#include "bechordal_t.h"
+#include "beirg.h"
#define DUMP_BEFORE 1
#define DUMP_AFTER 2
static int max_depth = 20;
static double constr_factor = 0.9;
-/* Options using libcore */
static const lc_opt_enum_mask_items_t dump_items[] = {
{ "before", DUMP_BEFORE },
{ "after", DUMP_AFTER },
LC_OPT_ENT_INT ("iter", "iterations for subtree nodes", &subtree_iter),
LC_OPT_ENT_DBL ("cf", "factor of constraint importance (between 0.0 and 1.0)", &constr_factor),
LC_OPT_ENT_INT ("max", "maximum recursion depth", &max_depth),
- { NULL }
+ LC_OPT_LAST
};
-void be_init_copyheur2(void)
-{
- 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 *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
-
- lc_opt_add_table(co2_grp, options);
-}
-
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
-
/*
____ _ _
/ ___|| |_ __ _ _ __| |_
} co2_t;
struct _co2_irn_t {
- ir_node *irn;
+ const ir_node *irn;
affinity_node_t *aff;
co2_irn_t *touched_next;
col_t tmp_col;
#define get_co2_irn(co2, irn) ((co2_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
#define get_co2_cloud_irn(co2, irn) ((co2_cloud_irn_t *) phase_get_or_set_irn_data(&co2->ph, irn))
-static void *co2_irn_init(ir_phase *ph, ir_node *irn, void *data)
+static void *co2_irn_init(ir_phase *ph, const ir_node *irn, void *data)
{
co2_t *env = (co2_t *) ph;
affinity_node_t *a = get_affinity_info(env->co, irn);
memset(ci, 0, size);
INIT_LIST_HEAD(&ci->changed_list);
ci->touched_next = env->touched;
- ci->orig_col = get_irn_col(env->co, irn);
+ ci->orig_col = get_irn_col(irn);
env->touched = ci;
ci->irn = irn;
ci->aff = a;
return QSORT_CMP(q->costs, p->costs);
}
-static col_t get_col(co2_t *env, ir_node *irn)
+static col_t get_col(co2_t *env, const ir_node *irn)
{
co2_irn_t *ci = get_co2_irn(env, irn);
return ci->tmp_fixed ? ci->tmp_col : ci->orig_col;
}
-static INLINE int color_is_fix(co2_t *env, ir_node *irn)
+static inline int color_is_fix(co2_t *env, const ir_node *irn)
{
co2_irn_t *ci = get_co2_irn(env, irn);
return ci->fixed || ci->tmp_fixed;
}
-static INLINE bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
+static inline bitset_t *get_adm(co2_t *env, co2_irn_t *ci)
{
if(ci->adm_cache == NULL) {
const arch_register_req_t *req;
ci->adm_cache = bitset_obstack_alloc(phase_obst(&env->ph), env->n_regs);
- req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
+ req = arch_get_register_req_out(ci->irn);
if(arch_register_req_is(req, limited)) {
int i, n;
return ci->adm_cache;
}
-static INLINE bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
+static inline bitset_t *admissible_colors(co2_t *env, co2_irn_t *ci, bitset_t *bs)
{
bitset_copy(bs, get_adm(env, ci));
return bs;
}
-static INLINE int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
+static inline int is_color_admissible(co2_t *env, co2_irn_t *ci, col_t col)
{
bitset_t *bs = get_adm(env, ci);
return bitset_is_set(bs, col);
}
-static INLINE int is_constrained(co2_t *env, co2_irn_t *ci)
+static inline int is_constrained(co2_t *env, co2_irn_t *ci)
{
if(!ci->adm_cache)
get_adm(env, ci);
return ci->is_constrained;
}
-static void incur_constraint_costs(co2_t *env, ir_node *irn, col_cost_pair_t *col_costs, int costs)
+static void incur_constraint_costs(co2_t *env, const ir_node *irn, col_cost_pair_t *col_costs, int costs)
{
- const arch_register_req_t *req;
-
- req = arch_get_register_req(env->co->aenv, irn, BE_OUT_POS(0));
+ const arch_register_req_t *req = arch_get_register_req_out(irn);
- if(arch_register_req_is(req, limited)) {
- unsigned n_regs = env->co->cls->n_regs;
+ if (arch_register_req_is(req, limited)) {
+ unsigned n_regs = env->co->cls->n_regs;
unsigned n_constr = 0;
- int i;
+ unsigned i;
n_constr = rbitset_popcnt(req->limited, n_regs);
- for(i = 0; i < n_regs; ++i) {
- if(rbitset_is_set(req->limited, i)) {
- col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
+ for (i = 0; i < n_regs; ++i) {
+ if (rbitset_is_set(req->limited, i)) {
+ col_costs[i].costs = add_saturated(col_costs[i].costs, costs / n_constr);
}
}
}
*/
static void determine_color_costs(co2_t *env, co2_irn_t *ci, col_cost_pair_t *col_costs)
{
- ir_node *irn = ci->irn;
+ const ir_node *irn = ci->irn;
be_ifg_t *ifg = env->co->cenv->ifg;
int n_regs = env->co->cls->n_regs;
bitset_t *forb = bitset_alloca(n_regs);
affinity_node_t *a = ci->aff;
bitset_pos_t elm;
- ir_node *pos;
+ const ir_node *pos;
void *it;
int i;
seq[i].costs = INT_MAX;
}
+ (void) ci;
assert(is_color_admissible(env, ci, col));
seq[col].col = 0;
seq[0].col = col;
}
}
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth);
-static int recolor(co2_t *env, ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
+static int recolor(co2_t *env, const ir_node *irn, col_cost_pair_t *col_list, struct list_head *parent_changed, int depth)
{
int n_regs = env->co->cls->n_regs;
be_ifg_t *ifg = env->co->cenv->ifg;
int neigh_ok = 1;
struct list_head changed;
- ir_node *n;
+ const ir_node *n;
void *it;
DBG((env->dbg, LEVEL_3, "\t\t%2{firm:indent}trying color %d(%d) on %+F\n", depth, tgt_col, costs, irn));
return res;
}
-static int change_color_not(co2_t *env, ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
+static int change_color_not(co2_t *env, const ir_node *irn, col_t not_col, struct list_head *parent_changed, int depth)
{
co2_irn_t *ci = get_co2_irn(env, irn);
int res = 0;
/* The node has the color it should not have _and_ has not been visited yet. */
if(!color_is_fix(env, irn)) {
int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *csts = alloca(n_regs * sizeof(csts[0]));
+ col_cost_pair_t *csts = ALLOCAN(col_cost_pair_t, n_regs);
/* Get the costs for giving the node a specific color. */
determine_color_costs(env, ci, csts);
return res;
}
-static int change_color_single(co2_t *env, ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
+static int change_color_single(co2_t *env, const ir_node *irn, col_t tgt_col, struct list_head *parent_changed, int depth)
{
co2_irn_t *ci = get_co2_irn(env, irn);
col_t col = get_col(env, irn);
if(!color_is_fix(env, irn) && is_color_admissible(env, ci, tgt_col)) {
int n_regs = env->co->cls->n_regs;
- col_cost_pair_t *seq = alloca(n_regs * sizeof(seq[0]));
+ col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, n_regs);
/* Get the costs for giving the node a specific color. */
single_color_cost(env, ci, tgt_col, seq);
bitset_t *bs = bitset_alloca(n_regs);
bitset_pos_t elm;
- ir_node *irn;
+ const ir_node *irn;
void *it;
admissible_colors(env, &ci->inh, bs);
static int coalesce_top_down(co2_cloud_irn_t *ci, int child_nr, int depth)
{
co2_t *env = ci->cloud->env;
- col_cost_pair_t *seq = alloca(env->n_regs * sizeof(seq[0]));
+ col_cost_pair_t *seq = ALLOCAN(col_cost_pair_t, env->n_regs);
int is_root = ci->mst_parent == ci;
- col_t parent_col = is_root ? -1 : get_col(env, ci->mst_parent->inh.irn);
+ col_t parent_col = is_root ? (col_t) -1 : get_col(env, ci->mst_parent->inh.irn);
int min_badness = INT_MAX;
int best_col_costs = INT_MAX;
int best_col = -1;
static void apply_coloring(co2_cloud_irn_t *ci, col_t col, int depth)
{
- ir_node *irn = ci->inh.irn;
+ const ir_node *irn = ci->inh.irn;
int *front = FRONT_BASE(ci, col);
int i, ok;
struct list_head changed;
co2_t *env = cloud->env;
int n_regs = env->n_regs;
int n_edges = 0;
- int *mst_edges = xmalloc(cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
+ int *mst_edges = XMALLOCNZ(int, cloud->n_memb * cloud->n_memb);
pdeq *q;
edge_t *edges;
int i;
int best_col;
- memset(mst_edges, 0, cloud->n_memb * cloud->n_memb * sizeof(mst_edges[0]));
-
/* Collect all edges in the cloud on an obstack and sort the increasingly */
obstack_init(&cloud->obst);
for(i = 0; i < cloud->n_memb; ++i) {
int n_childs = ci->mst_n_childs;
int j;
- ci->col_costs = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->col_costs[0]));
- ci->tmp_coloring = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->tmp_coloring[0]));
- ci->fronts = obstack_alloc(&cloud->obst, n_regs * n_childs * sizeof(ci->fronts[0]));
- ci->color_badness = obstack_alloc(&cloud->obst, n_regs * sizeof(ci->fronts[0]));
- memset(ci->color_badness, 0, n_regs * sizeof(ci->color_badness[0]));
- memset(ci->col_costs, 0, n_regs * sizeof(ci->col_costs[0]));
- memset(ci->tmp_coloring, 0, n_regs * sizeof(ci->tmp_coloring[0]));
- memset(ci->fronts, 0, n_regs * n_childs * sizeof(ci->fronts[0]));
+ ci->col_costs = OALLOCNZ(&cloud->obst, int, n_regs);
+ ci->tmp_coloring = OALLOCNZ(&cloud->obst, col_cost_pair_t, n_regs);
+ ci->fronts = OALLOCNZ(&cloud->obst, int, n_regs * n_childs);
+ ci->color_badness = OALLOCNZ(&cloud->obst, int, n_regs);
for(j = 0; j < env->n_regs; j++)
ci->col_costs[j] = INT_MAX;
-
}
determine_color_badness(cloud->mst_root, 0);
}
i = 0;
- clouds = xmalloc(n_clouds * sizeof(clouds[0]));
+ clouds = XMALLOCN(co2_cloud_t*, n_clouds);
list_for_each_entry(co2_cloud_t, pos, &env->cloud_head, list)
clouds[i++] = pos;
qsort(clouds, n_clouds, sizeof(clouds[0]), cmp_clouds_gt);
static void writeback_colors(co2_t *env)
{
- const arch_env_t *aenv = env->co->aenv;
co2_irn_t *irn;
for(irn = env->touched; irn; irn = irn->touched_next) {
const arch_register_t *reg = arch_register_for_index(env->co->cls, irn->orig_col);
- arch_set_irn_register(aenv, irn->irn, reg);
+ arch_set_irn_register((ir_node*)irn->irn, reg);
}
}
|_| |___/
*/
-static const char *get_dot_color_name(int col)
+static const char *get_dot_color_name(size_t col)
{
- static const char *names[] = {
+ static const char *const names[] = {
"blue",
"red",
"green",
"palevioletred"
};
- return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
+ return col < (sizeof(names)/sizeof(names[0])) ? names[col] : "white";
}
-static const char *get_dot_shape_name(co2_t *env, co2_irn_t *ci)
+static const char *get_dot_shape_name(co2_irn_t *ci)
{
- const arch_register_req_t *req;
+ const arch_register_req_t *req = arch_get_register_req_out(ci->irn);
- req = arch_get_register_req(env->co->aenv, ci->irn, BE_OUT_POS(0));
if(arch_register_req_is(req, limited))
return "diamond";
static void ifg_dump_graph_attr(FILE *f, void *self)
{
+ (void) self;
fprintf(f, "overlay=false");
}
static int ifg_is_dump_node(void *self, ir_node *irn)
{
- co2_t *env = self;
- return !arch_irn_is(env->co->aenv, irn, ignore);
+ const arch_register_req_t *req = arch_get_register_req_out(irn);
+ (void)self;
+ return !(req->type & arch_register_req_type_ignore);
}
static void ifg_dump_node_attr(FILE *f, void *self, ir_node *irn)
}
ir_fprintf(f, "label=\"%+F%s\" style=filled peripheries=%d color=%s shape=%s", irn, buf, peri,
- get_dot_color_name(get_col(env, irn)), get_dot_shape_name(env, ci));
+ get_dot_color_name(get_col(env, irn)), get_dot_shape_name(ci));
}
static void ifg_dump_at_end(FILE *file, void *self)
ifg_dump_at_end
};
-
int co_solve_heuristic_new(copy_opt_t *co)
{
- char buf[256];
+ char buf[256];
co2_t env;
- FILE *f;
+ FILE *f;
- phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init);
+ phase_init(&env.ph, "co2", co->cenv->birg->irg, PHASE_DEFAULT_GROWTH, co2_irn_init, NULL);
env.touched = NULL;
env.visited = 0;
env.co = co;
env.n_regs = co->cls->n_regs;
env.ignore_regs = bitset_alloca(co->cls->n_regs);
- arch_put_non_ignore_regs(co->aenv, co->cls, env.ignore_regs);
- bitset_flip_all(env.ignore_regs);
- be_abi_put_ignore_regs(co->cenv->birg->abi, co->cls, env.ignore_regs);
+ be_put_ignore_regs(co->cenv->birg, co->cls, env.ignore_regs);
FIRM_DBG_REGISTER(env.dbg, "firm.be.co2");
INIT_LIST_HEAD(&env.cloud_head);
phase_free(&env.ph);
return 0;
}
+
+void be_init_copyheur2(void)
+{
+ 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 *co2_grp = lc_opt_get_grp(chordal_grp, "co2");
+
+ static co_algo_info copyheur = {
+ co_solve_heuristic_new, 0
+ };
+
+ lc_opt_add_table(co2_grp, options);
+ be_register_copyopt("heur2", ©heur);
+}
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur2);
projects / libfirm / blobdiff