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

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                12.04.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  *
   7  * Header for copy optimization problem. Analysis and set up of the problem.
   8  */
   9
  10 /*
  11  * TODO: get_nodes_block(get_irn_n(get_nodes_block(phi), i)); --> get_ifgblock_nodeblock
  12  */
  13
  14 #ifndef _BECOPYOPT_H
  15 #define _BECOPYOPT_H
  16
  17 #include "debug.h"
  18 #include "obst.h"
  19 #include "list.h"
  20 #include "set.h"
  21 #include "pset.h"
  22 #include "bitset.h"
  23 #include "sp_matrix.h"
  24
  25 #include "irgraph.h"
  26 #include "irgwalk.h"
  27 #include "irnode.h"
  28 #include "irdom.h"
  29 #include "irouts.h"
  30
  31 #include "beutil.h"
  32 #include "benumb_t.h"
  33 #include "belive_t.h"
  34 #include "bechordal_t.h"
  35 #include "bearch.h"
  36
  37 #define DEBUG_IRG "NONE spec.c__main__datab"
  38 #define DEBUG_LVL_CO   LEVEL_1
  39 #define DEBUG_LVL_HEUR LEVEL_1
  40 #define DEBUG_LVL_ILP  LEVEL_1
  41
  42 typedef int(*cost_fct_t)(ir_node*, ir_node*, int);
  43
  44 /**
  45  * Data representing the problem of copy minimization.
  46  */
  47 typedef struct _copy_opt_t {
  48         be_chordal_env_t *chordal_env;
  49         char *name;                                             /**< ProgName__IrgName__RegClass */
  50         struct list_head units;                 /**< all units to optimize in right order */
  51         pset *roots;                                    /**< used only temporary for detecting multiple appends */
  52         cost_fct_t get_costs;                   /**< function ptr used to get costs for copies */
  53         struct obstack ob;
  54 } copy_opt_t;
  55
  56 /**
  57  * A single unit of optimization. Lots of these form a copy-opt problem
  58  */
  59 typedef struct _unit_t {
  60         struct list_head units;         /**< chain for all units */
  61         copy_opt_t *co;                         /**< the copy_opt this unit belongs to */
  62         int node_count;                         /**< size of the nodes array */
  63         ir_node **nodes;                        /**< [0] is the root-node, others are non interfering args of it. */
  64         int *costs;                                     /**< costs[i] are arising, if nodes[i] has a different color */
  65         int complete_costs;                     /**< sum of all costs[i] */
  66         int minimal_costs;                      /**< a lower bound for this ou, considering only ifg (not coloring conflicts) */
  67
  68         //TODO Think of the ordering.
  69         int avg_costs;                          /**< average costs. controls the order of ou's. */
  70
  71         /* for heuristic */
  72         struct list_head queue;         /**< list of (mis/color) sorted by size of mis */
  73 } unit_t;
  74
  75 /* Helpers */
  76 #define set_irn_col(co, irn, col) \
  77         arch_set_irn_register(co->chordal_env->arch_env, irn, 0, arch_register_for_index(co->chordal_env->cls, col))
  78
  79 #define get_irn_col(co, irn) \
  80         arch_register_get_index(arch_get_irn_register(co->chordal_env->arch_env, irn, 0))
  81
  82 #define list_entry_units(lh) list_entry(lh, unit_t, units)
  83
  84
  85 /**
  86  * Generate the problem. Collect all infos and optimizable nodes.
  87  */
  88 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, int (*get_costs)(ir_node*, ir_node*, int));
  89
  90 /**
  91  * Free the space...
  92  */
  93 void free_copy_opt(copy_opt_t *co);
  94
  95
  96 #define is_Perm(arch_env, irn) (arch_irn_classify(arch_env, irn) == arch_irn_class_perm)
  97
  98 /**
  99  * A copy is a proj haning out of perm node
 100  */
 101 #define is_Copy(arch_env, irn) (is_Proj(irn) && is_Perm(arch_env, get_Proj_pred(irn)))
 102
 103 /**
 104  * returns the corresponding argument of the perm node for a copy
 105  */
 106 #define get_Copy_src(irn) (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
 107
 108 /**
 109  * Checks if a node is optimizable, viz. is a target of a 'copy-op'
 110  */
 111 #define is_optimizable(arch_env, irn) (is_Phi(irn) || is_Copy(arch_env, irn))
 112
 113 /**
 114  * Checks if the irn is a non-interfering argument of a node which 'is_optimizable'
 115  */
 116 int is_optimizable_arg(const copy_opt_t *co, ir_node *irn);
 117
 118 /**
 119  * Computes the costs of a copy according to loop depth
 120  * @param root, arg: clear.
 121  * @param pos:  -1 for perm-copies.
 122  *                              Else the argument position of arg in the phi node root.
 123  * @return Must be >= 0 in all cases.
 124  */
 125 int get_costs_loop_depth(ir_node *root, ir_node* arg, int pos);
 126
 127 /**
 128  * All costs equal 1. Using this will reduce the number of copies.
 129  * @return Must be >= 0 in all cases.
 130  */
 131 int get_costs_all_one(ir_node *root, ir_node* arg, int pos);
 132
 133 /**
 134  * Returns the current costs the copies are causing
 135  */
 136 int co_get_copy_costs(const copy_opt_t *co);
 137
 138 /**
 139  * Returns a lower bound for the costs of copies based on interfering
 140  * arguments and the size of a max indep. set (only ifg-edges) of the other args.
 141  */
 142 int co_get_lower_bound(const copy_opt_t *co);
 143
 144 /**
 145  * Solves the problem using a heuristic approach
 146  */
 147 void co_heur_opt(copy_opt_t *co);
 148
 149 /**
 150  * Solves the problem using mixed integer programming
 151  */
 152 void co_ilp_opt(copy_opt_t *co);
 153
 154 #endif