beifg.c 15.6 KB
Newer Older
1
/**
Sebastian Hack's avatar
Sebastian Hack committed
2
3
 * @file   beifg.c
 * @date   18.11.2005
4
 * @author Sebastian Hack
Sebastian Hack's avatar
Sebastian Hack committed
5
6
7
 *
 * Copyright (C) 2005 Universitaet Karlsruhe
 * Released under the GPL
8
 */
Sebastian Hack's avatar
Sebastian Hack committed
9
10
11

#include <stdlib.h>

Sebastian Hack's avatar
Sebastian Hack committed
12
13
14
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
15

Sebastian Hack's avatar
Sebastian Hack committed
16
#ifdef HAVE_MALLOC_H
17
#include <malloc.h>
Sebastian Hack's avatar
Sebastian Hack committed
18
#endif
Sebastian Hack's avatar
Sebastian Hack committed
19

20
21
22
23
#ifdef __linux__
#include <malloc.h>
#endif /* __linux__ */

Sebastian Hack's avatar
Sebastian Hack committed
24
25
26
27
#ifdef HAVE_ALLOCA_H
#include <alloca.h>
#endif

28
29
30
31
32
33
#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#include <libcore/lc_timing.h>
#endif /* WITH_LIBCORE */

34
35
#include "bitset.h"

36
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
37
38
#include "irnode_t.h"
#include "irprintf.h"
39
#include "irtools.h"
40
#include "irbitset.h"
41
#include "beifg_t.h"
42
43
44
45
46
47
48
49
50
51
#include "beifg_impl.h"
#include "irphase.h"
#include "irphase_t.h"
#include "bechordal.h"

#include "becopystat.h"
#include "becopyopt.h"

/** Defines values for the ifg performance test */
#define BE_CH_PERFORMANCETEST_MIN_NODES (50)
52
#define BE_CH_PERFORMANCETEST_COUNT (500)
53
54
55
56
57
58
59
60

typedef struct _coloring_t coloring_t;

struct _coloring_t {
	phase_t ph;
	const arch_env_t *arch_env;
	ir_graph *irg;
};
61

Sebastian Hack's avatar
Sebastian Hack committed
62
63
64
65
66
67
68
69
70
71
72
73
size_t (be_ifg_nodes_iter_size)(const void *self)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->nodes_iter_size;
}

size_t (be_ifg_neighbours_iter_size)(const void *self)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->neighbours_iter_size;
}

Daniel Grund's avatar
Daniel Grund committed
74
75
76
77
78
79
size_t (be_ifg_cliques_iter_size)(const void *self)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->cliques_iter_size;
}

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
static void *regs_irn_data_init(phase_t *ph, ir_node *irn, void *data)
{
	coloring_t *coloring = (coloring_t *) ph;
	return (void *) arch_get_irn_register(coloring->arch_env, irn);
}

coloring_t *coloring_init(coloring_t *c, ir_graph *irg, const arch_env_t *aenv)
{
	phase_init(&c->ph, "regs_map", irg, PHASE_DEFAULT_GROWTH, regs_irn_data_init);
	c->arch_env = aenv;
	c->irg = irg;
	return c;
}

static void get_irn_color(ir_node *irn, void *c)
{
	coloring_t *coloring = c;
	phase_get_or_set_irn_data(&coloring->ph, irn);
}

static void restore_irn_color(ir_node *irn, void *c)
{
	coloring_t *coloring = c;
	const arch_register_t *reg = phase_get_irn_data(&coloring->ph, irn);
	if(reg)
		arch_set_irn_register(coloring->arch_env, irn, reg);
}

void coloring_save(coloring_t *c)
{
	irg_walk_graph(c->irg, NULL, get_irn_color, c);
}

void coloring_restore(coloring_t *c)
{
	irg_walk_graph(c->irg, NULL, restore_irn_color, c);
}

Sebastian Hack's avatar
Sebastian Hack committed
118
119
120
121
void (be_ifg_free)(void *self)
{
	be_ifg_t *ifg = self;
	ifg->impl->free(self);
122
123
}

Sebastian Hack's avatar
Sebastian Hack committed
124
125
126
127
128
int (be_ifg_connected)(const void *self, const ir_node *a, const ir_node *b)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->connected(self, a, b);
}
129

Sebastian Hack's avatar
Sebastian Hack committed
130
131
132
133
ir_node *(be_ifg_neighbours_begin)(const void *self, void *iter, const ir_node *irn)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->neighbours_begin(self, iter, irn);
134
135
}

Sebastian Hack's avatar
Sebastian Hack committed
136
137
138
139
ir_node *(be_ifg_neighbours_next)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->neighbours_next(self, iter);
140
141
}

