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