2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Common stuff used by all ILP formulations.
23 * @author Daniel Grund
27 #ifndef FIRM_BE_BECOPYILP_T_H
28 #define FIRM_BE_BECOPYILP_T_H
30 #include "firm_config.h"
31 #include "firm_types.h"
33 #include "becopyopt_t.h"
35 /******************************************************************************
38 | (___ _ _______ _ __ ___ __| |_ _ ___| |_ _ ___ _ __
39 \___ \| |_ / _ \ | '__/ _ \/ _` | | | |/ __| __| |/ _ \| '_ \
40 ____) | |/ / __/ | | | __/ (_| | |_| | (__| |_| | (_) | | | |
41 |_____/|_/___\___| |_| \___|\__,_|\__,_|\___|\__|_|\___/|_| |_|
43 *****************************************************************************/
45 typedef struct _coloring_suffix_t coloring_suffix_t;
47 struct _coloring_suffix_t {
48 coloring_suffix_t *next;
52 typedef struct _size_red_t {
54 pset *all_removed; /**< All nodes removed during problem size reduction */
55 coloring_suffix_t *col_suff; /**< Coloring suffix. Reverse would be a PEO prefix */
60 * Just prepare. Do nothing yet.
62 size_red_t *new_size_red(copy_opt_t *co);
65 * Checks if a node has already been removed
67 #define sr_is_removed(sr, irn) pset_find_ptr((sr)->all_removed, irn)
70 * Virtually remove all nodes not related to the problem
71 * (simplicial AND not adjacent to a equal-color-edge)
73 void sr_remove(size_red_t *sr);
76 * Virtually reinsert the nodes removed before and color them
78 void sr_reinsert(size_red_t *sr);
83 void free_size_red(size_red_t *sr);
86 * TODO: This search is necessary because during the construction of the
87 * units (ou's) args could be merged and weights are accumulated.
90 static INLINE int co_ilp_get_costs(copy_opt_t *co, ir_node *root, ir_node *arg) {
94 /* search optimization unit for phi */
95 list_for_each_entry(unit_t, curr, &co->units, units)
96 if (curr->nodes[0] == root) {
98 for (i = 1; i < curr->node_count; ++i)
99 if (curr->nodes[i] == arg)
100 return curr->costs[i];
102 assert(0 && "irn must occur in this ou");
105 assert(0 && "phi must be found in a ou");
109 /******************************************************************************
110 _____ _ _____ _ _____
111 / ____| (_) |_ _| | | __ \
112 | | __ ___ _ __ ___ _ __ _ ___ | | | | | |__) |
113 | | |_ |/ _ \ '_ \ / _ \ '__| |/ __| | | | | | ___/
114 | |__| | __/ | | | __/ | | | (__ _| |_| |____| |
115 \_____|\___|_| |_|\___|_| |_|\___| |_____|______|_|
117 *****************************************************************************/
122 #define LPP_SOLVE_NET
125 # include <lpp/lpp_net.h>
127 # include <lpp/lpp_cplex.h>
130 #define EPSILON 0.00001
132 typedef struct _ilp_env_t ilp_env_t;
134 typedef void(*ilp_callback)(ilp_env_t*);
137 const copy_opt_t *co; /**< the copy opt problem */
138 size_red_t *sr; /**< problem size reduction. removes simple nodes */
139 lpp_t *lp; /**< the linear programming problem */
145 ilp_env_t *new_ilp_env(copy_opt_t *co, ilp_callback build, ilp_callback apply, void *env);
147 lpp_sol_state_t ilp_go(ilp_env_t *ienv);
149 void free_ilp_env(ilp_env_t *ienv);
152 #define name_cdd(buf, char1, int1, int2) \
153 (snprintf(buf, sizeof(buf), "%c_%d_%d", char1, int1, int2), buf)
155 #define name_cdd_sorted(buf, char1, int1, int2) \
156 name_cdd(buf, char1, MIN(int1, int2), MAX(int1, int2))
158 #endif /* WITH_ILP */
160 #endif /* FIRM_BE_BECOPYILP_T_H */