Sebastian Hack's avatar
Sebastian Hack committed
142
143
144
145
146
147
void (be_ifg_neighbours_break)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	ifg->impl->neighbours_break(self, iter);
}

Sebastian Hack's avatar
Sebastian Hack committed
148
149
150
151
ir_node *(be_ifg_nodes_begin)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->nodes_begin(self, iter);
152
153
}

Sebastian Hack's avatar
Sebastian Hack committed
154
155
156
157
ir_node *(be_ifg_nodes_next)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->nodes_next(self, iter);
158
159
}

Sebastian Hack's avatar
Sebastian Hack committed
160
161
162
163
164
165
void (be_ifg_nodes_break)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	ifg->impl->nodes_break(self, iter);
}

Daniel Grund's avatar
Daniel Grund committed
166
167
168
169
170
171
int (be_ifg_cliques_begin)(const void *self, void *iter, ir_node **buf)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->cliques_begin(self, iter, buf);
}

Daniel Grund's avatar
Fixes    
Daniel Grund committed
172
int (be_ifg_cliques_next)(const void *self, void *iter)
Daniel Grund's avatar
Daniel Grund committed
173
174
{
	const be_ifg_t *ifg = self;
Daniel Grund's avatar
Fixes    
Daniel Grund committed
175
	return ifg->impl->cliques_next(self, iter);
Daniel Grund's avatar
Daniel Grund committed
176
177
178
179
180
181
182
183
}

void (be_ifg_cliques_break)(const void *self, void *iter)
{
	const be_ifg_t *ifg = self;
	ifg->impl->cliques_break(self, iter);
}

Sebastian Hack's avatar
Sebastian Hack committed
184
185
186
187
int (be_ifg_degree)(const void *self, const ir_node *irn)
{
	const be_ifg_t *ifg = self;
	return ifg->impl->degree(self, irn);
188
189
}

Sebastian Hack's avatar
Sebastian Hack committed
190
191
192
193

int be_ifg_is_simplicial(const be_ifg_t *ifg, const ir_node *irn)
{
	int degree = be_ifg_degree(ifg, irn);
Sebastian Hack's avatar
Sebastian Hack committed
194
	void *iter = be_ifg_neighbours_iter_alloca(ifg);
Sebastian Hack's avatar
Sebastian Hack committed
195

Michael Beck's avatar
Michael Beck committed
196
	ir_node **neighbours = xmalloc(degree * sizeof(neighbours[0]));
Sebastian Hack's avatar
Sebastian Hack committed
197
198
199
200

	ir_node *curr;
	int i, j;

Michael Beck's avatar
Michael Beck committed
201
	i = 0;
Sebastian Hack's avatar
Sebastian Hack committed
202
203
204
205
206
207
208
209
210
211
212
213
214
215
	be_ifg_foreach_neighbour(ifg, iter, irn, curr)
		neighbours[i++] = curr;

	for(i = 0; i < degree; ++i) {
		for(j = 0; j < i; ++j)
			if(!be_ifg_connected(ifg, neighbours[i], neighbours[j])) {
				free(neighbours);
				return 0;
			}
	}


	free(neighbours);
	return 1;
216
217
}

Sebastian Hack's avatar
Sebastian Hack committed
218
void be_ifg_check(const be_ifg_t *ifg)
Sebastian Hack's avatar
Sebastian Hack committed
219
{
220
	void *iter1 = be_ifg_nodes_iter_alloca(ifg);
Sebastian Hack's avatar
Sebastian Hack committed
221
	void *iter2 = be_ifg_neighbours_iter_alloca(ifg);
Sebastian Hack's avatar
Sebastian Hack committed
222
223

	ir_node *n, *m;
224
225
226
227
228
229
230
231
232
233
234
235
236
237
	int node_count = 0;
	int neighbours_count = 0;
	int degree = 0;

	/* count all nodes */
	ir_printf("\n\nFound the following nodes in the graph %+F:\n\n", current_ir_graph);
	be_ifg_foreach_node(ifg,iter1,n)
	{
		node_count++;
		degree = be_ifg_degree(ifg, n);
		ir_printf("%d. %+F with degree: %d\n", node_count, n, degree);
	}

	ir_printf("\n\nNumber of nodes: %d\n\n", node_count);
Sebastian Hack's avatar
Sebastian Hack committed
238
239

	/* Check, if all neighbours are indeed connected to the node. */
240
241
242
	be_ifg_foreach_node(ifg, iter1, n)
	{
		ir_printf("\n%+F; ", n);
Sebastian Hack's avatar
Sebastian Hack committed
243
		be_ifg_foreach_neighbour(ifg, iter2, n, m)
244
245
246
		{
			ir_printf("%+F; ", m);
			neighbours_count++;
Sebastian Hack's avatar
Sebastian Hack committed
247
248
			if(!be_ifg_connected(ifg, n, m))
				ir_fprintf(stderr, "%+F is a neighbour of %+F but they are not connected!\n", n, m);
249
		}
Sebastian Hack's avatar
Sebastian Hack committed
250
	}
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
	ir_printf("\n\nFound %d nodes in the 'check neighbour section'\n", neighbours_count);
}

