/*
- * 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @brief PBQP based register allocation.
* @author Thomas Bersch
* @date 27.11.2009
- * @version $Id: bechordal.c 26750 2009-11-27 09:37:43Z bersch $
*/
/* miscellaneous includes */
#include "iredges_t.h"
#include "irprintf.h"
#include "irgwalk.h"
+#include "irtools.h"
#include "time.h"
-
-/* libfirm/ir/adt includes */
+#include "execfreq_t.h"
#include "bipartite.h"
/* libfirm/ir/be includes */
#include "bechordal_common.h"
#include "bechordal.h"
#include "bechordal_t.h"
+#include "becopyopt_t.h"
#include "beinsn_t.h"
#include "benode.h"
#include "belive.h"
#include "beutil.h"
#include "plist.h"
#include "pqueue.h"
-#include "becopyopt.h"
/* pbqp includes */
#include "kaps.h"
ir_graph *irg; /**< The graph under examination. */
const arch_register_class_t *cls; /**< Current processed register class */
be_lv_t *lv;
- bitset_t *allocatable_regs;
+ bitset_t const *allocatable_regs;
pbqp_matrix_t *ife_matrix_template;
pbqp_matrix_t *aff_matrix_template;
plist_t *rpeo;
unsigned *restr_nodes;
unsigned *ife_edge_num;
+ ir_execfreq_int_factors execfreq_factors;
be_chordal_env_t *env;
} be_pbqp_alloc_env_t;
-#define is_Reg_Phi(irn) (is_Phi(irn) && mode_is_data(get_irn_mode(irn)))
-#define get_Perm_src(irn) (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
-#define is_Perm_Proj(irn) (is_Proj(irn) && be_is_Perm(get_Proj_pred(irn)))
#define insert_edge(pbqp, src_node, trg_node, template_matrix) (add_edge_costs(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node), pbqp_matrix_copy(pbqp, template_matrix)))
#define get_free_regs(restr_nodes, cls, irn) (arch_register_class_n_regs(cls) - restr_nodes[get_irn_idx(irn)])
-static inline int is_2addr_code(const arch_register_req_t *req)
-{
- return (req->type & arch_register_req_type_should_be_same) != 0;
-}
-
static const lc_opt_table_entry_t options[] = {
LC_OPT_ENT_BOOL("exec_freq", "use exec_freq", &use_exec_freq),
LC_OPT_ENT_BOOL("late_decision", "use late decision for register allocation", &use_late_decision),
static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn)
{
- const arch_register_class_t *cls = pbqp_alloc_env->cls;
- pbqp_t *pbqp_inst = pbqp_alloc_env->pbqp_inst;
- bitset_t *allocatable_regs = pbqp_alloc_env->allocatable_regs;
- unsigned colors_n = arch_register_class_n_regs(cls);
- unsigned cntConstrains = 0;
+ arch_register_class_t const *const cls = pbqp_alloc_env->cls;
+ pbqp_t *const pbqp_inst = pbqp_alloc_env->pbqp_inst;
+ bitset_t const *const allocatable_regs = pbqp_alloc_env->allocatable_regs;
+ unsigned const colors_n = arch_register_class_n_regs(cls);
+ unsigned cntConstrains = 0;
/* create costs vector depending on register constrains */
vector_t *costs_vector = vector_alloc(pbqp_inst, colors_n);
/* set costs depending on register constrains */
unsigned idx;
for (idx = 0; idx < colors_n; idx++) {
- if (!bitset_is_set(allocatable_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) {
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
+ const arch_register_t *reg = arch_register_for_index(cls, idx);
+ if (!bitset_is_set(allocatable_regs, idx)
+ || !arch_reg_is_allocatable(req, reg)) {
/* constrained */
vector_set(costs_vector, idx, INF_COSTS);
cntConstrains++;
if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
if (use_exec_freq) {
/* get exec_freq for copy_block */
- ir_node *root_bl = get_nodes_block(src_node);
- ir_node *copy_bl = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
- ir_exec_freq *exec_freq = be_get_irg_exec_freq(pbqp_alloc_env->irg);
- unsigned long res = get_block_execfreq_ulong(exec_freq, copy_bl);
+ ir_node *root_bl = get_nodes_block(src_node);
+ ir_node *copy_bl = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
+ int res = get_block_execfreq_int(&pbqp_alloc_env->execfreq_factors, copy_bl);
/* create afe-matrix */
unsigned row, col;
{
be_pbqp_alloc_env_t *pbqp_alloc_env = (be_pbqp_alloc_env_t*)env;
const arch_register_class_t *cls = pbqp_alloc_env->cls;
- const arch_register_req_t *req = arch_get_register_req_out(irn);
+ const arch_register_req_t *req = arch_get_irn_register_req(irn);
unsigned pos;
unsigned max;
- if (is_Reg_Phi(irn)) { /* Phis */
+ if (is_Phi(irn)) { /* Phis */
for (pos = 0, max = get_irn_arity(irn); pos < max; ++pos) {
ir_node *arg = get_irn_n(irn, pos);
return;
insert_afe_edge(pbqp_alloc_env, irn, arg, -1);
- }
- else { /* 2-address code */
- if (is_2addr_code(req)) {
- const unsigned other = req->other_same;
- int i;
-
- for (i = 0; 1U << i <= other; ++i) {
- if (other & (1U << i)) {
- ir_node *other = get_irn_n(skip_Proj(irn), i);
- if (!arch_irn_consider_in_reg_alloc(cls, other))
- continue;
-
- /* no edges to itself */
- if (irn == other) {
- continue;
- }
+ } else if (arch_register_req_is(req, should_be_same)) {
+ const unsigned other = req->other_same;
+ int i;
+
+ for (i = 0; 1U << i <= other; ++i) {
+ if (other & (1U << i)) {
+ ir_node *other = get_irn_n(skip_Proj(irn), i);
+ if (!arch_irn_consider_in_reg_alloc(cls, other))
+ continue;
- insert_afe_edge(pbqp_alloc_env, irn, other, i);
+ /* no edges to itself */
+ if (irn == other) {
+ continue;
}
+
+ insert_afe_edge(pbqp_alloc_env, irn, other, i);
}
}
}
pbqp_t *pbqp_inst = pbqp_alloc_env->pbqp_inst;
plist_t *temp_list = plist_new();
plist_element_t *el;
- ir_node *irn;
ir_nodeset_t live_nodes;
#if USE_BIPARTIT_MATCHING
int *assignment = ALLOCAN(int, cls->n_regs);
/* create pbqp nodes, interference edges and reverse perfect elimination order */
sched_foreach_reverse(block, irn) {
- ir_node *live;
- ir_nodeset_iterator_t iter;
-
- if (get_irn_mode(irn) == mode_T) {
- const ir_edge_t *edge;
- foreach_out_edge(irn, edge) {
- ir_node *proj = get_edge_src_irn(edge);
- if (!arch_irn_consider_in_reg_alloc(cls, proj))
- continue;
-
- /* create pbqp source node if it dosn't exist */
- if (get_node(pbqp_inst, get_irn_idx(proj)) == NULL) {
- create_pbqp_node(pbqp_alloc_env, proj);
- }
-
- /* create nodes and interference edges */
- foreach_ir_nodeset(&live_nodes, live, iter) {
- /* create pbqp source node if it dosn't exist */
- if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
- create_pbqp_node(pbqp_alloc_env, live);
- }
+ be_foreach_value(irn, value,
+ if (!arch_irn_consider_in_reg_alloc(cls, value))
+ continue;
- /* no edges to itself */
- if (proj == live) {
- continue;
- }
+ /* create pbqp source node if it dosn't exist */
+ if (!get_node(pbqp_inst, get_irn_idx(value)))
+ create_pbqp_node(pbqp_alloc_env, value);
- insert_ife_edge(pbqp_alloc_env, proj, live);
- }
- }
- }
- else {
- if (arch_irn_consider_in_reg_alloc(cls, irn)) {
+ /* create nodes and interference edges */
+ foreach_ir_nodeset(&live_nodes, live, iter) {
/* create pbqp source node if it dosn't exist */
- if (get_node(pbqp_inst, get_irn_idx(irn)) == NULL) {
- create_pbqp_node(pbqp_alloc_env, irn);
- }
+ if (!get_node(pbqp_inst, get_irn_idx(live)))
+ create_pbqp_node(pbqp_alloc_env, live);
- /* create nodes and interference edges */
- foreach_ir_nodeset(&live_nodes, live, iter) {
- /* create pbqp source node if it dosn't exist */
- if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
- create_pbqp_node(pbqp_alloc_env, live);
- }
-
- /* no edges to itself */
- if (irn == live) {
- continue;
- }
+ /* no edges to itself */
+ if (value == live)
+ continue;
- /* insert interference edge */
- insert_ife_edge(pbqp_alloc_env, irn, live);
- }
+ insert_ife_edge(pbqp_alloc_env, value, live);
}
- }
+ );
/* get living nodes for next step */
if (!is_Phi(irn)) {
bipartite_t *bp = bipartite_new(cls->n_regs, cls->n_regs);
/* add all proj after a perm to clique */
- const ir_edge_t *edge;
foreach_out_edge(irn, edge) {
ir_node *proj = get_edge_src_irn(edge);
#else
/* order nodes for perfect elimination order */
if (get_irn_mode(irn) == mode_T) {
- bool allHaveIFEdges = true;
- const ir_edge_t *edge;
-
+ bool allHaveIFEdges = true;
foreach_out_edge(irn, edge) {
ir_node *proj = get_edge_src_irn(edge);
if (!arch_irn_consider_in_reg_alloc(cls, proj))
static void insert_perms(ir_node *block, void *data)
{
be_chordal_env_t *env = (be_chordal_env_t*)data;
- ir_node *irn;
-
- for (irn = sched_first(block); !sched_is_end(irn);) {
- be_insn_t *insn = chordal_scan_insn(env, irn);
- irn = insn->next_insn;
- if (!insn->has_constraints)
- continue;
-
- pre_process_constraints(env, &insn);
+ sched_foreach_safe(block, irn) {
+ be_insn_t *insn = be_scan_insn(env, irn);
+ if (insn)
+ pre_process_constraints(env, &insn);
}
}
printf("#### ----- === Allocating registers of %s (%s) ===\n", cls->name, get_entity_name(get_irg_entity(irg)));
#endif
- lv = be_assure_liveness(irg);
- be_liveness_assure_sets(lv);
- be_liveness_assure_chk(lv);
+ be_assure_live_sets(irg);
+ lv = be_get_irg_liveness(irg);
/* insert perms */
assure_doms(irg);
/* dump graph after inserting perms */
if (env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
char buf[256];
- snprintf(buf, sizeof(buf), "-%s-constr", cls->name);
+ snprintf(buf, sizeof(buf), "%s-constr", cls->name);
dump_ir_graph(irg, buf);
}
+ ir_calculate_execfreq_int_factors(&pbqp_alloc_env.execfreq_factors, irg);
/* initialize pbqp allocation data structure */
pbqp_alloc_env.pbqp_inst = alloc_pbqp(get_irg_last_idx(irg)); /* initialize pbqp instance */
pbqp_alloc_env.cls = cls;
pbqp_alloc_env.irg = irg;
pbqp_alloc_env.lv = lv;
- pbqp_alloc_env.allocatable_regs = bitset_malloc(colors_n);
+ pbqp_alloc_env.allocatable_regs = env->allocatable_regs;
pbqp_alloc_env.rpeo = plist_new();
pbqp_alloc_env.restr_nodes = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
pbqp_alloc_env.ife_edge_num = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
pbqp_alloc_env.env = env;
- be_put_allocatable_regs(irg, cls, pbqp_alloc_env.allocatable_regs);
-
/* create costs matrix template for interference edges */
ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
#if KAPS_DUMP
fclose(file_before);
#endif
- bitset_free(pbqp_alloc_env.allocatable_regs);
free_pbqp(pbqp_alloc_env.pbqp_inst);
plist_free(pbqp_alloc_env.rpeo);
xfree(pbqp_alloc_env.restr_nodes);
projects / libfirm / blobdiff