X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbecopyopt_t.h;h=dc8f838c1d01039afb36eaef67bb0d7527c36f80;hb=ca1b1615fbe23a4d5cf72e7be5d2ee831615cbc2;hp=28fb8dd477752438daa8b3033562ba47e62ff687;hpb=719b0dc8377fc55decc4629bf5e523104a82b76f;p=libfirm diff --git a/ir/be/becopyopt_t.h b/ir/be/becopyopt_t.h index 28fb8dd47..dc8f838c1 100644 --- a/ir/be/becopyopt_t.h +++ b/ir/be/becopyopt_t.h @@ -10,13 +10,12 @@ #ifndef _BECOPYOPT_T_H #define _BECOPYOPT_T_H +#include #include "list.h" #include "bearch.h" #include "bechordal_t.h" #include "becopyopt.h" -#define MIS_HEUR_TRIGGER 8 - /** * Data representing the problem of copy minimization. */ @@ -26,85 +25,112 @@ struct _copy_opt_t { const arch_env_t *aenv; ir_graph *irg; char *name; /**< ProgName__IrgName__RegClassName */ + cost_fct_t get_costs; /**< function ptr used to get costs for copies */ + /** Representation as optimization units */ struct list_head units; /**< all units to optimize in specific order */ - cost_fct_t get_costs; /**< function ptr used to get costs for copies */ - struct obstack ob; + + /** Representation in graph structure. Only build on demand */ + struct obstack obst; + set *nodes; }; -/** - * A single unit of optimization. Lots of these form a copy-opt problem - */ +/* Helpers */ +#define ASSERT_OU_AVAIL(co) assert((co)->units.next && "Representation as optimization-units not build") +#define ASSERT_GS_AVAIL(co) assert((co)->nodes && "Representation as graph not build") + +#define get_irn_col(co, irn) arch_register_get_index(arch_get_irn_register((co)->aenv, irn)) +#define set_irn_col(co, irn, col) arch_set_irn_register((co)->aenv, irn, arch_register_for_index((co)->cls, col)) +#define is_curr_reg_class(co, irn) (arch_get_irn_reg_class((co)->aenv, irn, -1) == (co)->cls) + +#define MIN(a,b) ((atype == arch_register_req_type_should_be_same) + + +/****************************************************************************** + ____ _ _ _ _ _ _____ _ + / __ \ | | | | | | (_) | / ____| | + | | | |_ __ | |_| | | |_ __ _| |_ ___ | (___ | |_ ___ _ __ __ _ __ _ ___ + | | | | '_ \| __| | | | '_ \| | __/ __| \___ \| __/ _ \| '__/ _` |/ _` |/ _ \ + | |__| | |_) | |_| |__| | | | | | |_\__ \ ____) | || (_) | | | (_| | (_| | __/ + \____/| .__/ \__|\____/|_| |_|_|\__|___/ |_____/ \__\___/|_| \__,_|\__, |\___| + | | __/ | + |_| |___/ + ******************************************************************************/ + +#define MIS_HEUR_TRIGGER 8 + typedef struct _unit_t { struct list_head units; /**< chain for all units */ - copy_opt_t *co; /**< the copy_opt this unit belongs to */ + copy_opt_t *co; /**< the copy opt this unit belongs to */ int node_count; /**< size of the nodes array */ ir_node **nodes; /**< [0] is the root-node, others are non interfering args of it. */ int *costs; /**< costs[i] are incurred, if nodes[i] has a different color */ int inevitable_costs; /**< sum of costs of all args interfering with root */ int all_nodes_costs; /**< sum of all costs[i] */ - int min_nodes_costs; /**< a lower bound for the costs in costs[], determined by a max indep. set */ + int min_nodes_costs; /**< a lower bound for the costs in costs[], determined by a max independent set */ int sort_key; /**< maximum costs. controls the order of ou's in the struct list_head units. */ /* for heuristic */ struct list_head queue; /**< list of qn's sorted by weight of qn-mis */ } unit_t; -/* Helpers */ -#define get_irn_col(co, irn) arch_register_get_index(arch_get_irn_register((co)->aenv, irn)) -#define set_irn_col(co, irn, col) arch_set_irn_register((co)->aenv, irn, arch_register_for_index((co)->cls, col)) -#define is_curr_reg_class(co, irn) (arch_get_irn_reg_class((co)->aenv, irn, -1) == (co)->cls) -#define MIN(a,b) ((atype == arch_register_req_type_should_be_same) -/** - * Checks if a node is optimizable, viz. has somthing to do with coalescing - * @param arch The architecture environment - * @param irn The irn to check - * @param req A register_requirement structure (used to check for 2-addr-code) - */ -#define co_is_optimizable(arch, irn, req) (!arch_irn_is_ignore(arch, irn) && (is_Reg_Phi(irn) || is_Perm_Proj(arch, irn) || is_2addr_code(arch, irn, req))) +struct _neighb_t { + neighb_t *next; /** the next neighbour entry*/ + ir_node *irn; /** the neighbour itself */ + int costs; /** the costs of the edge (affinity_node_t->irn, neighb_t->irn) */ +}; -/** - * Checks if the irn is a non-interfering argument of a node which 'is_optimizable' - */ -int co_is_optimizable_arg(const copy_opt_t *co, ir_node *irn); +struct _affinity_node_t { + ir_node *irn; /** a node with affinity edges */ + int degree; /** number of affinity edges in the linked list below */ + neighb_t *neighbours; /** a linked list of all affinity neighbours */ +}; -/** - * Returns the maximal costs possible, i.e. the costs if all - * pairs would be assigned different registers. - */ -int co_get_max_copy_costs(const copy_opt_t *co); -/** - * Returns the inevitable costs, i.e. the costs of - * all copy pairs which interfere. - */ -int co_get_inevit_copy_costs(const copy_opt_t *co); +static INLINE affinity_node_t *get_affinity_info(const copy_opt_t *co, ir_node *irn) { + affinity_node_t find; -/** - * Returns the current costs the copies are causing. - * The result includes inevitable costs and the costs - * of the copies regarding the current register allocation - */ -int co_get_copy_costs(const copy_opt_t *co); + ASSERT_GS_AVAIL(co); + + find.irn = irn; + return set_find(co->nodes, &find, sizeof(find), HASH_PTR(irn)); +} + +#define co_gs_nodes_begin(co) set_first((co)->nodes) +#define co_gs_nodes_next(co) set_next((co)->nodes) +#define co_gs_nodes_break(co) set_break((co)->nodes) +#define co_gs_foreach_aff_node(co, aff_node) for (aff_node = co_gs_nodes_begin(co); aff_node; aff_node = co_gs_nodes_next(co)) + +#define co_gs_foreach_neighb(aff_node, neighb) for (neighb = aff_node->neighbours; neighb; neighb = neighb->next) -/** - * Returns a lower bound for the costs of copies in this ou. - * The result includes inevitable costs and the costs of a - * minimal costs caused by the nodes of the ou. - */ -int co_get_lower_bound(const copy_opt_t *co); #endif