int be_ifg_check_get_node_count(const be_ifg_t *ifg)
{
	void *iter = be_ifg_nodes_iter_alloca(ifg);
	int node_count = 0;
	ir_node *n;

	be_ifg_foreach_node(ifg, iter, n)
	{
		node_count++;
	}

	return node_count;
}

static int be_ifg_check_cmp_nodes(const void *a, const void *b)
{
	const ir_node *node_a = *(ir_node **)a;
	const ir_node *node_b = *(ir_node **)b;

Matthias Braun's avatar
Matthias Braun committed
273
274
	long nr_a = get_irn_node_nr(node_a);
	long nr_b = get_irn_node_nr(node_b);
275
276
277
278

	return QSORT_CMP(nr_a, nr_b);
}

279
void be_ifg_check_sorted(const be_ifg_t *ifg)
280
281
282
283
284
285
286
287
288
289
290
291
{
	void *iter1 = be_ifg_nodes_iter_alloca(ifg);
	void *iter2 = be_ifg_neighbours_iter_alloca(ifg);

	ir_node *n, *m;
	const int node_count = be_ifg_check_get_node_count(ifg);
	int i = 0;

	ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));

	be_ifg_foreach_node(ifg, iter1, n)
	{
292
293
		if(!node_is_in_irgs_storage(ifg->env->irg, n))
		{
Christoph Mallon's avatar
Christoph Mallon committed
294
			ir_printf("+%F is in ifg but not in the current irg!", n);
295
296
297
			assert (node_is_in_irgs_storage(ifg->env->irg, n));
		}

298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
		all_nodes[i] = n;
		i++;
	}

	qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);

	for (i = 0; i < node_count; i++)
	{
		ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
		int j = 0;
		int k = 0;
		int degree = 0;

		degree = be_ifg_degree(ifg, all_nodes[i]);

		be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
		{
			neighbours[j] = m;
			j++;
		}

		qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);

321
		ir_printf("%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);
322
323
324

		for(k = 0; k < j; k++)
		{
325
			ir_printf("%+F, ", neighbours[k]);
326
327
		}

328
		ir_printf("\n");
329

330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
		free(neighbours);
	}

	free(all_nodes);

}

void be_ifg_check_sorted_to_file(const be_ifg_t *ifg, FILE *f)
{
	void *iter1 = be_ifg_nodes_iter_alloca(ifg);
	void *iter2 = be_ifg_neighbours_iter_alloca(ifg);

	ir_node *n, *m;
	const int node_count = be_ifg_check_get_node_count(ifg);
	int i = 0;

	ir_node **all_nodes = xmalloc(node_count * sizeof(all_nodes[0]));

	be_ifg_foreach_node(ifg, iter1, n)
	{
		if(!node_is_in_irgs_storage(ifg->env->irg, n))
		{
			ir_fprintf (f,"+%F is in ifg but not in the current irg!",n);
			assert (node_is_in_irgs_storage(ifg->env->irg, n));
		}

		all_nodes[i] = n;
		i++;
	}

	qsort(all_nodes, node_count, sizeof(all_nodes[0]), be_ifg_check_cmp_nodes);

	for (i = 0; i < node_count; i++)
	{
		ir_node **neighbours = xmalloc(node_count * sizeof(neighbours[0]));
		int j = 0;
		int k = 0;
		int degree = 0;

		degree = be_ifg_degree(ifg, all_nodes[i]);

		be_ifg_foreach_neighbour(ifg, iter2, all_nodes[i], m)
		{
			neighbours[j] = m;
			j++;
		}

		qsort(neighbours, j, sizeof(neighbours[0]), be_ifg_check_cmp_nodes);

		ir_fprintf (f,"%d. %+F's neighbours(%d): ", i+1, all_nodes[i], degree);

		for(k = 0; k < j; k++)
		{
			ir_fprintf (f,"%+F, ", neighbours[k]);
		}

		ir_fprintf (f,"\n");

388
389
390
391
392
		free(neighbours);
	}

	free(all_nodes);

393
}
394

