4 * @author Sebastian Hack
6 * Principal routines for liveness and interference checks.
8 * Copyright (C) 2007 Universitaet Karlsruhe
9 * Released under the GPL
12 #ifndef _BELIVECHK_T_H
13 #define _BELIVECHK_T_H
18 #include "iredges_t.h"
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.
26 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
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);
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.
41 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
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);
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.
57 static inline int _value_dominates(const ir_node *a, const ir_node *b)
59 const ir_node *block_a = get_block_const(a);
60 const ir_node *block_b = get_block_const(b);
63 * a and b are not in the same block,
64 * so dominance is determined by the dominance of the blocks.
66 if(block_a != block_b) {
67 return block_dominates(block_a, block_b);
71 * Dominance is determined by the time steps of the schedule.
73 return _value_dominates_intrablock(a, b);
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.
83 static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
85 const ir_node *block_a = get_block_const(a);
86 const ir_node *block_b = get_block_const(b);
89 * a and b are not in the same block,
90 * so dominance is determined by the dominance of the blocks.
92 if(block_a != block_b) {
93 return block_dominates(block_a, block_b);
97 * Dominance is determined by the time steps of the schedule.
99 return _value_strictly_dominates_intrablock(a, b);
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.
109 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
111 int a2b = _value_dominates(a, b);
112 int b2a = _value_dominates(b, a);
116 * Adjust a and b so, that a dominates b if
117 * a dominates b or vice versa.
120 const ir_node *t = a;
126 /* If there is no dominance relation, they do not interfere. */
128 ir_node *bb = get_nodes_block(b);
131 * If a is live end in b's block it is
132 * live at b's definition (a dominates b)
134 if(be_is_live_end(lv, bb, a)) {
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
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
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)) {
163 #define value_dominates(a, b) _value_dominates(a, b)