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 int value_dominates(const ir_node *a, const ir_node *b)
  22 {
  23   int res = 0;
  24         const ir_node *ba = get_block(a);
  25         const ir_node *bb = get_block(b);
  26
  27   /*
  28    * a and b are not in the same block,
  29    * so dominance is determined by the dominance of the blocks.
  30    */
  31   if(ba != bb)
  32     res = block_dominates(ba, bb);
  33
  34   /*
  35    * Dominance is determined by the time steps of the schedule.
  36    */
  37   else {
  38     sched_timestep_t as = sched_get_time_step(a);
  39     sched_timestep_t bs = sched_get_time_step(b);
  40     res = as <= bs;
  41   }
  42
  43   return res;
  44 }
  45
  46 /**
  47  * Check, if two values interfere.
  48  * @param a The first value.
  49  * @param b The second value.
  50  * @return 1, if a and b interfere, 0 if not.
  51  */
  52 int values_interfere(const ir_node *a, const ir_node *b)
  53 {
  54   int a2b = value_dominates(a, b);
  55   int b2a = value_dominates(b, a);
  56
  57   /*
  58    * Adjust a and b so, that a dominates b if
  59    * a dominates b or vice versa.
  60    */
  61   if(b2a) {
  62     const ir_node *t = a;
  63     a = b;
  64     b = t;
  65   }
  66
  67   /*
  68    * If either a dmoninates b or vice versa
  69    * check if there is usage which is dominated by b.
  70    *
  71    * remind, that if a and b are in a dom relation, a always dominates b
  72    * here due to the if above.
  73    */
  74   if(a2b + b2a) {
  75     const ir_edge_t *edge;
  76
  77     /* Look at all usages of a */
  78     foreach_out_edge(a, edge) {
  79       const ir_node *user = edge->src;
  80
  81       /*
  82        * If the user is a phi we must check the last instruction in the
  83        * corresponding phi predecessor block since the phi is not a
  84        * proper user.
  85        */
  86       if(is_Phi(user)) {
  87         ir_node *phi_block = get_nodes_block(user);
  88         user = sched_last(get_Block_cfgpred_block(phi_block, edge->pos));
  89       }
  90
  91       /* If b dominates a user of a, we can safely return 1 here. */
  92       if(value_dominates(b, user))
  93         return 1;
  94     }
  95
  96   }
  97
  98   return 0;
  99 }