2 * Header for copy optimization problem. Analysis and set up of the problem.
17 #include <sys/types.h>
26 #include "sp_matrix.h"
37 #include "bechordal_t.h"
40 * TODO THIS EXTERNAL THINGS
41 * define get_weight to sth representing the _gain_ if node n and m
42 * have the same color. Must return values MIN_WEIGHT <= . <= MAX_WEIGHT.
44 #define get_weight(n,m) 1
45 #define is_possible_color(irn, col) 1
49 * A single unit of optimization. Lots of these form a copy-opt problem
51 typedef struct _unit_t {
52 struct list_head units; /**< chain for all units */
53 int interf; /**< number of nodes dropped due to interference */
54 int node_count; /**< size of the nodes array */
55 const ir_node **nodes; /**< [0] is the root-node, others are non interfering args of it. */
58 int mis_size; /**< size of a mis considering only ifg (not coloring conflicts) */
59 struct list_head queue; /**< list of (mis/color) sorted by size of mis */
63 * Data representing the problem of copy minimization.
65 typedef struct _copy_opt_t {
66 ir_graph *irg; /**< the irg which is processed */
67 struct list_head units; /**< all units to optimize in right oreder */
68 pset *roots; /**< used only temporary for detecting multiple appends */
71 pset *pinned_global; /**< optimized nodes should not be altered any more */
76 * Generate the problem. Collect all infos and optimizable nodes.
78 copy_opt_t *new_copy_opt(ir_graph *irg);
83 void free_copy_opt(copy_opt_t *co);
86 * Returns a lower bound for the number of copies needed based on interfering
87 * arguments and the size of a max indep. set (only ifg-edges) of the other args.
89 int co_get_lower_bound(copy_opt_t *co);
92 * Returns the number of arguments interfering with their root node. This also
93 * is a (worse) lower bound for the number of copies needed.
95 int co_get_interferer_count(copy_opt_t *co);
98 * Solves the problem using a heuristic approach
100 void co_heur_opt(copy_opt_t *co);
103 * Solves the problem using mixed integer programming
105 void co_ilp_opt(copy_opt_t *co);