becopyopt_t.h 3.98 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       Internal header for copy optimization problem.
 * @author      Daniel Grund
 * @date        12.04.2005
11
 */
Christian Würdig's avatar
Christian Würdig committed
12
13
#ifndef FIRM_BE_BECOPYOPT_T_H
#define FIRM_BE_BECOPYOPT_T_H
14

15
#include "obst.h"
16
#include "list.h"
Christian Würdig's avatar
Christian Würdig committed
17
#include "set.h"
18
#include "irnode_t.h"
Christian Würdig's avatar
Christian Würdig committed
19

20
#include "bearch.h"
21
22
23
24
25
26
#include "bechordal_t.h"
#include "becopyopt.h"

/**
 * Data representing the problem of copy minimization.
 */
27
struct copy_opt_t {
Christian Würdig's avatar
Christian Würdig committed
28
	be_chordal_env_t            *cenv;
29
	const arch_register_class_t *cls;
Christian Würdig's avatar
Christian Würdig committed
30
	ir_graph                    *irg;
Matthias Braun's avatar
Matthias Braun committed
31
	cost_fct_t                   get_costs; /**< function ptr used to get costs for copies */
32

Daniel Grund's avatar
Daniel Grund committed
33
	/** Representation as optimization units */
34
	struct list_head units;  /**< all units to optimize in specific order */
Daniel Grund's avatar
Daniel Grund committed
35
36
37

	/** Representation in graph structure. Only build on demand */
	struct obstack obst;
Matthias Braun's avatar
Matthias Braun committed
38
	set           *nodes;
39
40
};

41
42
#define ASSERT_OU_AVAIL(co)     assert((co)->units.next && "Representation as optimization-units not built")
#define ASSERT_GS_AVAIL(co)     assert((co)->nodes && "Representation as graph not built")
Daniel Grund's avatar
Daniel Grund committed
43

Matthias Braun's avatar
Matthias Braun committed
44
45
static inline unsigned get_irn_col(const ir_node *node)
{
46
	return arch_get_irn_register(node)->index;
Matthias Braun's avatar
Matthias Braun committed
47
48
49
50
51
52
53
54
}

static inline void set_irn_col(const arch_register_class_t *cls, ir_node *node,
                               unsigned color)
{
	const arch_register_t *reg = arch_register_for_index(cls, color);
	arch_set_irn_register(node, reg);
}
Daniel Grund's avatar
Daniel Grund committed
55

56
#define get_Perm_src(irn) (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
57
#define is_Perm_Proj(irn) (is_Proj(irn) && be_is_Perm(get_Proj_pred(irn)))
Daniel Grund's avatar
Daniel Grund committed
58

Matthias Braun's avatar
Matthias Braun committed
59
60
61
62
63
64
/**
 * Returns the inevitable costs, i.e. the costs of
 * all copy pairs which interfere.
 * Uses the OU data structure
 */
int co_get_inevit_copy_costs(const copy_opt_t *co);
Daniel Grund's avatar
Daniel Grund committed
65

Matthias Braun's avatar
Matthias Braun committed
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 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.
 * Uses the OU data structure
 */
int co_get_lower_bound(const copy_opt_t *co);

/**
 * Checks if a node is optimizable, viz has something to do with coalescing.
 * Uses the GRAPH data structure
 */
bool co_gs_is_optimizable(copy_opt_t const *co, ir_node *irn);
Daniel Grund's avatar
Daniel Grund committed
79

80
typedef struct unit_t {
Matthias Braun's avatar
Matthias Braun committed
81
82
83
84
85
86
87
88
	struct list_head units;            /**< chain for all units */
	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 independent set */
	int              sort_key;         /**< maximum costs. controls the order of ou's in the struct list_head units. */
89
90

	/* for heuristic */
Matthias Braun's avatar
Matthias Braun committed
91
	struct list_head queue;            /**< list of qn's sorted by weight of qn-mis */
92
93
} unit_t;

Matthias Braun's avatar
Matthias Braun committed
94
typedef struct neighb_t        neighb_t;
95
typedef struct affinity_node_t affinity_node_t;
96

97
struct neighb_t {
Matthias Braun's avatar
Matthias Braun committed
98
99
100
	neighb_t      *next;  /** the next neighbour entry*/
	const ir_node *irn;   /** the neighbour itself */
	int            costs; /** the costs of the edge (affinity_node_t->irn, neighb_t->irn) */
Daniel Grund's avatar
Daniel Grund committed
101
};
102

103
struct affinity_node_t {
Matthias Braun's avatar
Matthias Braun committed
104
105
	const ir_node  *irn;        /** a node with affinity edges */
	neighb_t       *neighbours; /** a linked list of all affinity neighbours */
106
107
};

108

109
110
static inline affinity_node_t *get_affinity_info(const copy_opt_t *co, const ir_node *irn)
{
Daniel Grund's avatar
Daniel Grund committed
111
	ASSERT_GS_AVAIL(co);
112

Matthias Braun's avatar
Matthias Braun committed
113
	affinity_node_t find;
114
	find.irn = irn;
115
	return set_find(affinity_node_t, co->nodes, &find, sizeof(find), hash_irn(irn));
116
117
}

118
#define co_gs_foreach_aff_node(co, aff_node)     foreach_set((co)->nodes, affinity_node_t, (aff_node))
119
#define co_gs_foreach_neighb(aff_node, neighb)   for (neighb_t *neighb = aff_node->neighbours; neighb; neighb = neighb->next)
120

Matthias Braun's avatar
Matthias Braun committed
121
#endif