nsz Git - libfirm/blob - ir/be/bera.c

   1 /*
   2  * Copyright (C) 1995-2007 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       Base routines for register allocation.
  23  * @author      Sebastian Hack
  24  * @date        22.11.2004
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <stdlib.h>
  32
  33 #include "pset.h"
  34 #include "impl.h"
  35
  36 #include "irnode.h"
  37 #include "irmode.h"
  38 #include "irdom.h"
  39 #include "iredges.h"
  40
  41 #include "bera.h"
  42 #include "beutil.h"
  43 #include "besched_t.h"
  44 #include "belive_t.h"
  45 #include "bemodule.h"
  46
  47 be_ra_timer_t *global_ra_timer = NULL;
  48
  49 #define get_time_step(irn) (is_Phi(irn) ? 0 : sched_get_time_step(irn))
  50
  51 static INLINE int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  52 {
  53         sched_timestep_t as = get_time_step(a);
  54         sched_timestep_t bs = get_time_step(b);
  55         return as <= bs;
  56 }
  57
  58 int value_dominates_intrablock(const ir_node *a, const ir_node *b)
  59 {
  60         return _value_dominates_intrablock(a, b);
  61 }
  62
  63 int value_dominates(const ir_node *a, const ir_node *b)
  64 {
  65         const ir_node *block_a = get_block(a);
  66         const ir_node *block_b = get_block(b);
  67
  68         /*
  69          * a and b are not in the same block,
  70          * so dominance is determined by the dominance of the blocks.
  71          */
  72         if(block_a != block_b) {
  73                 return block_dominates(block_a, block_b);
  74         }
  75
  76         /*
  77          * Dominance is determined by the time steps of the schedule.
  78          */
  79         return _value_dominates_intrablock(a, b);
  80 }
  81
  82 /**
  83  * Check, if two values interfere.
  84  * @param a The first value.
  85  * @param b The second value.
  86  * @return 1, if a and b interfere, 0 if not.
  87  */
  88 int values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  89 {
  90         int a2b = value_dominates(a, b);
  91         int b2a = value_dominates(b, a);
  92
  93         /* If there is no dominance relation, they do not interfere. */
  94         if((a2b | b2a) > 0) {
  95                 const ir_edge_t *edge;
  96                 ir_node *bb;
  97
  98                 /*
  99                  * Adjust a and b so, that a dominates b if
 100                  * a dominates b or vice versa.
 101                  */
 102                 if(b2a) {
 103                         const ir_node *t = a;
 104                         a = b;
 105                         b = t;
 106                 }
 107
 108                 bb = get_nodes_block(b);
 109
 110                 /*
 111                  * If a is live end in b's block it is
 112                  * live at b's definition (a dominates b)
 113                  */
 114                 if(be_is_live_end(lv, bb, a))
 115                         return 1;
 116
 117                 /*
 118                  * Look at all usages of a.
 119                  * If there's one usage of a in the block of b, then
 120                  * we check, if this use is dominated by b, if that's true
 121                  * a and b interfere. Note that b must strictly dominate the user,
 122                  * since if b is the last user of in the block, b and a do not
 123                  * interfere.
 124                  * Uses of a not in b's block can be disobeyed, because the
 125                  * check for a being live at the end of b's block is already
 126                  * performed.
 127                  */
 128                 foreach_out_edge(a, edge) {
 129                         const ir_node *user = get_edge_src_irn(edge);
 130                         if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && value_dominates(b, user))
 131                                 return 1;
 132                 }
 133         }
 134
 135         return 0;
 136 }
 137
 138 /** The list of register allocators */
 139 static be_module_list_entry_t *register_allocators = NULL;
 140 static be_ra_t *selected_allocator = NULL;
 141
 142 void be_register_allocator(const char *name, be_ra_t *allocator)
 143 {
 144         if(selected_allocator == NULL)
 145                 selected_allocator = allocator;
 146         be_add_module_to_list(&register_allocators, name, allocator);
 147 }
 148
 149 void be_allocate_registers(be_irg_t *birg)
 150 {
 151         assert(selected_allocator != NULL);
 152         if(selected_allocator != NULL) {
 153                 selected_allocator->allocate(birg);
 154         }
 155 }
 156
 157 void be_init_ra(void)
 158 {
 159         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 160
 161         be_add_module_list_opt(be_grp, "regalloc", "register allocator",
 162                                &register_allocators, (void**) &selected_allocator);
 163 }
 164 BE_REGISTER_MODULE_CONSTRUCTOR(init_be_ra);