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 "besched.h"
  16 #include "belive_t.h"
  17 #include "beutil.h"
  18 #include "iredges_t.h"
  19
  20 /**
  21  * Check dominance of two nodes in the same block.
  22  * @param a The first node.
  23  * @param b The second node.
  24  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  25  */
  26 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  27 {
  28         assert(sched_is_scheduled(a));
  29         assert(sched_is_scheduled(b));
  30         sched_timestep_t const as = sched_get_time_step(a);
  31         sched_timestep_t const bs = sched_get_time_step(b);
  32         return as <= bs;
  33 }
  34
  35 /**
  36  * Check strict dominance of two nodes in the same block.
  37  * @param a The first node.
  38  * @param b The second node.
  39  * @return 1 if a comes before b in the same block, 0 else.
  40  */
  41 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
  42 {
  43         assert(sched_is_scheduled(a));
  44         assert(sched_is_scheduled(b));
  45         sched_timestep_t const as = sched_get_time_step(a);
  46         sched_timestep_t const bs = 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_const(a);
  60         const ir_node *block_b = get_block_const(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_const(a);
  86         const ir_node *block_b = get_block_const(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
 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 be_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         int res = 0;
 114
 115         /*
 116          * Adjust a and b so, that a dominates b if
 117          * a dominates b or vice versa.
 118          */
 119         if(b2a) {
 120                 const ir_node *t = a;
 121                 a = b;
 122                 b = t;
 123                 a2b = 1;
 124         }
 125
 126         /* If there is no dominance relation, they do not interfere. */
 127         if(a2b) {
 128                 ir_node *bb = get_nodes_block(b);
 129
 130                 /*
 131                  * If a is live end in b's block it is
 132                  * live at b's definition (a dominates b)
 133                  */
 134                 if(be_is_live_end(lv, bb, a)) {
 135                         res = 1;
 136                         goto end;
 137                 }
 138
 139                 /*
 140                  * Look at all usages of a.
 141                  * If there's one usage of a in the block of b, then
 142                  * we check, if this use is dominated by b, if that's true
 143                  * a and b interfere. Note that b must strictly dominate the user,
 144                  * since if b is the last user of in the block, b and a do not
 145                  * interfere.
 146                  * Uses of a not in b's block can be disobeyed, because the
 147                  * check for a being live at the end of b's block is already
 148                  * performed.
 149                  */
 150                 foreach_out_edge(a, edge) {
 151                         const ir_node *user = get_edge_src_irn(edge);
 152                         if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
 153                                 res = 1;
 154                                 goto end;
 155                         }
 156                 }
 157         }
 158
 159 end:
 160         return res;
 161 }
 162
 163 #define value_dominates(a, b) _value_dominates(a, b)
 164
 165 #endif