beifg_pointer.c 16.4 KB
Newer Older
1
2
/**
 * @file   beifg_pointer.c
3
 * @date   18.11.2005
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 * @author Sebastian Hack
 *
 * Copyright (C) 2005 Universitaet Karlsruhe
 * Released under the GPL
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdlib.h>

#include "belive_t.h"
#include "list.h"
18
19
#include "irphase.h"
#include "irphase_t.h"
20
21
22
23

#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
24
#include "irbitset.h"
25
26
27
28
29
30

#include "be_t.h"
#include "bera.h"
#include "beifg_t.h"
#include "bechordal_t.h"

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
typedef struct _ptr_element_t ptr_element_t;

typedef union element_content {
	ir_node *irn;
	ptr_element_t *element;
} element_content;

struct _ptr_element_t {
	int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
	element_content content_first; /* could be a ptr_element or ir_node */
	element_content content_second; /* could be a ptr_element or ir_node */
};

typedef struct _ptr_head_t {
	struct list_head list;
	ptr_element_t *element;
} ptr_head_t;
48
49
50
51

typedef struct _ifg_pointer_t {
	const be_ifg_impl_t *impl;
	const be_chordal_env_t *env;
52
	phase_t ph;
53
	struct obstack obst;
54
55
56
	ptr_head_t *curr_ptr_head;
	ptr_element_t *curr_element;
	pmap *node_map;
57
58
} ifg_pointer_t;

59
60
61
62
63
64
65
66
67
typedef struct _ptr_iter_t {
	const ifg_pointer_t *ifg;
	const ir_node *irn;
	ptr_head_t *curr_ptr_head;
	ptr_head_t *first_head;
	ptr_element_t *curr_element_t;
	ir_node *curr_irn;
	int get_first;
	int sub_call;
68
	bitset_t *visited_neighbours;
69
} ptr_iter_t;
70
71
72

/* PRIVATE FUNCTIONS */

Christoph Mallon's avatar
Christoph Mallon committed
73
static void *ptr_irn_data_init(phase_t *ph, ir_node *irn, void *data)
74
75
76
77
{
	ptr_head_t *head = phase_alloc(ph, sizeof(*head));
	INIT_LIST_HEAD(&head->list);
	return head;
78
79
}

80
static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
81
{
82
83
84
	ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
	memset(new_element, 0, sizeof(*new_element));
	return new_element;
85
86
}

87
static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
88
{
89
90
91
	ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
	INIT_LIST_HEAD(&new_element->list);
	return new_element;
92
93
}

94
static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
95
{
96
97
	ir_node *live_irn;
	bitset_pos_t elm;
98

99
100
101
102
103
	bitset_foreach_irn(ifg->env->irg, live, elm, live_irn)
	{
		ptr_head_t *head = phase_get_or_set_irn_data(&ifg->ph, live_irn);
		ptr_head_t *element = ptr_get_new_head(ifg);
		ir_node *irn = NULL;
104

Matthias Braun's avatar
Matthias Braun committed
105
106
#if 0
		// Matze: huh, what is this?!? node numbers aren't in any way deterministic AFAIK
107
108
		if (live_irn->node_nr == 1883 || live_irn->node_nr == 1858)
			irn = NULL;
Matthias Braun's avatar
Matthias Braun committed
109
#endif
110

111
112
		element->element = ifg->curr_element; /* write current highest sub-clique for each node */
		list_add(&element->list, &head->list);
113

114
115
116
117
118
		/* the following code is to find all nodes, it should be replaced by a "keywalker" of irphase */
		irn = pmap_get(ifg->node_map, live_irn);
		if (!irn)
			pmap_insert(ifg->node_map, live_irn, live_irn);
	}
119
120
}

