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         /*
 119          * Adjust a and b so, that a dominates b if
 120          * a dominates b or vice versa.
 121          */
 122         if(b2a) {
 123                 const ir_node *t = a;
 124                 a = b;
 125                 b = t;
 126                 a2b = 1;
 127         }
 128
 129         /* If there is no dominance relation, they do not interfere. */
 130         if(a2b) {
 131                 const ir_edge_t *edge;
 132                 ir_node *bb = get_nodes_block(b);
 133
 134                 //stat_ev_dbl("beintlive_ignore", arch_irn_is(lv->birg->main_env->arch_env, a, ignore));
 135
 136                 /*
 137                  * If a is live end in b's block it is
 138                  * live at b's definition (a dominates b)
 139                  */
 140                 if(be_is_live_end(lv, bb, a)) {
 141                         res = 1;
 142                         goto end;
 143                 }
 144
 145                 /*
 146                  * Look at all usages of a.
 147                  * If there's one usage of a in the block of b, then
 148                  * we check, if this use is dominated by b, if that's true
 149                  * a and b interfere. Note that b must strictly dominate the user,
 150                  * since if b is the last user of in the block, b and a do not
 151                  * interfere.
 152                  * Uses of a not in b's block can be disobeyed, because the
 153                  * check for a being live at the end of b's block is already
 154                  * performed.
 155                  */
 156                 foreach_out_edge(a, edge) {
 157                         const ir_node *user = get_edge_src_irn(edge);
 158                         if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
 159                                 res = 1;
 160                                 goto end;
 161                         }
 162                 }
 163         }
 164
 165 end:
 166         return res;
 167 }
 168
 169
 170
 171 /**
 172  * Check if a node dominates a use.
 173  * Note that the use of a phi is in its corresponding predecessor.
 174  * @param irn  The node.
 175  * @param edge The use.
 176  * @return     1, if @p irn dominates the use @p edge.
 177  */
 178 static INLINE int _dominates_use(const ir_node *irn, const ir_edge_t *edge)
 179 {
 180         ir_node *use = get_edge_src_irn(edge);
 181
 182         if (is_Phi(use)) {
 183                 int pos         = get_edge_src_pos(edge);
 184                 ir_node *phi_bl = get_nodes_block(use);
 185                 ir_node *use_bl = get_Block_cfgpred_block(phi_bl, pos);
 186                 ir_node *irn_bl = get_nodes_block(irn);
 187                 return block_dominates(irn_bl, use_bl);
 188         }
 189
 190         return _value_dominates(irn, use);
 191 }
 192
 193 /**
 194  * Check if a node strictly dominates a use.
 195  * Note that the use of a phi is in its corresponding predecessor.
 196  * @param irn  The node.
 197  * @param edge The use.
 198  * @return     1, if @p irn strictly dominates the use @p edge.
 199  */
 200 static INLINE int _strictly_dominates_use(const ir_node *irn, const ir_edge_t *edge)
 201 {
 202         return get_edge_src_irn(edge) != irn && _dominates_use(irn, edge);
 203 }
 204
 205 /**
 206  * Check, if a node is live in front of another.
 207  * @param birg  The backend irg.
 208  * @param irn   The node.
 209  * @param where The location to check for.
 210  * @return      1, if @p irn is live in front of @p where.
 211  */
 212 static INLINE int _be_lv_chk_before_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 213 {
 214         const be_lv_t *lv = be_get_birg_liveness(birg);
 215         const ir_edge_t *edge;
 216
 217         /* the node must strictly dominate the location, else it cannot be live there. */
 218         if (!_value_dominates(irn, where) || irn == where)
 219                 return 0;
 220
 221         /*
 222          * now that it is clear that it strictly dominates the location it is surely live
 223          * if it is also live end at the block.
 224          */
 225         if (be_is_live_end(lv, get_nodes_block(where), irn))
 226                 return 1;
 227
 228         /*
 229          * If the node is not live out, we have to check if there
 230          * is a use which is dominated by the location.
 231          */
 232         foreach_out_edge (irn, edge) {
 233                 if (_dominates_use(where, edge))
 234                         return 1;
 235         }
 236
 237         return 0;
 238 }
 239
 240 /**
 241  * Check, if a node is live after another node.
 242  * @param birg  The backend irg.
 243  * @param irn   The node.
 244  * @param where The location to check for.
 245  * @return      1, if @p irn is live after @p where.
 246  */
 247 static INLINE int _be_lv_chk_after_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 248 {
 249         const be_lv_t *lv = be_get_birg_liveness(birg);
 250         const ir_edge_t *edge;
 251
 252         if (!_value_dominates(irn, where))
 253                 return 0;
 254
 255         if (be_is_live_end(lv, get_nodes_block(where), irn))
 256                 return 1;
 257
 258         foreach_out_edge (irn, edge) {
 259                 if (_strictly_dominates_use(where, edge))
 260                         return 1;
 261         }
 262
 263         return 0;
 264 }
 265
 266 #define value_dominates_intrablock(a, b)         _value_dominates_intrablock(a, b)
 267 #define value_dominates(a, b)                    _value_dominates(a, b)
 268 #define values_interfere(birg, a, b)             _lv_values_interfere(be_get_birg_liveness(birg), a, b)
 269 #define dominates_use(a, e)                      _dominates_use(a, e)
 270 #define strictly_dominates_use(a, e)             _strictly_dominates_use(a, e)
 271 #define be_lv_chk_before_irn(birg, a, b)         _be_lv_chk_before_irn(birg, a, b)
 272 #define be_lv_chk_after_irn(birg, a, b)          _be_lv_chk_after_irn(birg, a, b)
 273
 274 #endif /* _BELIVECHK_T_H */