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