121
static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
122
{
123
124
	ptr_element_t *element = ifg->curr_element;
	ptr_element_t *res = NULL;
125

126
127
128
129
	/* search the last sub-clique before the sub-clique that contains the node irn */
	if (element && element->kind == 8888
		&& (element->content_first.irn == irn
		|| element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
130
	{
131
132
133
134
135
136
137
138
139
140
		if (bitset_is_set(live, get_irn_idx(element->content_first.irn)) && element->content_first.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
		{
			bitset_set(my_live, get_irn_idx(element->content_first.irn));
		}

		if (bitset_is_set(live, get_irn_idx(element->content_second.irn))&& element->content_second.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
		{
			bitset_set(my_live, get_irn_idx(element->content_second.irn));
		}
		res = NULL;
141
142
143
	}
	else
	{
144
145
146
147
148
149
150
		if (element && element->kind == 8889)
		{ /* this was a "single-node-clique" */
			res = NULL;
		}

		if (element && (element->kind == 3101)
			&& (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
151
		{
152
			res = element->content_first.element;
153
154
155
		}
		else
		{
156
157
158
159
160
161
162
163
164
165
166
167
168
			if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
			{
				if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
				{
					bitset_set(my_live, get_irn_idx(element->content_second.irn));
				}
				ifg->curr_element = element->content_first.element;
				res = get_last_sub_clique(ifg, live, my_live, irn);
			}
			else
			{
				res = NULL;
			}
169
170
		}
	}
171
	return res;
172
173
174
175
}

static void find_neighbour_walker(ir_node *bl, void *data)
{
176
177
	ifg_pointer_t *ifg      = data;
	struct list_head *head  = get_block_border_head(ifg->env, bl);
178
	border_t *b;
179
180
181
182
183
184
	bitset_t *live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
	bitset_t *my_live;
	bitset_pos_t my_elm;
	ir_node *my_irn;
	element_content last_irn;
	element_content last_element;
185
	int was_def = 0;
186
187
	ir_node *first = NULL;
	int was_first = 0;
188

189
190
	last_irn.irn = NULL;
	last_element.element = NULL;
191
192
193

	assert(is_Block(bl) && "There is no block to work on.");

194
	foreach_border_head(head, b) /* follow the borders of the block */
195
196
	{
		ir_node *irn = b->irn;
197
198
		ptr_element_t *element = NULL;

Matthias Braun's avatar
Matthias Braun committed
199
200
#if 0
		// ?!?
201
202
		if (irn->node_nr == 1883 || irn->node_nr == 1858)
			i=1;
Matthias Braun's avatar
Matthias Braun committed
203
#endif
204

205
		if (b->is_def) /* b is a new node */
206
		{
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
			bitset_set(live, get_irn_idx(irn));
			if (last_element.element)
			{
				element = ptr_get_new_element(ifg);
				element->content_first.element = last_element.element;
				element->content_second.irn = b->irn;
				element->kind = 3101; /* first is an element, second an ir_node */

				last_element.element = element;
				ifg->curr_element = element;
			}
			else
			{
				if (last_irn.irn)	/* create new sub-clique */
				{
					element = ptr_get_new_element(ifg);
					element->content_first.irn = last_irn.irn;
					element->content_second.irn = b->irn;
					element->kind = 8888; /* both are ir_nodes */

Matthias Braun's avatar
Matthias Braun committed
227
228
#if 0
					// ?!?
229
230
					if (irn->node_nr == 1883 || irn->node_nr == 1858 || irn->node_nr == 1936)
						i=1;
Matthias Braun's avatar
Matthias Braun committed
231
#endif
232
233
234
235
236
237
238
239
240
241
242
243
244


					last_element.element = element;
					ifg->curr_element = element;
					last_irn.irn = NULL;
				}
				else
				{
					last_irn.irn = b->irn;	/* needed to create first sub-clique */
					last_element.element = NULL;
				}
			}

245
246
			was_def = 1;
		}
247
		else
248
		{
249
			if (was_def == 1) /* if there is a USE after a DEF... */
250
			{
251
252
253
254
255
256
257
258
259
260
261
262
				if (!last_element.element)
				{ /* there was only one element in the clique */
					element = ptr_get_new_element(ifg);
					element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
					element->content_first.irn = last_irn.irn;
					last_irn.irn = NULL;
					element = NULL;
					ifg->curr_element = NULL;
				}


				write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
263
264
				was_def = 0;
			}
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

			my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
			last_element.element = get_last_sub_clique(ifg, live, my_live, irn);

			/* check and add still living nodes */
			//bitset_remv_irn(my_live, irn);
			if (bitset_popcnt(my_live) > 1)
			{
				if (last_element.element)
				{
					bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
					{
						ptr_element_t *my_element = ptr_get_new_element(ifg);
						my_element->content_first.element = last_element.element;
						my_element->content_second.irn = my_irn;
						my_element->kind = 3101; /* first is an element, second an ir_node */

						last_element.element = my_element;
						ifg->curr_element = my_element;
					}
				}
				else
				{
					bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
					{
						ptr_element_t *my_element = NULL;
						if (!first && !was_first)
						{
							first = my_irn;
							was_first = 1;
						}
						else
						{
							if (first && was_first)
							{
								my_element = ptr_get_new_element(ifg);
								my_element->content_first.irn = first;
								my_element->content_second.irn = my_irn;
								my_element->kind = 8888; /* both are ir_nodes */
								last_element.element = my_element;
								ifg->curr_element = my_element;

Matthias Braun's avatar
Matthias Braun committed
307
308
#if 0
								// ?!?
309
310
								if (my_irn->node_nr == 1883 || my_irn->node_nr == 1858 || my_irn->node_nr == 1936)
									i=1;
Matthias Braun's avatar
Matthias Braun committed
311
#endif
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
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


								first = NULL;
							}
							else
							{
								my_element = ptr_get_new_element(ifg);
								my_element->content_first.element = last_element.element;
								my_element->content_second.irn = my_irn;
								my_element->kind = 3101; /* first is an element, second an ir_node */
								last_element.element = my_element;
								ifg->curr_element = my_element;
							}
						}
					}
					was_first = 0;
				}
			}
			else
			{
				if (bitset_popcnt(my_live) == 1) /* there is only one node left */
				{
					if (last_element.element)
					{
						bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
						{
							ptr_element_t *my_element = ptr_get_new_element(ifg);
							my_element->content_first.element = last_element.element;
							my_element->content_second.irn = my_irn;
							my_element->kind = 3101; /* first is an element, second an ir_node */

							last_element.element = my_element;
							ifg->curr_element = my_element;
						}
					}
					else
					{
						bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
						{
							ptr_element_t *my_element = ptr_get_new_element(ifg);
							my_element->content_first.irn = my_irn;
							my_element->content_second.irn = NULL;
							my_element->kind = 8889;
							last_element.element =  my_element;
							ifg->curr_element = my_element;
						}
					}
				}
			}
			bitset_free(my_live);
			bitset_remv_irn(live, irn);
363
364
		}
	}
365
	bitset_free(live);
366
367
}

368
static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
369
{
370
371
372
373
374
375
	/* this should be replaced using a keywalker of the irphase &ifg.ph */
	ir_node *irn;
	pmap_entry *entry;

	it->ifg = ifg;
	entry = pmap_first(ifg->node_map);
376

377
378
	if (!entry)
		return NULL;
379

380
381
	irn =  entry->value;
	it->curr_irn = irn;
382

383
	return irn;
384
385
}

386
static ir_node *get_next_irn(ptr_iter_t *it)
387
{
388
389
390
	/* this should be replaced using a keywalker of the irphase &ifg.ph */
	ir_node *irn;
	pmap_entry *entry;
391

392
393
	irn = it->curr_irn;
	entry = pmap_next(it->ifg->node_map);
394

395
396
	if (!entry)
		return NULL;
397

398
	it->curr_irn = entry->value;
399

400
401
402
403
404
405
406
407
408
409
410
411
	return entry->value;
}

static ir_node *get_next_neighbour(ptr_iter_t *it)
{
	ir_node *res;
	ptr_head_t *head;
	ptr_element_t *element;

	element = it->curr_element_t;

	if (element == NULL)
412
	{
Matthias Braun's avatar
Matthias Braun committed
413
414
#if 0
		// ?!?
415
416
		if (it->irn->node_nr == 1883 || it->irn->node_nr == 1858)
			i=1;
Matthias Braun's avatar
Matthias Braun committed
417
#endif
418

419
		if (it->curr_ptr_head->list.next != &it->first_head->list)
420
		{
421
422
423
424
425
426
427
			head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
			it->curr_ptr_head = head;
			element = head->element;
		}
		else
			return NULL; /* there are no more neighbours */
	}
428

429
430
431
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
459
460
461
462
463
464
465
466
467
468
469
470
471
	if (element && element->kind == 8889) /* node has no neighbours */
	{
		res = element->content_first.irn;
		it->curr_element_t = NULL;
	}
	else
	{
		if (element && element->kind == 8888) /* node has only one more neighbour */
		{
			if (it->get_first)
			{
				if (element->content_first.irn != it->irn)
				{
					res = element->content_first.irn;
					it->get_first = 0;
					it->curr_element_t = NULL;
				}
				else
				{
					it->get_first = 0;
					it->curr_element_t = NULL;
					it->sub_call++;
					res = get_next_neighbour(it);
					it->sub_call--;
				}
			}
			else
			{
				if (element->content_second.irn != it->irn)
				{
					res = element->content_second.irn;
					it->get_first = 1;
					it->curr_element_t = element;
				}
				else
				{
					it->get_first = 1;
					it->curr_element_t = element;
					it->sub_call++;
					res = get_next_neighbour(it);
					it->sub_call--;
				}
			}
472
473
474
		}
		else
		{
475
476
477
478
479
480
481
482
483
484
			if (element && element->kind == 3101)
			{
				it->curr_element_t = element->content_first.element;
				res = element->content_second.irn;
			}
			else
			{ /* element is only an ir_node */// TODO
				it->curr_element_t = NULL;
				return NULL;
			}
485
486
487
		}
	}

488
489
	if (res && !it->sub_call)
	{
490
		if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
491
492
493
494
495
		{
			res = get_next_neighbour(it);
		}
		else
		{
496
			bitset_set(it->visited_neighbours, get_irn_idx(res));
497
498
499
500
		}
	}

	return res;
501
502
}

503
static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
504
{
505
506
507
	ir_node *res;
	ptr_head_t *head;
	ptr_element_t *element;
508
	bitset_t *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
509
510
511
512
513

	it->ifg = ifg;
	it->irn = irn;
	it->get_first = 0;
	it->sub_call = 0;
514
515

	it->visited_neighbours = bitsetvisited_neighbours;
516
517
518
519
520
521
522
523
524
525
526

	head = phase_get_irn_data(&ifg->ph, irn);
	if (!head)
		return NULL;
	else
	{
		it->first_head = head;
		head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
		it->curr_ptr_head = head;
		element = head->element;
	}
527

528
529
530
531
532
533
	if (element && element->kind == 8889) /* node has no neighbours */
	{
		res = element->content_first.irn;
		it->curr_element_t = NULL;
	}
	else
534
	{
535
		if (element && element->kind == 8888) /* node has only one neighbour */
536
		{
537
			if (it->get_first)
538
			{
539
540
541
542
543
544
545
546
547
548
549
550
551
552
				if (element->content_first.irn != it->irn)
				{
					res = element->content_first.irn;
					it->get_first = 0;
					it->curr_element_t = NULL;
				}
				else
				{
					it->get_first = 0;
					it->curr_element_t = NULL;
					it->sub_call++;
					res = get_next_neighbour(it);
					it->sub_call--;
				}
553
554
555
			}
			else
			{
556
557
558
559
560
561
562
563
564
565
566
567
568
569
				if (element->content_second.irn != it->irn)
				{
					res = element->content_second.irn;
					it->curr_element_t = element;
					it->get_first = 1;
				}
				else
				{
					it->get_first = 1;
					it->curr_element_t = element;
					it->sub_call++;
					res = get_next_neighbour(it);
					it->sub_call--;
				}
570
571
			}
		}
572
573
574
575
576
577
578
579
580
581
582
		else
			if (element && element->kind == 3101)
			{
				it->curr_element_t = element->content_first.element;
				res = element->content_second.irn;
			}
			else
			{ /* element is only an ir_node */
				it->curr_element_t = NULL;
				return NULL;
			}
583
584
	}

585
	if (res && !it->sub_call)
586
	{
587
		if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
588
589
590
591
592
		{
			res = get_next_neighbour(it);
		}
		else
		{
593
			bitset_set(it->visited_neighbours, get_irn_idx(res));
594
		}
595
596
597
598
599
600
	}

	return res;
}


601

602
603
604
605
/* PUBLIC FUNCTIONS */

static void ifg_pointer_free(void *self)
{
606
607
608
	ifg_pointer_t *ifg = self;
	obstack_free(&ifg->obst, NULL);
	phase_free(&ifg->ph);
609
610
611
612

	free(self);
}

Matthias Braun's avatar
Matthias Braun committed
613
static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
614
{
Matthias Braun's avatar
Matthias Braun committed
615
	const ifg_pointer_t *ifg = self;
616
	int connected = -1;
617
	ptr_iter_t it;
618
619
	ir_node *irn = NULL;

620
	irn = get_first_neighbour(ifg, &it, a);
621
622
623
624
625
626
	connected = 0;
	while (irn != NULL)
	{
		if (irn == b)
		{
			connected = 1;
627
			break;
628
		}
629
		irn = get_next_neighbour(&it);
630
631
632
633
634
635
636
	}

	return connected;
}

static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
{
637
	return get_first_neighbour(self, iter, irn);
638
639
640
641
642
643
644
645
646
}

static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
{
	return get_next_neighbour(iter);
}

static void ifg_pointer_neighbours_break(const void *self, void *iter)
{
647
648
649
650
	ptr_iter_t *it = iter;

	bitset_free(it->visited_neighbours);

651
652
653
654
655
	return;
}

static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
{
656
	return get_first_irn(self, iter);
657
658
659
660
}

static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
{
661
	return get_next_irn(iter);
662
663
664
665
666
667
668
669
670
671
}

static void ifg_pointer_nodes_break(const void *self, void *iter)
{
	return;
}

static int ifg_pointer_degree(const void *self, const ir_node *irn)
{
	int degree = -1;
672
	ptr_iter_t it;
673

674
	irn = get_first_neighbour(self, &it, irn);
675
676
677
678
	degree = 0;
	while (irn != NULL)
	{
		degree++;
679
		irn = get_next_neighbour(&it);
680
681
682
683
684
685
	}

	return degree;
}

static const be_ifg_impl_t ifg_pointer_impl = {
686
687
	sizeof(ptr_iter_t),
	sizeof(ptr_iter_t),
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
	0,
	ifg_pointer_free,
	ifg_pointer_connected,
	ifg_pointer_neighbours_begin,
	ifg_pointer_neighbours_next,
	ifg_pointer_neighbours_break,
	ifg_pointer_nodes_begin,
	ifg_pointer_nodes_next,
	ifg_pointer_nodes_break,
	NULL,
	NULL,
	NULL,
	ifg_pointer_degree
};

be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
{
705
	ifg_pointer_t *ifg	= xmalloc(sizeof(*ifg));
706
	ifg->impl     		= &ifg_pointer_impl;
707
708
709
	ifg->env			= env;

	ifg->node_map 		= pmap_create(); /* to find all nodes, should be replaced by a "keywalker" of irphase */
710

711
712
	phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init);
	obstack_init(&ifg->obst);
713

714
	dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
715

716
	obstack_finish(&ifg->obst);
717
718
	return (be_ifg_t *) ifg;
}