nsz Git - libfirm/blob - ir/be/becopyopt.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       Copy minimization driver.
  23  * @author      Daniel Grund
  24  * @date        11.04.2005
  25  *
  26  * Main file for the optimization reducing the copies needed for:
  27  * - Phi coalescing
  28  * - Register-constrained nodes
  29  * - Two-address code instructions
  30  */
  31 #ifndef FIRM_BE_BECOPYOPT_H
  32 #define FIRM_BE_BECOPYOPT_H
  33
  34 #include <stdio.h>
  35 #include <stdbool.h>
  36
  37 #include "firm_types.h"
  38 #include "be_types.h"
  39 #include "bechordal.h"
  40 #include "beutil.h"
  41
  42 typedef int(*cost_fct_t)(const ir_node *node, int input);
  43
  44 typedef struct {
  45         int (*copyopt)(copy_opt_t *co); /**< function ptr to run copyopt */
  46         bool can_improve_existing;
  47 } co_algo_info;
  48
  49 /**
  50  * Register a new copy optimization algorithm.
  51  *
  52  * @param name     the name of the copy optimazation algorithm,
  53  *                 used to select it
  54  * @param copyopt  a copy optimazation entry
  55  */
  56 void be_register_copyopt(const char *name, co_algo_info *copyopt);
  57
  58 /** The driver for copy minimization. */
  59 void co_driver(be_chordal_env_t *cenv);
  60
  61 /**
  62  * Generate the problem. Collect all information and optimizable nodes.
  63  */
  64 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs);
  65
  66 /**
  67  * Free the space used...
  68  */
  69 void free_copy_opt(copy_opt_t *co);
  70
  71 /**
  72  * Statistics over a copy optimization module.
  73  */
  74 typedef struct {
  75         unsigned long long aff_edges;            /**< number of affinity edges. */
  76         unsigned long long aff_nodes;            /**< number of nodes with incident affinity edges. */
  77         unsigned long long aff_int;              /**< number of affinity edges whose nodes also interfere. */
  78         unsigned long long inevit_costs;         /**< costs which cannot be evited (due to interfering affinities). */
  79         unsigned long long max_costs;            /**< all costs of the affinities. */
  80         unsigned long long costs;                /**< The costs of the current coloring. */
  81         unsigned long long unsatisfied_edges;    /**< The number of unequally colored affinity edges. */
  82 } co_complete_stats_t;
  83
  84 /**
  85  * Collect statistics of a copy optimization module.
  86  * @param co    The copy optimization environment.
  87  * @param stat  Where to put the stats.
  88  * @note  This requires the graph info to be computed.
  89  */
  90 void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat);
  91
  92
  93 /**
  94  * Build internal optimization units structure
  95  */
  96 void co_build_ou_structure(copy_opt_t *co);
  97
  98 /**
  99  * Frees the space used by the opt unit representation.
 100  * Does NOT free the whole copyopt structure
 101  */
 102 void co_free_ou_structure(copy_opt_t *co);
 103
 104 /**
 105  * Solves the problem using a heuristic approach
 106  * Uses the OU data structure
 107  */
 108 int co_solve_heuristic(copy_opt_t *co);
 109
 110 /**
 111  * Returns the maximal costs possible, i.e. the costs if all
 112  * pairs would be assigned different registers.
 113  * Uses the OU data structure
 114  */
 115 int co_get_max_copy_costs(const copy_opt_t *co);
 116
 117 /**
 118  * Returns the inevitable costs, i.e. the costs of
 119  * all copy pairs which interfere.
 120  * Uses the OU data structure
 121  */
 122 int co_get_inevit_copy_costs(const copy_opt_t *co);
 123
 124 /**
 125  * Returns the current costs the copies are causing.
 126  * The result includes inevitable costs and the costs
 127  * of the copies regarding the current register allocation
 128  * Uses the OU data structure
 129  */
 130 int co_get_copy_costs(const copy_opt_t *co);
 131
 132 /**
 133  * Returns a lower bound for the costs of copies in this ou.
 134  * The result includes inevitable costs and the costs of a
 135  * minimal costs caused by the nodes of the ou.
 136  * Uses the OU data structure
 137  */
 138 int co_get_lower_bound(const copy_opt_t *co);
 139
 140 /**
 141  * Constructs another internal representation of the affinity edges
 142  */
 143 void co_build_graph_structure(copy_opt_t *co);
 144
 145 /**
 146  * Frees the space used by the graph representation.
 147  * Does NOT free the whole copyopt structure
 148  */
 149 void co_free_graph_structure(copy_opt_t *co);
 150
 151 /**
 152  * Checks if a node is optimizable, viz has something to do with coalescing.
 153  * Uses the GRAPH data structure
 154  */
 155 int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn);
 156
 157 #endif