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 "pset.h"
  11 #include "impl.h"
  12
  13 #include "irnode.h"
  14 #include "irmode.h"
  15 #include "irdom.h"
  16
  17 #include "bera_t.h"
  18 #include "besched_t.h"
  19 #include "belive_t.h"
  20
  21 FIRM_IMPL1(is_allocatable_irn, int, const ir_node *)
  22
  23 size_t ra_irn_data_offset = 0;
  24 size_t ra_irg_data_offset = 0;
  25
  26 void be_ra_init(void)
  27 {
  28         ra_irn_data_offset = register_additional_node_data(sizeof(ra_info_t));
  29         ra_irg_data_offset = register_additional_graph_data(sizeof(void *));
  30 }
  31
  32 static INLINE int values_interfere_dom(const ir_node *a, const ir_node *b)
  33 {
  34         const ir_node *b1 = get_nodes_block(a);
  35         const ir_node *b2 = get_nodes_block(b);
  36         int lo_a, lo_b;
  37
  38         assert(block_dominates(b1, b2));
  39
  40         /*
  41          * if the two blocks are not equal, a and b can only interfere if a is
  42          * live in at b2.
  43          */
  44         if(b1 != b2 && !is_live_in(b2, a))
  45                 return 0;
  46
  47         lo_a = is_live_end(b2, a);
  48         lo_b = is_live_end(b2, b);
  49
  50         /*
  51          * If the two blocks are the same and one value is live out and the
  52          * definition of the other is after the definition ov the live out
  53          * value, they interfere.
  54          */
  55         if(b1 == b2) {
  56                 int pos_a = sched_get_time_step(a);
  57                 int pos_b = sched_get_time_step(b);
  58
  59                 if((pos_a < pos_b && lo_a) || (pos_b < pos_a && lo_b))
  60                         return 1;
  61         }
  62
  63         /*
  64          * Now it is left to check, if the sequence from the last use of 'b'
  65          * (or the end of the block b2, if b is live out)
  66          * to the def of 'b' contains a use and NOT the def of 'a'. Then they
  67          * also interfere
  68          */
  69         {
  70                 const ir_node *irn;
  71
  72                 /* Initialize the liveness. */
  73                 int a_live = lo_a;
  74                 int b_live = lo_b;
  75
  76                 /* Go from the end of block b2 and try to detect the liveness. */
  77                 sched_foreach_reverse(b2, irn) {
  78                         int i, n;
  79
  80                         /*
  81                          * If the definition of 'a' was found 'a' and 'b' interfere, if
  82                          * 'b' is live here.
  83                          */
  84                         if(irn == a)
  85                                 return b_live;
  86
  87                         /* Same goes for 'b'. */
  88                         if(irn == b)
  89                                 return a_live;
  90
  91                         /* If 'a' is not yet live, search for a use. */
  92                         if(!a_live) {
  93                                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
  94                                         if(get_irn_n(irn, i) == a) {
  95                                                 a_live = 1;
  96                                                 break;
  97                                 }
  98                         }
  99
 100                         /* Same for 'b' */
 101                         if(!b_live) {
 102                                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
 103                                         if(get_irn_n(irn, i) == b) {
 104                                                 b_live = 1;
 105                                                 break;
 106                                         }
 107                         }
 108
 109                 }
 110         }
 111
 112         assert(0 && "You may never reach this place");
 113
 114         /* This is never reached */
 115         return 0;
 116 }
 117
 118 int values_interfere(const ir_node *a, const ir_node *b)
 119 {
 120         const ir_node *b1 = get_nodes_block(a);
 121         const ir_node *b2 = get_nodes_block(b);
 122
 123         if(block_dominates(b1, b2))
 124                 return values_interfere_dom(a, b);
 125         else if(block_dominates(b2, b1))
 126                 return values_interfere_dom(b, a);
 127         else
 128                 return 0;
 129 }