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