nsz Git - libfirm/blob - ir/be/becopyilp_t.h

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * Author:      Daniel Grund
  22  * Date:                28.02.2006
  23  * Copyright:   (c) Universitaet Karlsruhe
  24  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  25  *
  26  * Common stuff used by all ILP fomulations.
  27  *
  28  */
  29
  30 #ifndef _BECOPYILP_T_H
  31 #define _BECOPYILP_T_H
  32
  33 #include "firm_config.h"
  34
  35 #include "irnode_t.h"
  36 #include "pset.h"
  37 #include "becopyopt_t.h"
  38 #include "xmalloc.h"
  39
  40 /******************************************************************************
  41     _____ _                        _            _   _
  42    / ____(_)                      | |          | | (_)
  43   | (___  _ _______   _ __ ___  __| |_   _  ___| |_ _  ___  _ __
  44    \___ \| |_  / _ \ | '__/ _ \/ _` | | | |/ __| __| |/ _ \| '_ \
  45    ____) | |/ /  __/ | | |  __/ (_| | |_| | (__| |_| | (_) | | | |
  46   |_____/|_/___\___| |_|  \___|\__,_|\__,_|\___|\__|_|\___/|_| |_|
  47
  48  *****************************************************************************/
  49
  50 typedef struct _coloring_suffix_t coloring_suffix_t;
  51
  52 struct _coloring_suffix_t {
  53         coloring_suffix_t *next;
  54         ir_node *irn;
  55 };
  56
  57 typedef struct _size_red_t {
  58         copy_opt_t *co;
  59         pset *all_removed;                              /**< All nodes removed during problem size reduction */
  60         coloring_suffix_t *col_suff;    /**< Coloring suffix. Reverse would be a PEO prefix */
  61         struct obstack ob;
  62 } size_red_t;
  63
  64 /**
  65  * Just prepare. Do nothing yet.
  66  */
  67 size_red_t *new_size_red(copy_opt_t *co);
  68
  69 /**
  70  * Checks if a node has already been removed
  71  */
  72 #define sr_is_removed(sr, irn)          pset_find_ptr((sr)->all_removed, irn)
  73
  74 /**
  75  * Virtually remove all nodes not related to the problem
  76  * (simplicial AND not adjacent to a equal-color-edge)
  77  */
  78 void sr_remove(size_red_t *sr);
  79
  80 /**
  81  * Virtually reinsert the nodes removed before and color them
  82  */
  83 void sr_reinsert(size_red_t *sr);
  84
  85 /**
  86  * Free all space...
  87  */
  88 void free_size_red(size_red_t *sr);
  89
  90 /**
  91  * TODO: This search is necessary because during the construction of the
  92  *       units (ou's) args could be merged and weights are accumulated.
  93  *       Is this necessary?
  94  */
  95 static INLINE int co_ilp_get_costs(copy_opt_t *co, ir_node *root, ir_node *arg) {
  96         int i;
  97         unit_t *curr;
  98
  99         /* search optimization unit for phi */
 100         list_for_each_entry(unit_t, curr, &co->units, units)
 101                 if (curr->nodes[0] == root) {
 102
 103                         for (i=1; i<curr->node_count; ++i)
 104                                 if (curr->nodes[i] == arg)
 105                                         return curr->costs[i];
 106
 107                                 assert(0 && "irn must occur in this ou");
 108                 }
 109
 110         assert(0 && "phi must be found in a ou");
 111         return 0;
 112 }
 113
 114 /******************************************************************************
 115     _____                      _        _____ _      _____
 116    / ____|                    (_)      |_   _| |    |  __ \
 117   | |  __  ___ _ __   ___ _ __ _  ___    | | | |    | |__) |
 118   | | |_ |/ _ \ '_ \ / _ \ '__| |/ __|   | | | |    |  ___/
 119   | |__| |  __/ | | |  __/ |  | | (__   _| |_| |____| |
 120    \_____|\___|_| |_|\___|_|  |_|\___| |_____|______|_|
 121
 122  *****************************************************************************/
 123
 124 #ifdef WITH_ILP
 125 #include <lpp/lpp.h>
 126
 127 #define LPP_SOLVE_NET
 128
 129 #ifdef LPP_SOLVE_NET
 130 #  include <lpp/lpp_net.h>
 131 #else
 132 #  include <lpp/lpp_cplex.h>
 133 #endif
 134
 135 #define EPSILON 0.00001
 136
 137 typedef struct _ilp_env_t ilp_env_t;
 138
 139 typedef void(*ilp_callback)(ilp_env_t*);
 140
 141 struct _ilp_env_t {
 142         const copy_opt_t *co;                   /**< the copy opt problem */
 143         size_red_t *sr;                                 /**< problem size reduction. removes simple nodes */
 144         lpp_t *lp;                                              /**< the linear programming problem */
 145         void *env;
 146         ilp_callback build;
 147         ilp_callback apply;
 148 };
 149
 150 ilp_env_t *new_ilp_env(copy_opt_t *co, ilp_callback build, ilp_callback apply, void *env);
 151
 152 lpp_sol_state_t ilp_go(ilp_env_t *ienv);
 153
 154 void free_ilp_env(ilp_env_t *ienv);
 155
 156
 157 #define name_cdd(buf, char1, int1, int2) \
 158                         (snprintf(buf, sizeof(buf), "%c_%d_%d", char1, int1, int2), buf)
 159
 160 #define name_cdd_sorted(buf, char1, int1, int2) \
 161                         name_cdd(buf, char1, MIN(int1, int2), MAX(int1, int2))
 162
 163 #endif // WITH_ILP
 164
 165 #endif