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

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