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