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 static INLINE
  50 sched_timestep_t get_time_step(const ir_node *irn)
  51 {
  52         if(is_Phi(irn))
  53                 return 0;
  54
  55         return sched_get_time_step(irn);
  56 }
  57
  58 int value_dominates_intrablock(const ir_node *a, const ir_node *b)
  59 {
  60         sched_timestep_t as = get_time_step(a);
  61         sched_timestep_t bs = get_time_step(b);
  62
  63         return as <= bs;
  64 }
  65
  66 int value_dominates(const ir_node *a, const ir_node *b)
  67 {
  68         const ir_node *block_a = get_block(a);
  69         const ir_node *block_b = get_block(b);
  70
  71         /*
  72          * a and b are not in the same block,
  73          * so dominance is determined by the dominance of the blocks.
  74          */
  75         if(block_a != block_b) {
  76                 return block_dominates(block_a, block_b);
  77         }
  78
  79         /*
  80          * Dominance is determined by the time steps of the schedule.
  81          */
  82         return value_dominates_intrablock(a, b);
  83 }
  84
  85 /**
  86  * Check, if two values interfere.
  87  * @param a The first value.
  88  * @param b The second value.
  89  * @return 1, if a and b interfere, 0 if not.
  90  */
  91 int values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  92 {
  93         int a2b = value_dominates(a, b);
  94         int b2a = value_dominates(b, a);
  95
  96         /* If there is no dominance relation, they do not interfere. */
  97         if((a2b | b2a) > 0) {
  98                 const ir_edge_t *edge;
  99                 ir_node *bb;
 100
 101                 /*
 102                  * Adjust a and b so, that a dominates b if
 103                  * a dominates b or vice versa.
 104                  */
 105                 if(b2a) {
 106                         const ir_node *t = a;
 107                         a = b;
 108                         b = t;
 109                 }
 110
 111                 bb = get_nodes_block(b);
 112
 113                 /*
 114                  * If a is live end in b's block it is
 115                  * live at b's definition (a dominates b)
 116                  */
 117                 if(be_is_live_end(lv, bb, a))
 118                         return 1;
 119
 120                 /*
 121                  * Look at all usages of a.
 122                  * If there's one usage of a in the block of b, then
 123                  * we check, if this use is dominated by b, if that's true
 124                  * a and b interfere. Note that b must strictly dominate the user,
 125                  * since if b is the last user of in the block, b and a do not
 126                  * interfere.
 127                  * Uses of a not in b's block can be disobeyed, because the
 128                  * check for a being live at the end of b's block is already
 129                  * performed.
 130                  */
 131                 foreach_out_edge(a, edge) {
 132                         const ir_node *user = get_edge_src_irn(edge);
 133                         if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && value_dominates(b, user))
 134                                 return 1;
 135                 }
 136         }
 137
 138         return 0;
 139 }
 140
 141 /** The list of register allocators */
 142 static be_module_list_entry_t *register_allocators = NULL;
 143 static be_ra_t *selected_allocator = NULL;
 144
 145 void be_register_allocator(const char *name, be_ra_t *allocator)
 146 {
 147         if(selected_allocator == NULL)
 148                 selected_allocator = allocator;
 149         be_add_module_to_list(&register_allocators, name, allocator);
 150 }
 151
 152 void be_allocate_registers(be_irg_t *birg)
 153 {
 154         assert(selected_allocator != NULL);
 155         if(selected_allocator != NULL) {
 156                 selected_allocator->allocate(birg);
 157         }
 158 }
 159
 160 void be_init_ra(void)
 161 {
 162         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 163
 164         be_add_module_list_opt(be_grp, "regalloc", "register allocator",
 165                                &register_allocators, (void**) &selected_allocator);
 166 }
 167 BE_REGISTER_MODULE_CONSTRUCTOR(init_be_ra);