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 #ifndef _BECOPYOPT_H
  11 #define _BECOPYOPT_H
  12
  13 #include "debug.h"
  14 #include "obst.h"
  15 #include "list.h"
  16 #include "set.h"
  17 #include "pset.h"
  18 #include "bitset.h"
  19 #include "sp_matrix.h"
  20
  21 #include "irgraph.h"
  22 #include "irgwalk.h"
  23 #include "irnode.h"
  24 #include "irdom.h"
  25 #include "irouts.h"
  26
  27 #include "beutil.h"
  28 #include "benumb_t.h"
  29 #include "belive_t.h"
  30 #include "bechordal_t.h"
  31 #include "bearch.h"
  32
  33 #define DEBUG_IRG "-scanner.c__init_td__gp"
  34 //TODO is_Perm
  35 #define is_Perm(irn) 0
  36
  37 /**
  38  * Data representing the problem of copy minimization.
  39  */
  40 typedef struct _copy_opt_t {
  41         be_chordal_env_t *chordal_env;
  42         char *name;                                                     /**< ProgName__IrgName__RegClass */
  43         struct list_head units;                         /**< all units to optimize in right order */
  44         pset *roots;                                            /**< used only temporary for detecting multiple appends */
  45         struct obstack ob;
  46 } copy_opt_t;
  47
  48 /**
  49  * A single unit of optimization. Lots of these form a copy-opt problem
  50  */
  51 typedef struct _unit_t {
  52         struct list_head units;         /**< chain for all units */
  53         copy_opt_t *co;                         /**< the copy_opt this unit belongs to */
  54         int interf;                                     /**< number of nodes dropped due to interference */
  55         int node_count;                         /**< size of the nodes array */
  56         ir_node **nodes;                        /**< [0] is the root-node, others are non interfering args of it. */
  57         int ifg_mis_size;                       /**< size of a mis considering only ifg (not coloring conflicts) */
  58
  59         /* for heuristic */
  60         struct list_head queue;         /**< list of (mis/color) sorted by size of mis */
  61 } unit_t;
  62
  63 /* Helpers */
  64 #define set_irn_col(co, irn, col) \
  65         arch_set_irn_register(co->chordal_env->arch_env, irn, 0, arch_register_for_index(co->chordal_env->cls, col))
  66
  67 #define get_irn_col(co, irn) \
  68         arch_register_get_index(arch_get_irn_register(co->chordal_env->arch_env, irn, 0))
  69
  70
  71 /**
  72  * Generate the problem. Collect all infos and optimizable nodes.
  73  */
  74 copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env);
  75
  76 /**
  77  * Free the space...
  78  */
  79 void free_copy_opt(copy_opt_t *co);
  80
  81 /**
  82  * A copy is a proj haning out of perm node
  83  */
  84 #define is_Copy(irn) (is_Proj(irn) && is_Perm(get_Proj_pred(irn)))
  85
  86 /**
  87  * returns the corresponding argument of the perm node for a copy
  88  */
  89 #define get_Copy_src(irn) (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
  90
  91 /**
  92  * Checks if a node is optimizable, viz. is a target of a 'copy-op'
  93  */
  94 #define is_optimizable(irn) (is_Phi(irn) || is_Copy(irn))
  95
  96 /**
  97  * Checks if the irn is a non-interfering argument of a node which 'is_optimizable'
  98  */
  99 int is_optimizable_arg(const copy_opt_t *co, ir_node *irn);
 100
 101
 102 /**
 103  * Returns the current number of copies needed
 104  */
 105 int co_get_copy_count(const copy_opt_t *co);
 106
 107 /**
 108  * Returns a lower bound for the number of copies needed based on interfering
 109  * arguments and the size of a max indep. set (only ifg-edges) of the other args.
 110  */
 111 int co_get_lower_bound(const copy_opt_t *co);
 112
 113 /**
 114  * Returns the number of arguments interfering with their root node. This also
 115  * is a (worse) lower bound for the number of copies needed.
 116  */
 117 int co_get_interferer_count(const copy_opt_t *co);
 118
 119 /**
 120  * Solves the problem using a heuristic approach
 121  */
 122 void co_heur_opt(copy_opt_t *co);
 123
 124 /**
 125  * Solves the problem using mixed integer programming
 126  */
 127 void co_ilp_opt(copy_opt_t *co);
 128
 129 /**
 130  * Checks the register allocation for correctness
 131  */
 132 void co_check_allocation(copy_opt_t *co);
 133
 134 #endif