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 "iredges_t.h"
  18
  19 /**
  20  * Check dominance of two nodes in the same block.
  21  * @param a The first node.
  22  * @param b The second node.
  23  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  24  */
  25 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  26 {
  27         /* TODO: ? :  can be removed?! */
  28         sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
  29         sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
  30         return as <= bs;
  31 }
  32
  33 /**
  34  * Check strict dominance of two nodes in the same block.
  35  * @param a The first node.
  36  * @param b The second node.
  37  * @return 1 if a comes before b in the same block, 0 else.
  38  */
  39 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
  40 {
  41         /* TODO: ? :  can be removed?! */
  42         sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
  43         sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
  44         return as < bs;
  45 }
  46
  47 /**
  48  * Check, if one value dominates the other.
  49  * The dominance is not strict here.
  50  * @param a The first node.
  51  * @param b The second node.
  52  * @return 1 if a dominates b or if a == b, 0 else.
  53  */
  54 static inline int _value_dominates(const ir_node *a, const ir_node *b)
  55 {
  56         const ir_node *block_a = get_block_const(a);
  57         const ir_node *block_b = get_block_const(b);
  58
  59         /*
  60          * a and b are not in the same block,
  61          * so dominance is determined by the dominance of the blocks.
  62          */
  63         if(block_a != block_b) {
  64                 return block_dominates(block_a, block_b);
  65         }
  66
  67         /*
  68          * Dominance is determined by the time steps of the schedule.
  69          */
  70         return _value_dominates_intrablock(a, b);
  71 }
  72
  73 /**
  74  * Check, if one value dominates the other.
  75  * The dominance is strict here.
  76  * @param a The first node.
  77  * @param b The second node.
  78  * @return 1 if a dominates b, 0 else.
  79  */
  80 static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
  81 {
  82         const ir_node *block_a = get_block_const(a);
  83         const ir_node *block_b = get_block_const(b);
  84
  85         /*
  86          * a and b are not in the same block,
  87          * so dominance is determined by the dominance of the blocks.
  88          */
  89         if(block_a != block_b) {
  90                 return block_dominates(block_a, block_b);
  91         }
  92
  93         /*
  94          * Dominance is determined by the time steps of the schedule.
  95          */
  96         return _value_strictly_dominates_intrablock(a, b);
  97 }
  98
  99 /**
 100  * Check, if two values interfere.
 101  * @param lv Liveness information
 102  * @param a The first value.
 103  * @param b The second value.
 104  * @return 1, if a and b interfere, 0 if not.
 105  */
 106 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
 107 {
 108         int a2b = _value_dominates(a, b);
 109         int b2a = _value_dominates(b, a);
 110         int res = 0;
 111
 112         /*
 113          * Adjust a and b so, that a dominates b if
 114          * a dominates b or vice versa.
 115          */
 116         if(b2a) {
 117                 const ir_node *t = a;
 118                 a = b;
 119                 b = t;
 120                 a2b = 1;
 121         }
 122
 123         /* If there is no dominance relation, they do not interfere. */
 124         if(a2b) {
 125                 ir_node *bb = get_nodes_block(b);
 126
 127                 /*
 128                  * If a is live end in b's block it is
 129                  * live at b's definition (a dominates b)
 130                  */
 131                 if(be_is_live_end(lv, bb, a)) {
 132                         res = 1;
 133                         goto end;
 134                 }
 135
 136                 /*
 137                  * Look at all usages of a.
 138                  * If there's one usage of a in the block of b, then
 139                  * we check, if this use is dominated by b, if that's true
 140                  * a and b interfere. Note that b must strictly dominate the user,
 141                  * since if b is the last user of in the block, b and a do not
 142                  * interfere.
 143                  * Uses of a not in b's block can be disobeyed, because the
 144                  * check for a being live at the end of b's block is already
 145                  * performed.
 146                  */
 147                 foreach_out_edge(a, edge) {
 148                         const ir_node *user = get_edge_src_irn(edge);
 149                         if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
 150                                 res = 1;
 151                                 goto end;
 152                         }
 153                 }
 154         }
 155
 156 end:
 157         return res;
 158 }
 159
 160 #define value_dominates(a, b) _value_dominates(a, b)
 161
 162 #endif