nsz Git - libfirm/blob - ir/be/beintlive_t.h

   1 /**
   2  * @file   beintlive_t.h
   3  * @date   10.05.2007
   4  * @author Sebastian Hack
   5  *
   6  * Principal routines for liveness and interference checks.
   7  *
   8  * Copyright (C) 2007 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11
  12 #ifndef _BELIVECHK_T_H
  13 #define _BELIVECHK_T_H
  14
  15 #include "irgraph_t.h"
  16 #include "irphase_t.h"
  17 #include "iredges_t.h"
  18
  19 #include "irlivechk.h"
  20
  21 #include "beirg_t.h"
  22 #include "besched_t.h"
  23
  24 /**
  25  * Check dominance of two nodes in the same block.
  26  * @param a The first node.
  27  * @param b The second node.
  28  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  29  */
  30 static INLINE int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  31 {
  32         /* TODO: ? :  can be removed?! */
  33         sched_timestep_t as = is_Phi(a) ? 0 : sched_get_time_step(a);
  34         sched_timestep_t bs = is_Phi(b) ? 0 : sched_get_time_step(b);
  35         return as <= bs;
  36 }
  37
  38 /**
  39  * Check, if one value dominates the other.
  40  * The dominance is not strict here.
  41  * @param a The first node.
  42  * @param b The second node.
  43  * @return 1 if a dominates b or if a == b, 0 else.
  44  */
  45 static INLINE int _value_dominates(const ir_node *a, const ir_node *b)
  46 {
  47         const ir_node *block_a = get_block(a);
  48         const ir_node *block_b = get_block(b);
  49
  50         /*
  51          * a and b are not in the same block,
  52          * so dominance is determined by the dominance of the blocks.
  53          */
  54         if(block_a != block_b) {
  55                 return block_dominates(block_a, block_b);
  56         }
  57
  58         /*
  59          * Dominance is determined by the time steps of the schedule.
  60          */
  61         return _value_dominates_intrablock(a, b);
  62 }
  63
  64 /**
  65  * Check, if two values interfere.
  66  * @param lv Liveness information (in the future we should use a be_irg_t here).
  67  * @param a The first value.
  68  * @param b The second value.
  69  * @return 1, if a and b interfere, 0 if not.
  70  */
  71 static INLINE int _lv_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  72 {
  73         int a2b = _value_dominates(a, b);
  74         int b2a = _value_dominates(b, a);
  75
  76         /* If there is no dominance relation, they do not interfere. */
  77         if((a2b | b2a) > 0) {
  78                 const ir_edge_t *edge;
  79                 ir_node *bb;
  80
  81                 /*
  82                  * Adjust a and b so, that a dominates b if
  83                  * a dominates b or vice versa.
  84                  */
  85                 if(b2a) {
  86                         const ir_node *t = a;
  87                         a = b;
  88                         b = t;
  89                 }
  90
  91                 bb = get_nodes_block(b);
  92
  93                 /*
  94                  * If a is live end in b's block it is
  95                  * live at b's definition (a dominates b)
  96                  */
  97                 if(be_is_live_end(lv, bb, a))
  98                         return 1;
  99
 100                 /*
 101                  * Look at all usages of a.
 102                  * If there's one usage of a in the block of b, then
 103                  * we check, if this use is dominated by b, if that's true
 104                  * a and b interfere. Note that b must strictly dominate the user,
 105                  * since if b is the last user of in the block, b and a do not
 106                  * interfere.
 107                  * Uses of a not in b's block can be disobeyed, because the
 108                  * check for a being live at the end of b's block is already
 109                  * performed.
 110                  */
 111                 foreach_out_edge(a, edge) {
 112                         const ir_node *user = get_edge_src_irn(edge);
 113                         if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && _value_dominates(b, user))
 114                                 return 1;
 115                 }
 116         }
 117
 118         return 0;
 119 }
 120
 121
 122
 123 /**
 124  * Check if a node dominates a use.
 125  * Note that the use of a phi is in its corresponding predecessor.
 126  * @param irn  The node.
 127  * @param edge The use.
 128  * @return     1, if @p irn dominates the use @p edge.
 129  */
 130 static INLINE int _dominates_use(const ir_node *irn, const ir_edge_t *edge)
 131 {
 132         ir_node *use = get_edge_src_irn(edge);
 133
 134         if (is_Phi(use)) {
 135                 int pos         = get_edge_src_pos(edge);
 136                 ir_node *phi_bl = get_nodes_block(use);
 137                 ir_node *use_bl = get_Block_cfgpred_block(phi_bl, pos);
 138                 ir_node *irn_bl = get_nodes_block(irn);
 139                 return block_dominates(irn_bl, use_bl);
 140         }
 141
 142         return _value_dominates(irn, use);
 143 }
 144
 145 /**
 146  * Check if a node strictly dominates a use.
 147  * Note that the use of a phi is in its corresponding predecessor.
 148  * @param irn  The node.
 149  * @param edge The use.
 150  * @return     1, if @p irn strictly dominates the use @p edge.
 151  */
 152 static INLINE int _strictly_dominates_use(const ir_node *irn, const ir_edge_t *edge)
 153 {
 154         return get_edge_src_irn(edge) != irn && _dominates_use(irn, edge);
 155 }
 156
 157 /**
 158  * Check, if a node is live in front of another.
 159  * @param birg  The backend irg.
 160  * @param irn   The node.
 161  * @param where The location to check for.
 162  * @return      1, if @p irn is live in front of @p where.
 163  */
 164 static INLINE int _be_lv_chk_before_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 165 {
 166         const lv_chk_t *lv = be_get_birg_liveness_chk(birg);
 167         const ir_edge_t *edge;
 168
 169         /* the node must strictly dominate the location, else it cannot be live there. */
 170         if (!_value_dominates(irn, where) || irn == where)
 171                 return 0;
 172
 173         /*
 174          * now that it is clear that it strictly dominates the location it is surely live
 175          * if it is also live end at the block.
 176          */
 177         if (lv_chk_bl_end(lv, get_nodes_block(where), irn))
 178                 return 1;
 179
 180         /*
 181          * If the node is not live out, we have to check if there
 182          * is a use which is dominated by the location.
 183          */
 184         foreach_out_edge (irn, edge) {
 185                 if (_dominates_use(where, edge))
 186                         return 1;
 187         }
 188
 189         return 0;
 190 }
 191
 192 /**
 193  * Check, if a node is live after another node.
 194  * @param birg  The backend irg.
 195  * @param irn   The node.
 196  * @param where The location to check for.
 197  * @return      1, if @p irn is live after @p where.
 198  */
 199 static INLINE int _be_lv_chk_after_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 200 {
 201         const lv_chk_t *lv = be_get_birg_liveness_chk(birg);
 202         const ir_edge_t *edge;
 203
 204         if (!_value_dominates(irn, where))
 205                 return 0;
 206
 207         if (lv_chk_bl_end(lv, get_nodes_block(where), irn))
 208                 return 1;
 209
 210         foreach_out_edge (irn, edge) {
 211                 if (_strictly_dominates_use(where, edge))
 212                         return 1;
 213         }
 214
 215         return 0;
 216 }
 217
 218 /**
 219  * Check, if two nodes interfere.
 220  * This will become the favored rotine to call but it is not used yet.
 221  * @param birg   The backend irg.
 222  * @param a      The first node.
 223  * @param b      The second node.
 224  * @return       1, if a and b interfere, 0 if not.
 225  */
 226 static INLINE int _be_lv_chk_values_interfere(const be_irg_t *birg, const ir_node *a, const ir_node *b)
 227 {
 228         int adb = _value_dominates(a, b);
 229         int bda = _value_dominates(b, a);
 230
 231         if (bda) {
 232                 const ir_node *t = a;
 233                 a = b;
 234                 b = t;
 235                 adb = 1;
 236         }
 237
 238         return adb && _be_lv_chk_after_irn(birg, a, b);
 239 }
 240
 241 #define value_dominates_intrablock(a, b)         _value_dominates_intrablock(a, b)
 242 #define value_dominates(a, b)                    _value_dominates(a, b)
 243 #define lv_values_interfere(lv, a, b)            _lv_values_interfere(lv, a, b)
 244 #define values_interfere(birg, a, b)             _lv_values_interfere(be_get_birg_liveness(birg), a, b)
 245 #define dominates_use(a, e)                      _dominates_use(a, e)
 246 #define strictly_dominates_use(a, e)             _strictly_dominates_use(a, e)
 247 #define be_lv_chk_before_irn(birg, a, b)         _be_lv_chk_before_irn(birg, a, b)
 248 #define be_lv_chk_after_irn(birg, a, b)          _be_lv_chk_after_irn(birg, a, b)
 249 #define be_lv_chk_values_interfere(birg, a, b)   _be_lv_chk_values_interfere(birg, a, b)
 250
 251 #endif /* _BELIVECHK_T_H */