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

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