395
396
void be_ifg_check_performance(be_chordal_env_t *chordal_env)
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
397
#ifdef WITH_LIBCORE
398
399
400
	int tests = BE_CH_PERFORMANCETEST_COUNT;
	coloring_t coloring;

401
	int used_memory;
402
403
404
405
406
407
408
409
410

	int i = 0;
	int rt;
	copy_opt_t *co;
	be_ifg_t *old_if = chordal_env->ifg;

	lc_timer_t *timer = lc_timer_register("getTime","get Time of copy minimization using the ifg");
	unsigned long elapsed_usec = 0;

Michael Beck's avatar
BugFix:    
Michael Beck committed
411
	if (get_irg_estimated_node_cnt(chordal_env->irg) >= BE_CH_PERFORMANCETEST_MIN_NODES)
412
413
414
415
416
417
418
419
	{
		coloring_init(&coloring, chordal_env->irg, chordal_env->birg->main_env->arch_env);
		coloring_save(&coloring);

		lc_timer_reset(timer);

		for (i = 0; i<tests; i++) /* performance test with std */
		{
420
421

			used_memory = lc_get_heap_used_bytes();
422
423
424
425
426
427
428
429
430

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			chordal_env->ifg = be_ifg_std_new(chordal_env);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

431
			used_memory = lc_get_heap_used_bytes() - used_memory;
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458

			coloring_restore(&coloring);

			co = NULL;
			co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
			co_build_ou_structure(co);
			co_build_graph_structure(co);

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			co_solve_heuristic_new(co);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

			co_free_graph_structure(co);
			co_free_ou_structure(co);
			free_copy_opt(co);
			be_ifg_free(chordal_env->ifg);

		}

		elapsed_usec = lc_timer_elapsed_usec(timer);
		/* calculating average */
		elapsed_usec = elapsed_usec / tests;

459
		ir_printf("\nstd:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
460
461
462
463
464
465

		used_memory=0;
		elapsed_usec=0;

		for (i = 0; i<tests; i++)  /* performance test with clique */
		{
466
			used_memory = lc_get_heap_used_bytes();
467
468
469
470
471
472
473
474
475

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			chordal_env->ifg = be_ifg_clique_new(chordal_env);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

476
			used_memory = lc_get_heap_used_bytes() - used_memory;
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503

			coloring_restore(&coloring);

			co = NULL;
			co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
			co_build_ou_structure(co);
			co_build_graph_structure(co);

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			co_solve_heuristic_new(co);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

			co_free_graph_structure(co);
			co_free_ou_structure(co);
			free_copy_opt(co);
			be_ifg_free(chordal_env->ifg);

		}

		elapsed_usec = lc_timer_elapsed_usec(timer);
		/* calculating average */
		elapsed_usec = elapsed_usec / tests;

504
		ir_printf("\nclique:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
505
506
507
508
509
510

		used_memory=0;
		elapsed_usec=0;

		for (i = 0; i<tests; i++)  /* performance test with list */
		{
511
			used_memory = lc_get_heap_used_bytes();
512
513
514
515
516
517
518
519
520

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			chordal_env->ifg = be_ifg_list_new(chordal_env);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

521
			used_memory = lc_get_heap_used_bytes() - used_memory;
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548

			coloring_restore(&coloring);

			co = NULL;
			co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
			co_build_ou_structure(co);
			co_build_graph_structure(co);

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			co_solve_heuristic_new(co);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

			co_free_graph_structure(co);
			co_free_ou_structure(co);
			free_copy_opt(co);
			be_ifg_free(chordal_env->ifg);

		}

		elapsed_usec = lc_timer_elapsed_usec(timer);
		/* calculating average */
		elapsed_usec = elapsed_usec / tests;

549
		ir_printf("\nlist:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
550
551
552
553
554
555

		used_memory=0;
		elapsed_usec=0;

		for (i = 0; i<tests; i++)  /* performance test with pointer */
		{
556
			used_memory = lc_get_heap_used_bytes();
557
558
559
560
561
562
563
564
565

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			chordal_env->ifg = be_ifg_pointer_new(chordal_env);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

566
			used_memory = lc_get_heap_used_bytes() - used_memory;
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593

			coloring_restore(&coloring);

			co = NULL;
			co = new_copy_opt(chordal_env, co_get_costs_loop_depth);
			co_build_ou_structure(co);
			co_build_graph_structure(co);

			rt = lc_timer_enter_high_priority();
			lc_timer_start(timer);

			co_solve_heuristic_new(co);

			lc_timer_stop(timer);
			rt = lc_timer_leave_high_priority();

			co_free_graph_structure(co);
			co_free_ou_structure(co);
			free_copy_opt(co);
			be_ifg_free(chordal_env->ifg);

		}

		elapsed_usec = lc_timer_elapsed_usec(timer);
		/* calculating average */
		elapsed_usec = elapsed_usec / tests;

594
		ir_printf("\npointer:; %+F; %u; %u ",current_ir_graph, used_memory, elapsed_usec);
595
596
597
598
599
600
601

		i=0;
		used_memory=0;
		elapsed_usec=0;
	}

	chordal_env->ifg = old_if;
Michael Beck's avatar
BugFix:    
Michael Beck committed
602
#endif /* WITH_LIBCORE */
603
604
}

605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
{
	void *nodes_it  = be_ifg_nodes_iter_alloca(ifg);
	void *neigh_it  = be_ifg_neighbours_iter_alloca(ifg);
	bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));

	ir_node *n, *m;

	fprintf(file, "graph G {\n\tgraph [");
	if(cb->graph_attr)
		cb->graph_attr(file, self);
	fprintf(file, "];\n");

	if(cb->at_begin)
		cb->at_begin(file, self);

	be_ifg_foreach_node(ifg, nodes_it, n) {
		if(cb->is_dump_node && cb->is_dump_node(self, n)) {
			int idx = get_irn_idx(n);
			bitset_set(nodes, idx);
			fprintf(file, "\tnode [");
			if(cb->node_attr)
				cb->node_attr(file, self, n);
			fprintf(file, "]; n%d;\n", idx);
		}
	}

	/* Check, if all neighbours are indeed connected to the node. */
	be_ifg_foreach_node(ifg, nodes_it, n) {
		be_ifg_foreach_neighbour(ifg, neigh_it, n, m) {
			int n_idx = get_irn_idx(n);
			int m_idx = get_irn_idx(m);

			if(n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
				fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
				if(cb->edge_attr)
					cb->edge_attr(file, self, n, m);
				fprintf(file, "];\n");
			}
		}
	}

	if(cb->at_end)
		cb->at_end(file, self);

	fprintf(file, "}\n");
	bitset_free(nodes);
}
653

