* @author Daniel Grund
* @date 12.04.2005
*/
-
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifdef HAVE_ALLOCA_H
+#include <alloca.h>
+#endif
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
+
+#include "xmalloc.h"
#include "becopyopt.h"
+#include "becopystat.h"
#define DEBUG_LVL 0 //SET_LEVEL_1
static firm_dbg_module_t *dbg = NULL;
/**
* If an irn is changed, the changes first get stored in a node_stat_t,
- * to allow undo of changes (=drop new data) in case of conflicts.
+ * to allow undo of changes (=drop new data) in case of conflicts.
*/
typedef struct _node_stat_t {
const ir_node *irn;
*/
typedef struct _qnode_t {
struct list_head queue; /**< chaining of unit_t->queue */
+ const unit_t *ou; /**< the opt unit this qnode belongs to */
int color; /**< target color */
set *conflicts; /**< contains conflict_t's. All internal conflicts */
int mis_size; /**< number of nodes in the mis. */
- const ir_node **mis; /**< the nodes of unit_t->nodes[] beeing part of the max idependent set */
+ const ir_node **mis; /**< the nodes of unit_t->nodes[] being part of the max independent set */
set *changed_nodes; /**< contains node_stat_t's. */
} qnode_t;
* @param irn The node to set the color for
* @param col The color to set
* @param trigger The irn that caused the wish to change the color of the irn
- * @return CHANGE_SAVE iff setting the color is possible, with all transiteve effects.
+ * @return CHANGE_SAVE iff setting the color is possible, with all transitive effects.
* CHANGE_IMPOSSIBLE iff conflicts with reg-constraintsis occured.
* Else the first conflicting ir_node encountered is returned.
*
- * ASSUMPTION: Assumes that a life range of a single value can't be spilt into
+ * ASSUMPTION: Assumes that a life range of a single value can't be split into
* several smaller intervals where other values can live in between.
* This should be true in SSA.
*/
if (irn_col == col)
goto ret_save;
- if (!is_possible_color(irn, col))
- goto ret_imposs;
if (pset_find_ptr(pinned_global, irn) || qnode_is_pinned_local(qn, irn)) {
res = irn;
goto ret_confl;
}
+ if (!qn->ou->co->isa->is_reg_allocatable(irn, arch_register_for_index(qn->ou->co->cls, col)))
+ goto ret_imposs;
/* get all nodes which would conflict with this change */
{
ret_imposs:
DBG((dbg, LEVEL_3, "\t %n impossible\n", irn));
obstack_free(&confl_ob, NULL);
- return res;
+ return CHANGE_IMPOSSIBLE;
ret_confl:
DBG((dbg, LEVEL_3, "\t %n conflicting\n", irn));
/* stores the currently examined set */
curr = alloca(all_size*sizeof(*curr));
- while (1) { /* this loop will terminate because at least a single node'll be a max indep. set */
+ while (1) { /* this loop will terminate because at least a single node will be a max indep. set */
/* build current set */
for (i=0; i<curr_size; ++i)
curr[i] = all[which[all_size-curr_size+i]];
* Creates a new qnode
*/
static INLINE qnode_t *new_qnode(const unit_t *ou, int color) {
- qnode_t *qn = malloc(sizeof(*qn));
+ qnode_t *qn = xmalloc(sizeof(*qn));
+ qn->ou = ou;
qn->color = color;
qn->mis = malloc(ou->node_count * sizeof(*qn->mis));
qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS);
static INLINE void free_qnode(qnode_t *qn) {
del_set(qn->conflicts);
del_set(qn->changed_nodes);
- free(qn->mis);
- free(qn);
+ xfree(qn->mis);
+ xfree(qn);
}
/**
- * Inserts a qnode in the sorted queue of the outimization unit. Queue is
+ * Inserts a qnode in the sorted queue of the optimization unit. Queue is
* ordered by field 'size' (the size of the mis) in decreasing order.
*/
static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) {
static void ou_optimize(unit_t *ou) {
int i;
qnode_t *curr, *tmp;
+ bitset_t *pos_regs = bitset_alloca(ou->co->cls->n_regs);
DBG((dbg, LEVEL_1, "\tOptimizing unit:\n"));
for (i=0; i<ou->node_count; ++i)
/* init queue */
INIT_LIST_HEAD(&ou->queue);
- for (i=0; i<MAX_COLORS; ++i)
- if (is_possible_color(ou->nodes[0], i))
- ou_insert_qnode(ou, new_qnode(ou, i));
+ ou->co->isa->get_allocatable_regs(ou->nodes[0], ou->co->cls, pos_regs);
+ bitset_foreach(pos_regs, i)
+ ou_insert_qnode(ou, new_qnode(ou, i));
/* search best */
while (!list_empty(&ou->queue)) {
/* apply the best found qnode */
if (curr->mis_size >= 2) {
+ node_stat_t *ns;
+
DBG((dbg, LEVEL_1, "\t Best color: %d Copies: %d/%d\n", curr->color, ou->interf+ou->node_count-curr->mis_size, ou->interf+ou->node_count-1));
/* globally pin root and eventually others */
pset_insert_ptr(pinned_global, ou->nodes[0]);
}
/* set color of all changed nodes */
- node_stat_t *ns;
for (ns = set_first(curr->changed_nodes); ns; ns = set_next(curr->changed_nodes)) {
/* NO_COLOR is possible, if we had an undo */
if (ns->new_color != NO_COLOR) {
unit_t *curr;
dbg = firm_dbg_register("ir.be.copyoptheur");
firm_dbg_set_mask(dbg, DEBUG_LVL);
+ if (!strcmp(co->name, DEBUG_IRG))
+ firm_dbg_set_mask(dbg, -1);
pinned_global = pset_new_ptr(SLOTS_PINNED_GLOBAL);
-
list_for_each_entry(unit_t, curr, &co->units, units)
- ou_optimize(curr);
+ if (curr->node_count > 1)
+ ou_optimize(curr);
del_pset(pinned_global);
}
projects / libfirm / blobdiff