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 "beutil.h"
  18 #include "besched_t.h"
  19 #include "belive_t.h"
  20
  21 static sched_timestep_t get_time_step(const ir_node *irn)
  22 {
  23         if(is_Phi(irn))
  24                 return 0;
  25
  26         return sched_get_time_step(irn);
  27 }
  28
  29 int value_dominates(const ir_node *a, const ir_node *b)
  30 {
  31         int res = 0;
  32         const ir_node *ba = get_block(a);
  33         const ir_node *bb = get_block(b);
  34
  35         /*
  36          * a and b are not in the same block,
  37          * so dominance is determined by the dominance of the blocks.
  38          */
  39         if(ba != bb) {
  40                 res = block_dominates(ba, bb);
  41
  42         /*
  43          * Dominance is determined by the time steps of the schedule.
  44          */
  45         } else {
  46                 sched_timestep_t as = get_time_step(a);
  47                 sched_timestep_t bs = get_time_step(b);
  48                 res = as <= bs;
  49         }
  50
  51         return res;
  52 }
  53
  54 /**
  55  * Check, if two values interfere.
  56  * @param a The first value.
  57  * @param b The second value.
  58  * @return 1, if a and b interfere, 0 if not.
  59  */
  60 int values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  61 {
  62         int a2b = value_dominates(a, b);
  63         int b2a = value_dominates(b, a);
  64
  65         /* If there is no dominance relation, they do not interfere. */
  66         if((a2b | b2a) > 0) {
  67                 const ir_edge_t *edge;
  68                 ir_node *bb;
  69
  70                 /*
  71                  * Adjust a and b so, that a dominates b if
  72                  * a dominates b or vice versa.
  73                  */
  74                 if(b2a) {
  75                         const ir_node *t = a;
  76                         a = b;
  77                         b = t;
  78                 }
  79
  80                 bb = get_nodes_block(b);
  81
  82                 /*
  83                  * If a is live end in b's block it is
  84                  * live at b's definition (a dominates b)
  85                  */
  86                 if(be_is_live_end(lv, bb, a))
  87                         return 1;
  88
  89                 /*
  90                  * Look at all usages of a.
  91                  * If there's one usage of a in the block of b, then
  92                  * we check, if this use is dominated by b, if that's true
  93                  * a and b interfere. Note that b must strictly dominate the user,
  94                  * since if b is the last user of in the block, b and a do not
  95                  * interfere.
  96                  * Uses of a not in b's block can be disobeyed, because the
  97                  * check for a being live at the end of b's block is already
  98                  * performed.
  99                  */
 100                 foreach_out_edge(a, edge) {
 101                         const ir_node *user = get_edge_src_irn(edge);
 102                         if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && value_dominates(b, user))
 103                                 return 1;
 104                 }
 105   }
 106   return 0;
 107 }