Sebastian Hack's avatar
Sebastian Hack committed
654
static void int_comp_rec(const be_chordal_env_t *cenv, ir_node *n, bitset_t *seen)
655
{
Sebastian Hack's avatar
Sebastian Hack committed
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
	void *neigh_it  = be_ifg_neighbours_iter_alloca(cenv->ifg);
	ir_node *m;

	be_ifg_foreach_neighbour(cenv->ifg, neigh_it, n, m) {
		if(!bitset_contains_irn(seen, m) && !arch_irn_is(cenv->birg->main_env->arch_env, m, ignore)) {
			bitset_add_irn(seen, m);
			int_comp_rec(cenv, m, seen);
		}
	}

}

static int int_component_stat(const be_chordal_env_t *cenv)
{
	int n_comp     = 0;
	void *nodes_it = be_ifg_nodes_iter_alloca(cenv->ifg);
	bitset_t *seen = bitset_irg_malloc(cenv->irg);

	ir_node *n;

	be_ifg_foreach_node(cenv->ifg, nodes_it, n) {
		if(!bitset_contains_irn(seen, n) && !arch_irn_is(cenv->birg->main_env->arch_env, n, ignore)) {
			++n_comp;
			bitset_add_irn(seen, n);
			int_comp_rec(cenv, n, seen);
		}
	}

	free(seen);
	return n_comp;
}

void be_ifg_stat(const be_chordal_env_t *cenv, be_ifg_stat_t *stat)
{
	void *nodes_it  = be_ifg_nodes_iter_alloca(cenv->ifg);
	void *neigh_it  = be_ifg_neighbours_iter_alloca(cenv->ifg);
	bitset_t *nodes = bitset_irg_malloc(cenv->irg);
693
694
695
696

	ir_node *n, *m;

	memset(stat, 0, sizeof(stat[0]));
Sebastian Hack's avatar
Sebastian Hack committed
697
	be_ifg_foreach_node(cenv->ifg, nodes_it, n) {
698
		stat->n_nodes += 1;
Sebastian Hack's avatar
Sebastian Hack committed
699
		be_ifg_foreach_neighbour(cenv->ifg, neigh_it, n, m) {
700
701
702
703
704
			bitset_add_irn(nodes, n);
			stat->n_edges += !bitset_contains_irn(nodes, m);
		}
	}

Sebastian Hack's avatar
Sebastian Hack committed
705
	stat->n_comps = int_component_stat(cenv);
706
707
	bitset_free(nodes);
}