cdep.c 3.97 KB
Newer Older
Matthias Braun's avatar
Matthias Braun committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Matthias Braun's avatar
Matthias Braun committed
4
5
6
7
8
 */

/**
 * @file
 * @brief   Implementation of cdep
Matthias Braun's avatar
Matthias Braun committed
9
 * @author  Christoph Mallon
Matthias Braun's avatar
Matthias Braun committed
10
 */
11
12
#include <assert.h>
#include <stdlib.h>
13
#include "irdom_t.h"
14
#include "irgraph_t.h"
15
#include "irgwalk.h"
16
#include "irnode_t.h"
17
#include "pmap.h"
Michael Beck's avatar
Michael Beck committed
18
#include "obst.h"
Michael Beck's avatar
Michael Beck committed
19
#include "xmalloc.h"
20
#include "cdep_t.h"
21
#include "irprintf.h"
Michael Beck's avatar
Michael Beck committed
22
23
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
24
typedef struct cdep_info {
Matthias Braun's avatar
Matthias Braun committed
25
26
	pmap          *cdep_map; /**< A map to find the list of all control dependence nodes for a block. */
	struct obstack obst;     /**< An obstack where all cdep data lives on. */
Michael Beck's avatar
Michael Beck committed
27
} cdep_info;
28

Michael Beck's avatar
Michael Beck committed
29
static cdep_info *cdep_data;
30

31
32
33
34
35
36
37
38
39
40
ir_node *(get_cdep_node)(const ir_cdep *cdep)
{
	return _get_cdep_node(cdep);
}

ir_cdep *(get_cdep_next)(const ir_cdep *cdep)
{
	return _get_cdep_next(cdep);
}

41
42
ir_cdep *find_cdep(const ir_node *block)
{
43
	assert(is_Block(block));
44
	return pmap_get(ir_cdep, cdep_data->cdep_map, block);
45
46
}

47
48
void exchange_cdep(ir_node *old, const ir_node *nw)
{
49
	ir_cdep *cdep = find_cdep(nw);
50
	assert(is_Block(old));
Michael Beck's avatar
Michael Beck committed
51
	pmap_insert(cdep_data->cdep_map, old, cdep);
Christoph Mallon's avatar
Christoph Mallon committed
52
53
}

Michael Beck's avatar
Michael Beck committed
54
55
56
/**
 * Adds a control dependence from node to dep_on.
 */
57
58
static void add_cdep(ir_node *node, ir_node *dep_on)
{
59
	ir_cdep *dep = find_cdep(node);
60

61
	assert(is_Block(dep_on));
62
	if (dep == NULL) {
63
		ir_cdep *newdep = OALLOC(&cdep_data->obst, ir_cdep);
64
65
66

		newdep->node = dep_on;
		newdep->next = NULL;
Michael Beck's avatar
Michael Beck committed
67
		pmap_insert(cdep_data->cdep_map, node, newdep);
68
	} else {
69
		ir_cdep *newdep;
70
71

		for (;;) {
Matthias Braun's avatar
Matthias Braun committed
72
73
74
75
			if (get_cdep_node(dep) == dep_on)
				return;
			if (dep->next == NULL)
				break;
76
77
			dep = dep->next;
		}
78
		newdep = OALLOC(&cdep_data->obst, ir_cdep);
79
80
81
82
		newdep->node = dep_on;
		newdep->next = NULL;
		dep->next = newdep;
	}
83
84
}

85
86
87
/**
 * Pre-block-walker: calculate the control dependence
 */
88
89
static void cdep_pre(ir_node *node, void *ctx)
{
90
	(void)ctx;
Matthias Braun's avatar
Matthias Braun committed
91
	for (int i = get_Block_n_cfgpreds(node); i-- > 0; ) {
92
		ir_node *pred = get_Block_cfgpred_block(node, i);
93
		if (pred == NULL)
Matthias Braun's avatar
Matthias Braun committed
94
			continue;
95

Matthias Braun's avatar
Matthias Braun committed
96
97
98
		ir_node *pdom = get_Block_ipostdom(pred);
		for (ir_node *dependee = node; dependee != pdom;
		     dependee = get_Block_ipostdom(dependee)) {
99
100
101
102
			assert(!is_Bad(pdom));
			add_cdep(dependee, pred);
		}
	}
103
104
105
}


106
107
108
109
/**
 * A block edge hook: add all cdep edges of block.
 */
static int cdep_edge_hook(FILE *F, ir_node *block)
110
{
Matthias Braun's avatar
Matthias Braun committed
111
112
113
114
	for (ir_cdep *cd = find_cdep(block); cd != NULL; cd = cd->next) {
		fprintf(F, "edge:{sourcename:\"n%ld\" targetname:\"n%ld\" "
		           "linestyle:dashed color:gold}\n",
		        get_irn_node_nr(block), get_irn_node_nr(cd->node));
115
	}
116
117
118
119

	return 0;
}

120
121
void compute_cdep(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
122
	free_cdep(irg);
123
	cdep_data = XMALLOC(cdep_info);
Michael Beck's avatar
Michael Beck committed
124
125
126
	obstack_init(&cdep_data->obst);

	cdep_data->cdep_map = pmap_create();
127

128
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_POSTDOMINANCE);
129

Michael Beck's avatar
Michael Beck committed
130
131
132
133
	/* we must temporary change the post dominator relation:
	   the ipdom of the startblock is the end block.
	   Firm does NOT add the phantom edge from Start to End.
	 */
134
135
136
137
	ir_node *const start_block = get_irg_start_block(irg);
	ir_node *const end_block   = get_irg_end_block(irg);
	ir_node *const rem         = get_Block_ipostdom(start_block);
	set_Block_ipostdom(start_block, end_block);
Michael Beck's avatar
Michael Beck committed
138

139
	irg_block_walk_graph(irg, cdep_pre, NULL, NULL);
140

Matthias Braun's avatar
Matthias Braun committed
141
	(void)cdep_edge_hook;
142

143
	/* restore the post dominator relation */
144
	set_Block_ipostdom(start_block, rem);
145
146
}

147
148
void free_cdep(ir_graph *irg)
{
Matthias Braun's avatar
Matthias Braun committed
149
	(void)irg;
Michael Beck's avatar
Michael Beck committed
150
151
152
	if (cdep_data != NULL) {
		pmap_destroy(cdep_data->cdep_map);
		obstack_free(&cdep_data->obst, NULL);
153
		free(cdep_data);
Michael Beck's avatar
Michael Beck committed
154
155
		cdep_data = NULL;
	}
156
157
}

158
159
int is_cdep_on(const ir_node *dependee, const ir_node *candidate)
{
Matthias Braun's avatar
Matthias Braun committed
160
161
162
163
	for (const ir_cdep *dep = find_cdep(dependee); dep != NULL;
	     dep = dep->next) {
		if (get_cdep_node(dep) == candidate)
			return 1;
Christoph Mallon's avatar
Christoph Mallon committed
164
165
166
167
	}
	return 0;
}

168
169
ir_node *get_unique_cdep(const ir_node *block)
{
170
	ir_cdep *cdep = find_cdep(block);
171
	return cdep != NULL && cdep->next == NULL ? get_cdep_node(cdep) : NULL;
172
173
}

174
175
int has_multiple_cdep(const ir_node *block)
{
176
	ir_cdep *cdep = find_cdep(block);
177
178
	return cdep != NULL && cdep->next != NULL;
}