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 #define value_dominates(a, b) _value_dominates(a, b)
  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         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         sched_timestep_t const as = sched_get_time_step(a);
  44         sched_timestep_t const bs = sched_get_time_step(b);
  45         return as < bs;
  46 }
  47
  48 /**
  49  * Check, if one value dominates the other.
  50  * The dominance is not strict here.
  51  * @param a The first node.
  52  * @param b The second node.
  53  * @return 1 if a dominates b or if a == b, 0 else.
  54  */
  55 static inline int _value_dominates(const ir_node *a, const ir_node *b)
  56 {
  57         const ir_node *block_a = get_block_const(a);
  58         const ir_node *block_b = get_block_const(b);
  59
  60         /*
  61          * a and b are not in the same block,
  62          * so dominance is determined by the dominance of the blocks.
  63          */
  64         if(block_a != block_b) {
  65                 return block_dominates(block_a, block_b);
  66         }
  67
  68         /*
  69          * Dominance is determined by the time steps of the schedule.
  70          */
  71         return _value_dominates_intrablock(a, b);
  72 }
  73
  74 /**
  75  * Check, if two values interfere.
  76  * @param lv Liveness information
  77  * @param a The first value.
  78  * @param b The second value.
  79  * @return 1, if a and b interfere, 0 if not.
  80  */
  81 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  82 {
  83         int a2b = _value_dominates(a, b);
  84         int b2a = _value_dominates(b, a);
  85         int res = 0;
  86
  87         /*
  88          * Adjust a and b so, that a dominates b if
  89          * a dominates b or vice versa.
  90          */
  91         if(b2a) {
  92                 const ir_node *t = a;
  93                 a = b;
  94                 b = t;
  95                 a2b = 1;
  96         }
  97
  98         /* If there is no dominance relation, they do not interfere. */
  99         if(a2b) {
 100                 ir_node *bb = get_nodes_block(b);
 101
 102                 /*
 103                  * If a is live end in b's block it is
 104                  * live at b's definition (a dominates b)
 105                  */
 106                 if(be_is_live_end(lv, bb, a)) {
 107                         res = 1;
 108                         goto end;
 109                 }
 110
 111                 /*
 112                  * Look at all usages of a.
 113                  * If there's one usage of a in the block of b, then
 114                  * we check, if this use is dominated by b, if that's true
 115                  * a and b interfere. Note that b must strictly dominate the user,
 116                  * since if b is the last user of in the block, b and a do not
 117                  * interfere.
 118                  * Uses of a not in b's block can be disobeyed, because the
 119                  * check for a being live at the end of b's block is already
 120                  * performed.
 121                  */
 122                 foreach_out_edge(a, edge) {
 123                         const ir_node *user = get_edge_src_irn(edge);
 124                         if (get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates_intrablock(b, user)) {
 125                                 res = 1;
 126                                 goto end;
 127                         }
 128                 }
 129         }
 130
 131 end:
 132         return res;
 133 }
 134
 135 #endif