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

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