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

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