opt_blocks.c 32.6 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief   Combining congruent blocks
 * @author  Michael Beck
 * @version $Id$
 *
Michael Beck's avatar
Michael Beck committed
26
 * This phase find congruent blocks.
27
28
29
 * Two block are congruent, if they contains only equal calculations.
 */
#include "config.h"
30

31
#include "iroptimize.h"
32
#include "ircons.h"
33
#include "irgmod.h"
34
35
36
#include "irgraph_t.h"
#include "irnode_t.h"
#include "iropt_t.h"
37
#include "array_t.h"
38
#include "trouts.h"
39
#include "irgwalk.h"
40
#include "set.h"
Michael Beck's avatar
Michael Beck committed
41
#include "irpass.h"
42
#include "debug.h"
43
#include "irtools.h"
44

Michael Beck's avatar
Michael Beck committed
45
46
/* define this for general block shaping: congruent blocks
   are found not only before the end block but anywhere in the graph */
47
#define GENERAL_SHAPE
48

49
50
51
typedef struct partition_t     partition_t;
typedef struct block_t         block_t;
typedef struct node_t          node_t;
Michael Beck's avatar
Michael Beck committed
52
53
typedef struct pair_t          pair_t;
typedef struct phi_t           phi_t;
54
55
56
typedef struct opcode_key_t    opcode_key_t;
typedef struct listmap_entry_t listmap_entry_t;
typedef struct environment_t   environment_t;
57
typedef struct pred_t          pred_t;
58
59
60

/** An opcode map key. */
struct opcode_key_t {
61
	unsigned    code;   /**< The Firm opcode. */
62
63
64
	ir_mode     *mode;  /**< The mode of all nodes in the partition. */
	int         arity;  /**< The arity of this opcode (needed for Phi etc. */
	union {
65
66
		long            proj;   /**< For Proj nodes, its proj number */
		ir_entity       *ent;   /**< For Sel nodes, its entity */
Matthias Braun's avatar
Matthias Braun committed
67
		ir_tarval       *tv;    /**< For Const nodes, its tarval */
68
69
		symconst_symbol sym;    /**< For SymConst nodes, its symbol .*/
		void            *addr;  /**< Alias all addresses. */
70
		int             intVal; /**< For Conv/Div nodes: strict/remainderless. */
71
72
73
74
75
76
77
78
	} u;
};

/** A partition contains all congruent blocks. */
struct partition_t {
	list_head part_list;     /**< Double linked list of partitions. */
	list_head blocks;        /**< List of blocks in this partition. */
	unsigned  n_blocks;      /**< Number of block in this partition. */
79
	ir_node   *meet_block;   /**< The control flow meet block of this partition. */
80
81
82
83
84
85
86
87
88
89
90
#ifdef DEBUG_libfirm
	unsigned  nr;            /**< For debugging: number of this partition. */
#endif
};

/** A block. */
struct block_t {
	list_head  block_list;   /**< Double linked list of block inside a partition. */
	list_head  nodes;        /**< Wait-queue of nodes that must be checked for congruence. */
	block_t    *next;        /**< Next block of a split list. */
	ir_node    *block;       /**< Pointer to the associated IR-node block. */
91
92
	ir_node    **roots;      /**< An array of all root nodes. */
	node_t     *cf_root;     /**< The control flow root node of this block. */
Michael Beck's avatar
Michael Beck committed
93
94
	pair_t     *input_pairs; /**< The list of inputs to this block. */
	phi_t      *phis;        /**< The list of Phis in this block. */
95
96
	block_t    *all_next;    /**< Links all created blocks. */
	int        meet_input;   /**< Input number of this block in the meet-block. */
97
98
99
100
101
102
103
104
105
106
};

/** A node. */
struct node_t {
	list_head  node_list;    /**< Double linked list of block inside a partition. */
	ir_node    *node;        /**< Pointer to the associated IR-node or NULL for block inputs. */
	char       is_input;     /**< Set if this node is an input from other block. */
};

/** The environment. */
Michael Beck's avatar
Michael Beck committed
107
struct environment_t {
108
109
110
	list_head       partitions;     /**< list of partitions. */
	list_head       ready;          /**< list of ready partitions. */
	set             *opcode2id_map; /**< The opcodeMode->id map. */
111
112
	ir_node         **live_outs;    /**< Live out only nodes. */
	block_t         *all_blocks;    /**< List of all created blocks. */
113
114
115
	struct obstack  obst;           /** obstack for temporary data */
};

Michael Beck's avatar
Michael Beck committed
116
/** A (node, input index) pair. */
Michael Beck's avatar
Michael Beck committed
117
118
119
120
121
122
123
124
125
126
127
128
129
130
struct pair_t {
	pair_t  *next;    /**< Points to the next pair entry. */
	ir_node *irn;     /**< The IR-node. */
	int     index;    /**< An input index. */
	ir_node **ins;    /**< A new in array once allocated. */
};

/** A Phi, inputs pair. */
struct phi_t {
	phi_t   *next;    /**< Points to the next Phi pair entry. */
	ir_node *phi;     /**< The Phi node. */
	ir_node **ins;    /**< A new in array once allocated. */
};

131
132
133
134
135
136
/** Describes a predecessor input. */
struct pred_t {
	ir_node *pred;  /**< The predecessor. */
	int     index;  /**< Its input index. */
};

137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/**
 * An entry in the list_map.
 */
struct listmap_entry_t {
	void            *id;    /**< The id. */
	block_t         *list;  /**< The associated list for this id. */
	listmap_entry_t *next;  /**< Link to the next entry in the map. */
};

/** We must map id's to lists. */
typedef struct listmap_t {
	set             *map;    /**< Map id's to listmap_entry_t's */
	listmap_entry_t *values; /**< List of all values in the map. */
} listmap_t;

152
153
#define get_Block_entry(block)  ((block_t *)get_irn_link(block))

154
155
156
157
/** The debug module handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

/** Next partition number. */
158
DEBUG_ONLY(static unsigned part_nr = 0;)
159
160
161
162
163

#ifdef DEBUG_libfirm
/**
 * Dump partition to output.
 */
164
165
static void dump_partition(const char *msg, const partition_t *part)
{
166
167
168
	const block_t *block;
	int           first = 1;

169
	DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n  ", msg, part->nr, part->n_blocks));
170
171
172
173
	list_for_each_entry(block_t, block, &part->blocks, block_list) {
		DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", block->block));
		first = 0;
	}
174
	DB((dbg, LEVEL_2, "\n }\n"));
175
176
177
178
179
}  /* dump_partition */

/**
 * Dumps a list.
 */
180
181
static void dump_list(const char *msg, const block_t *block)
{
182
183
184
	const block_t *p;
	int           first = 1;

185
	DB((dbg, LEVEL_3, "  %s = {\n   ", msg));
186
187
188
189
	for (p = block; p != NULL; p = p->next) {
		DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->block));
		first = 0;
	}
190
	DB((dbg, LEVEL_3, "\n  }\n"));
191
192
193
194
195
196
197
198
199
}  /* do_dump_list */
#else
#define dump_partition(msg, part)
#define dump_list(msg, block)
#endif

/**
 * Compare two pointer values of a listmap.
 */
200
201
static int listmap_cmp_ptr(const void *elt, const void *key, size_t size)
{
202
203
	const listmap_entry_t *e1 = (const listmap_entry_t*)elt;
	const listmap_entry_t *e2 = (const listmap_entry_t*)key;
204
205
206
207
208
209
210
211
212
213

	(void) size;
	return e1->id != e2->id;
}  /* listmap_cmp_ptr */

/**
 * Initializes a listmap.
 *
 * @param map  the listmap
 */
214
215
static void listmap_init(listmap_t *map)
{
216
217
218
219
220
221
222
223
224
	map->map    = new_set(listmap_cmp_ptr, 16);
	map->values = NULL;
}  /* listmap_init */

/**
 * Terminates a listmap.
 *
 * @param map  the listmap
 */
225
226
static void listmap_term(listmap_t *map)
{
227
228
229
230
231
232
233
234
235
236
237
	del_set(map->map);
}  /* listmap_term */

/**
 * Return the associated listmap entry for a given id.
 *
 * @param map  the listmap
 * @param id   the id to search for
 *
 * @return the associated listmap entry for the given id
 */
238
239
static listmap_entry_t *listmap_find(listmap_t *map, void *id)
{
240
241
242
243
244
	listmap_entry_t key, *entry;

	key.id   = id;
	key.list = NULL;
	key.next = NULL;
245
	entry    = (listmap_entry_t*)set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261

	if (entry->list == NULL) {
		/* a new entry, put into the list */
		entry->next = map->values;
		map->values = entry;
	}
	return entry;
}  /* listmap_find */

/**
 * Calculate the hash value for an opcode map entry.
 *
 * @param entry  an opcode map entry
 *
 * @return a hash value for the given opcode map entry
 */
262
263
static unsigned opcode_hash(const opcode_key_t *entry)
{
264
	/* assume long >= int */
265
	return (unsigned)(PTR_TO_INT(entry->mode) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.addr) + entry->arity);
266
267
268
269
270
}  /* opcode_hash */

/**
 * Compare two entries in the opcode map.
 */
271
272
static int cmp_opcode(const void *elt, const void *key, size_t size)
{
273
274
	const opcode_key_t *o1 = (opcode_key_t*)elt;
	const opcode_key_t *o2 = (opcode_key_t*)key;
275
276
277
278

	(void) size;
	return o1->code != o2->code || o1->mode != o2->mode ||
	       o1->arity != o2->arity ||
279
	       o1->u.proj != o2->u.proj || o1->u.addr != o2->u.addr;
280
281
282
}  /* cmp_opcode */

/**
283
284
285
 * Creates a new empty partition and put in on the
 * partitions list.
 *
Michael Beck's avatar
Michael Beck committed
286
 * @param meet_block  the control flow meet block of this partition
287
 * @param env         the environment
288
 */
289
290
static partition_t *create_partition(ir_node *meet_block, environment_t *env)
{
291
	partition_t *part = OALLOC(&env->obst, partition_t);
292
293

	INIT_LIST_HEAD(&part->blocks);
294
295
	part->meet_block = meet_block;
	part->n_blocks   = 0;
296
	DEBUG_ONLY(part->nr = part_nr++;)
297
298
299
300
301
	list_add_tail(&part->part_list, &env->partitions);
	return part;
}  /* create_partition */

/**
302
 * Allocate a new block in the given partition.
303
 *
304
 * @param block      the IR-node
305
 * @param meet_input Input number of this block in the meet-block
306
307
 * @param partition  the partition to add to
 * @param env        the environment
308
 */
309
310
static block_t *create_block(ir_node *block, int meet_input, partition_t *partition, environment_t *env)
{
311
	block_t *bl = OALLOC(&env->obst, block_t);
312

313
314
	set_irn_link(block, bl);

315
	INIT_LIST_HEAD(&bl->nodes);
Michael Beck's avatar
Michael Beck committed
316
317
	bl->next        = NULL;
	bl->block       = block;
318
319
	bl->roots       = NEW_ARR_F(ir_node *, 0);
	bl->cf_root     = NULL;
Michael Beck's avatar
Michael Beck committed
320
321
	bl->input_pairs = NULL;
	bl->phis        = NULL;
322
	bl->meet_input  = meet_input;
323

324
	/* put it into the list of partition blocks */
325
	list_add_tail(&bl->block_list, &partition->blocks);
326
	++partition->n_blocks;
327

328
329
330
331
	/* put in into the list of all blocks */
	bl->all_next    = env->all_blocks;
	env->all_blocks = bl;

332
333
	return bl;
}  /* create_block */
334
335

/**
336
 * Allocate a new node and add it to a blocks wait queue.
337
338
 *
 * @param irn    the IR-node
339
 * @param block  the block to add to
340
341
 * @param env    the environment
 */
342
343
static node_t *create_node(ir_node *irn, block_t *block, environment_t *env)
{
344
	node_t *node = OALLOC(&env->obst, node_t);
345
346
347
348
349

	node->node     = irn;
	node->is_input = 0;

	list_add_tail(&node->node_list, &block->nodes);
350
351
352

	return node;
}  /* create_node */
353

Michael Beck's avatar
Michael Beck committed
354
355
356
357
358
359
360
361
/**
 * Add an input pair to a block.
 *
 * @param block  the block
 * @param irn    the IR-node that has an block input
 * @param idx    the index of the block input in node's predecessors
 * @param env    the environment
 */
362
363
static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env)
{
364
	pair_t *pair = OALLOC(&env->obst, pair_t);
Michael Beck's avatar
Michael Beck committed
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380

	pair->next  = block->input_pairs;
	pair->irn   = irn;
	pair->index = idx;
	pair->ins   = NULL;

	block->input_pairs = pair;
}  /* add_pair */

/**
 * Add a Phi to a block.
 *
 * @param block  the block
 * @param phi    the Phi node
 * @param env    the environment
 */
381
382
static void add_phi(block_t *block, ir_node *phi, environment_t *env)
{
383
	phi_t *node = OALLOC(&env->obst, phi_t);
Michael Beck's avatar
Michael Beck committed
384
385
386
387
388
389
390
391
392
393
394

	node->next = block->phis;
	node->phi  = phi;
	node->ins  = NULL;

	block->phis = node;
}  /** add_phi */

/**
 * Creates an opcode from a node.
 */
395
396
static opcode_key_t *opcode(const node_t *node, environment_t *env)
{
397
398
399
400
401
402
403
404
405
406
407
408
409
410
	opcode_key_t key, *entry;
	ir_node      *irn = node->node;

	if (node->is_input) {
		/* Node: as Block nodes are never propagated, it is safe to
		   use its code for "input" node */
		key.code   = iro_Block;
		key.arity  = 0;
	} else {
		key.code   = get_irn_opcode(irn);
		key.arity  = get_irn_arity(irn);
	}
	key.mode   = get_irn_mode(node->node);
	key.u.proj = 0;
411
	key.u.addr = NULL;
412
413
414
415
416
417
418
419

	switch (key.code) {
	case iro_Proj:
		key.u.proj = get_Proj_proj(irn);
		break;
	case iro_Sel:
		key.u.ent = get_Sel_entity(irn);
		break;
420
421
422
423
424
425
	case iro_SymConst:
		key.u.sym = get_SymConst_symbol(irn);
		break;
	case iro_Const:
		key.u.tv  = get_Const_tarval(irn);
		break;
426
427
428
	case iro_Conv:
		key.u.intVal = get_Conv_strict(irn);
		break;
429
430
431
	case iro_Load:
		key.mode = get_Load_mode(irn);
		break;
432
	case iro_Div:
433
		key.u.intVal = get_Div_no_remainder(irn);
434
		break;
435
436
437
	case iro_Builtin:
		key.u.intVal = get_Builtin_kind(irn);
		break;
438
439
440
441
	default:
		break;
	}

442
	entry = (opcode_key_t*)set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
443
444
445
446
447
448
449
450
451
452
453
454
	return entry;
}  /* opcode */

/**
 * Split a partition by a local list.
 *
 * @param Z    partition to split
 * @param g    a (non-empty) block list
 * @param env  the environment
 *
 * @return  a new partition containing the nodes of g
 */
455
456
static partition_t *split(partition_t *Z, block_t *g, environment_t *env)
{
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
	partition_t *Z_prime;
	block_t     *block;
	unsigned    n = 0;

	dump_partition("Splitting ", Z);
	dump_list("by list ", g);

	assert(g != NULL);

	/* Remove g from Z. */
	for (block = g; block != NULL; block = block->next) {
		list_del(&block->block_list);
		++n;
	}
	assert(n < Z->n_blocks);
	Z->n_blocks -= n;

	/* Move g to a new partition, Z'. */
475
	Z_prime = create_partition(Z->meet_block, env);
476
477
478
479
480
481
482
483
484
485
	for (block = g; block != NULL; block = block->next) {
		list_add_tail(&block->block_list, &Z_prime->blocks);
	}
	Z_prime->n_blocks = n;

	dump_partition("Now ", Z);
	dump_partition("Created new ", Z_prime);
	return Z_prime;
}  /* split */

486
/**
487
 * Return non-zero if pred should be tread as a input node.
488
 */
489
490
static int is_input_node(ir_node *pred, ir_node *irn, int index)
{
491
492
493
494
495
496
497
498
499
500
	/* for now, do NOT turn direct calls into indirect one */
	if (index != 1)
		return 1;
	if (! is_SymConst_addr_ent(pred))
		return 1;
	if (! is_Call(irn))
		return 1;
	return 0;
}  /* is_input_node */

501
502
503
504
/**
 * Propagate nodes on all wait queues of the given partition.
 *
 * @param part  the partition
505
 * @param env   the environment
506
 */
507
508
static void propagate_blocks(partition_t *part, environment_t *env)
{
509
510
511
512
513
514
	block_t         *ready_blocks = NULL;
	unsigned        n_ready       = 0;
	block_t         *bl, *next;
	listmap_t       map;
	listmap_entry_t *iter;

515
	DB((dbg, LEVEL_2, " Propagate blocks on part%u\n", part->nr));
516

517
	/* Let map be an empty mapping from the range of Opcodes to (local) list of blocks. */
518
519
520
521
522
523
524
525
526
527
	listmap_init(&map);
	list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
		opcode_key_t    *id;
		listmap_entry_t *entry;
		node_t          *node;

		if (list_empty(&bl->nodes)) {
			bl->next     = ready_blocks;
			ready_blocks = bl;
			++n_ready;
528
			DB((dbg, LEVEL_2, " Block %+F completely processed\n", bl->block));
529
530
531
532
533
534
535
536
537
538
539
540
			continue;
		}

		/* get the first node from the wait queue */
		node = list_entry(bl->nodes.next, node_t, node_list);
		list_del(&node->node_list);

		/* put all not-visited predecessors to the wait queue */
		if (! node->is_input) {
			ir_node *irn = node->node;
			int     i;

541
			DB((dbg, LEVEL_3, "  propagate %+F\n", irn));
542
543
544
545
546
547
548
			ir_normalize_node(node->node);
			for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
				ir_node *pred  = get_irn_n(irn, i);
				ir_node *block = get_nodes_block(skip_Proj(pred));
				node_t *p_node;

				if (block != bl->block) {
549
					p_node = create_node(pred, bl, env);
550
551
					if (is_input_node(pred, irn, i)) {
						/* is a block live input */
552
553
554
						p_node->is_input = 1;
						if (! is_Phi(irn))
							add_pair(bl, irn, i, env);
555
556
557
					} else if (is_Phi(pred)) {
						/* update the Phi list */
						add_phi(bl, pred, env);
558
					}
559
560
				} else if (! irn_visited_else_mark(pred)) {
					/* not yet visited, ok */
561
					p_node = create_node(pred, bl, env);
Michael Beck's avatar
Michael Beck committed
562
563
564
565
566

					if (is_Phi(pred)) {
						/* update the Phi list */
						add_phi(bl, pred, env);
					}
567
568
569
570
571
572
				}
			}
		} else {
			DB((dbg, LEVEL_3, "  propagate Input %+F\n", node->node));
		}

Michael Beck's avatar
Michael Beck committed
573
		/* Add bl to map[opcode(n)]. */
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
		id          = opcode(node, env);
		entry       = listmap_find(&map, id);
		bl->next    = entry->list;
		entry->list = bl;
	}

	/* split out ready blocks */
	if (n_ready > 0) {
		partition_t *Z;

		if (n_ready < part->n_blocks)
			Z = split(part, ready_blocks, env);
		else
			Z = part;
		list_del(&Z->part_list);

		if (Z->n_blocks > 1) {
591
			DB((dbg, LEVEL_2, " Partition %u is ready\n", Z->nr));
592
593
			list_add(&Z->part_list, &env->ready);
		} else {
594
			DB((dbg, LEVEL_2, " Partition %u contains only one block, killed\n", Z->nr));
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
		}
	}

	/* for all sets S except one in the range of map do */
	for (iter = map.values; iter != NULL; iter = iter->next) {
		block_t *S;

		if (iter->next == NULL) {
			/* this is the last entry, ignore */
			break;
		}
		S = iter->list;

		/* Add SPLIT( X, S ) to P. */
		split(part, S, env);
	}
	listmap_term(&map);
}  /* propagate_blocks */

/**
 * Propagate nodes on all wait queues.
 *
 * @param env    the environment
 */
619
620
static void propagate(environment_t *env)
{
621
622
623
	partition_t *part, *next;

	list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
624
625
		if (part->n_blocks < 2) {
			/* zero or one block left, kill this partition */
626
			list_del(&part->part_list);
627
			DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
628
629
630
631
632
		} else
			propagate_blocks(part, env);
	}
}  /* propagate */

633
634
635
/**
 * Map a block to the phi[block->input] live-trough.
 */
636
637
static void *live_throughs(const block_t *bl, const ir_node *phi)
{
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
	ir_node *input = get_Phi_pred(phi, bl->meet_input);

	/* If this input is inside our block, this
	   is a live-out and not a live trough.
	   Live-outs are tested inside propagate, so map all of
	   them to the "general" value NULL */
	if (get_nodes_block(input) == bl->block)
		return NULL;
	return input;
}  /* live_throughs */

/**
 * Split partition by live-outs and live-troughs.
 *
 * @param part  the partition
 * @param env   the environment
 */
655
static void propagate_blocks_live_troughs(partition_t *part, environment_t *env)
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
	const ir_node   *meet_block = part->meet_block;
	block_t         *bl, *next;
	listmap_t       map;
	listmap_entry_t *iter;
	const ir_node   *phi;

	DB((dbg, LEVEL_2, " Propagate live-troughs on part%u\n", part->nr));

	for (phi = get_Block_phis(meet_block); phi != NULL; phi = get_Phi_next(phi)) {
		/* propagate on all Phis of the meet-block */

		if (part->n_blocks < 2) {
			/* zero or one block left, kill this partition */
			list_del(&part->part_list);
			DB((dbg, LEVEL_2, " Partition %u contains less than 2 blocks, killed\n", part->nr));
			return;
		}

		/* Let map be an empty mapping from the range of live-troughs to (local) list of blocks. */
		listmap_init(&map);
		list_for_each_entry_safe(block_t, bl, next, &part->blocks, block_list) {
			opcode_key_t    *id;
			listmap_entry_t *entry;

			/* Add bl to map[live_trough(bl)]. */
682
			id          = (opcode_key_t*)live_throughs(bl, phi);
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
			entry       = listmap_find(&map, id);
			bl->next    = entry->list;
			entry->list = bl;
		}

		/* for all sets S except one in the range of map do */
		for (iter = map.values; iter != NULL; iter = iter->next) {
			block_t *S;

			if (iter->next == NULL) {
				/* this is the last entry, ignore */
				break;
			}
			S = iter->list;

			/* Add SPLIT( X, S ) to P. */
			split(part, S, env);
		}
		listmap_term(&map);
	}
}  /* propagate_blocks_live_troughs */

/**
 * Propagate live-troughs on all partitions on the partition list.
 *
 * @param env    the environment
 */
710
static void propagate_live_troughs(environment_t *env)
711
{
712
713
714
715
716
717
718
	partition_t *part, *next;

	list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) {
		propagate_blocks_live_troughs(part, env);
	}
}  /* propagate_live_troughs */

Michael Beck's avatar
Michael Beck committed
719
720
721
722
723
724
725
726
727
728
729
/**
 * Apply analysis results by replacing all blocks of a partition
 * by one representative.
 *
 * Route all inputs from all block of the partition to the one
 * representative.
 * Enhance all existing Phis by combining them.
 * Create new Phis for all previous input nodes.
 *
 * @param part  the partition to process
 */
730
731
static void apply(ir_graph *irg, partition_t *part)
{
Michael Beck's avatar
Michael Beck committed
732
733
	block_t *repr = list_entry(part->blocks.next, block_t, block_list);
	block_t *bl;
734
735
	ir_node *block, *end, *meet_block, *p, *next;
	ir_node **ins, **phi_ins;
Michael Beck's avatar
Michael Beck committed
736
737
	phi_t   *repr_phi, *phi;
	pair_t  *repr_pair, *pair;
738
	int     i, j, k, n, n_phis;
Michael Beck's avatar
Michael Beck committed
739
740
741
742
743
744
745
746

	list_del(&repr->block_list);

	/* prepare new in arrays for the block ... */
	block = repr->block;
	n     = get_Block_n_cfgpreds(block);
	ins   = NEW_ARR_F(ir_node *, n);

747
	for (i = 0; i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
748
		ins[i] = get_Block_cfgpred(block, i);
749
	}
Michael Beck's avatar
Michael Beck committed
750
751
752
753
754
755

	/* ... for all existing Phis ... */
	for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
		repr_phi->ins = NEW_ARR_F(ir_node *, n);

		for (i = 0; i < n; ++i)
756
			repr_phi->ins[i] = get_Phi_pred(repr_phi->phi, i);
Michael Beck's avatar
Michael Beck committed
757
758
759
760
	}

	/* ... and all newly created Phis */
	for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
761
762
763
764
765
		ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);

		repr_pair->ins = NEW_ARR_F(ir_node *, n);
		for (i = 0; i < n; ++i)
			repr_pair->ins[i] = input;
Michael Beck's avatar
Michael Beck committed
766
767
	}

768
769
	DB((dbg, LEVEL_1, "Replacing "));

Michael Beck's avatar
Michael Beck committed
770
771
772
773
774
	/* collect new in arrays */
	end = get_irg_end(irg);
	list_for_each_entry(block_t, bl, &part->blocks, block_list) {
		block = bl->block;

775
776
		DB((dbg, LEVEL_1, "%+F, ", block));

Michael Beck's avatar
Michael Beck committed
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
		/* first step: kill any keep-alive from this block */
		for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
			ir_node *ka = get_End_keepalive(end, i);

			if (is_Block(ka)) {
				if (ka == block)
					remove_End_keepalive(end, ka);
			} else {
				if (get_nodes_block(ka) == block)
					remove_End_keepalive(end, ka);
			}
		}

		/* second step: update control flow */
		n = get_Block_n_cfgpreds(block);
		for (i = 0; i < n; ++i) {
793
794
			ir_node *pred = get_Block_cfgpred(block, i);
			ARR_APP1(ir_node *, ins, pred);
Michael Beck's avatar
Michael Beck committed
795
796
797
798
799
800
		}

		/* third step: update Phis */
		for (repr_phi = repr->phis, phi = bl->phis;
		     repr_phi != NULL;
		     repr_phi = repr_phi->next, phi = phi->next) {
801
802
803
804
			for (i = 0; i < n; ++i) {
				ir_node *pred = get_Phi_pred(phi->phi, i);
				ARR_APP1(ir_node *, repr_phi->ins, pred);
			}
Michael Beck's avatar
Michael Beck committed
805
806
807
808
809
810
		}

		/* fourth step: update inputs for new Phis */
		for (repr_pair = repr->input_pairs, pair = bl->input_pairs;
		     repr_pair != NULL;
		     repr_pair = repr_pair->next, pair = pair->next) {
811
812
813
814
			ir_node *input = get_irn_n(pair->irn, pair->index);

			for (i = 0; i < n; ++i)
				ARR_APP1(ir_node *, repr_pair->ins, input);
Michael Beck's avatar
Michael Beck committed
815
816
817
		}
	}

818
	DB((dbg, LEVEL_1, "by %+F\n", repr->block));
Michael Beck's avatar
Michael Beck committed
819
820
821

	/* rewire block input ... */
	n = ARR_LEN(ins);
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851

	/*
	 * Some problem here. For:
	 * if (x) y = 1; else y = 2;
	 *
	 * the following code is constructed:
	 *
	 * b0: if (x) goto b1; else goto b1;
	 * b1: y = Phi(1,2)
	 *
	 * However, both predecessors of b1 are b0, making the Phi
	 * "wrong".
	 *
	 * We solve this by fixing critical edges.
	 */
	for (i = 0; i < n; ++i) {
		ir_node     *pred = ins[i];
		const ir_op *cfop;

		if (is_Bad(pred))
			continue;

		cfop = get_irn_op(skip_Proj(pred));
		if (is_op_fragile(cfop)) {
			/* ignore exception flow */
			continue;
		}
		if (is_op_forking(cfop)) {
			/* a critical edge */
			ir_node *block = new_r_Block(irg, 1, &ins[i]);
852
			ir_node *jmp   = new_r_Jmp(block);
853
854
855
856
			ins[i] = jmp;
		}
	}

Michael Beck's avatar
Michael Beck committed
857
858
859
860
861
862
863
864
865
866
867
868
869
870
	block = repr->block;
	set_irn_in(block, n, ins);
	DEL_ARR_F(ins);

	/* ... existing Phis ... */
	for (repr_phi = repr->phis; repr_phi != NULL; repr_phi = repr_phi->next) {
		set_irn_in(repr_phi->phi, n, repr_phi->ins);
		DEL_ARR_F(repr_phi->ins);
	}

	/* ... and all inputs by creating new Phis ... */
	for (repr_pair = repr->input_pairs; repr_pair != NULL; repr_pair = repr_pair->next) {
		ir_node *input = get_irn_n(repr_pair->irn, repr_pair->index);
		ir_mode *mode  = get_irn_mode(input);
871
		ir_node *phi   = new_r_Phi(block, n, repr_pair->ins, mode);
Michael Beck's avatar
Michael Beck committed
872
873
874

		set_irn_n(repr_pair->irn, repr_pair->index, phi);
		DEL_ARR_F(repr_pair->ins);
875
876
877
878

		/* might be optimized away */
		if (is_Phi(phi))
			add_Block_phi(block, phi);
Michael Beck's avatar
Michael Beck committed
879
880
	}

881
882
883
	/* ... finally rewire the meet block and fix its Phi-nodes */
	meet_block = part->meet_block;
	n         = get_Block_n_cfgpreds(meet_block);
Michael Beck's avatar
Michael Beck committed
884
885
886

	ins = NEW_ARR_F(ir_node *, n);

887
888
889
890
891
892
893
	n_phis = 0;
	for (p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p)) {
		++n_phis;
	}

	phi_ins = NEW_ARR_F(ir_node *, n_phis * n);

Michael Beck's avatar
Michael Beck committed
894
	for (i = j = 0; i < n; ++i) {
895
		ir_node *pred = get_Block_cfgpred(meet_block, i);
Michael Beck's avatar
Michael Beck committed
896
897

		list_for_each_entry(block_t, bl, &part->blocks, block_list) {
898
899
900
901
			if (bl->cf_root->node == pred)
				goto continue_outer;
		}
		ins[j] = pred;
Michael Beck's avatar
Michael Beck committed
902

903
904
		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = get_Phi_next(p), ++k) {
			phi_ins[k * n + j] = get_Phi_pred(p, i);
Michael Beck's avatar
Michael Beck committed
905
		}
906
907
908
		++j;

continue_outer:
909
		;
Michael Beck's avatar
Michael Beck committed
910
	}
911

912
913
914
915
916
917
918
919
920
921
922
923
	/* fix phis */
	if (j == 1) {
		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
			next = get_Phi_next(p);

			exchange(p, phi_ins[k * n]);
		}
		/* all Phis killed */
		set_Block_phis(meet_block, NULL);
	} else {
		for (k = 0, p = get_Block_phis(meet_block); p != NULL; p = next, ++k) {
			next = get_Phi_next(p);
Michael Beck's avatar
Michael Beck committed
924

925
926
927
			set_irn_in(p, j, &phi_ins[k * n]);
		}
	}
928
	DEL_ARR_F(phi_ins);
929

930
931
932
	/* fix inputs of the meet block */
	set_irn_in(meet_block, j, ins);
	DEL_ARR_F(ins);
Michael Beck's avatar
Michael Beck committed
933
934
}  /* apply */

935
936
937
938
939
940
/**
 * Create a partition for a the end block.
 *
 * @param end_block  the end block
 * @param env        the environment
 */
941
942
static void partition_for_end_block(ir_node *end_block, environment_t *env)
{
943
944
945
946
	partition_t *part = create_partition(end_block, env);
	ir_node     *end;
	int         i;

947
	/* collect normal blocks */
948
949
	for (i = get_Block_n_cfgpreds(end_block) - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfgpred(end_block, i);
950
951
952
953
954
955
956
		ir_node *block;
		block_t *bl;
		node_t  *node;

		mark_irn_visited(pred);

		block = get_nodes_block(pred);
957
		bl    = create_block(block, i, part, env);
958
959
		node  = create_node(pred, bl, env);

960
961
962
963
		bl->cf_root = node;
	}

	/* collect all no-return blocks */
964
	end = get_irg_end(get_irn_irg(end_block));
965
966
967
968
969
970
971
972
973
974
975
976
	for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
		ir_node *ka    = get_End_keepalive(end, i);
		ir_node *block;
		block_t *bl;
		node_t  *node;

		if (! is_Call(ka))
			continue;
		mark_irn_visited(ka);

		/* found one */
		block = get_nodes_block(ka);
977
		bl    = create_block(block, -1, part, env);
978
979
980
981
982
983
984
985
		node  = create_node(ka, bl, env);

		bl->cf_root = node;
	}

	dump_partition("Created", part);
}  /* partition_for_end_block */

986
987
988
989
990
991
992
993
994
#ifdef GENERAL_SHAPE
/**
 * Create a partition for a given meet block.
 *
 * @param block    the meet block
 * @param preds    array of candidate predecessors
 * @param n_preds  number of elements in preds
 * @param env      the environment
 */
995
996
static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, environment_t *env)
{
997
998
999
1000
	partition_t *part = create_partition(block, env);
	int         i;

	for (i = n_preds - 1; i >= 0; --i) {
1001
		ir_node *pred = preds[i].pred;
1002
1003
1004
1005
1006
1007
1008
		ir_node *block;
		block_t *bl;
		node_t  *node;

		mark_irn_visited(pred);

		block = get_nodes_block(pred);
1009
		bl    = create_block(block, preds[i].index, part, env);
1010
1011
1012
1013
1014
1015
1016
1017
		node  = create_node(pred, bl, env);

		bl->cf_root = node;
	}

	dump_partition("Created", part);
}  /* partition_for_block */

1018
1019
1020
1021
/**
 * Walker: clear the links of all block phi lists and normal
 * links.
 */
1022
1023
static void clear_phi_links(ir_node *irn, void *env)
{
1024
	(void) env;
1025
1026
1027
1028
1029
1030
1031
	if (is_Block(irn)) {
		set_Block_phis(irn, NULL);
		set_irn_link(irn, NULL);
	}
}  /* clear_phi_links */

/**
1032
 * Walker, detect live-out nodes.
1033
 */
1034
1035
static void find_liveouts(ir_node *irn, void *ctx)
{
1036
	environment_t *env        = (environment_t*)ctx;
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
	ir_node       **live_outs = env->live_outs;
	ir_node       *this_block;
	int           i;

	if (is_Block(irn))
		return;

	/* ignore Keep-alives */
	if (is_End(irn))
		return;

	this_block = get_nodes_block(irn);

	if (is_Phi(irn)) {
		/* update the Phi list */
		add_Block_phi(this_block, irn);
1053
1054
	}

1055
1056
1057
1058
1059
	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
		ir_node *pred_block;
		ir_node *pred = get_irn_n(irn, i);
		int     idx   = get_irn_idx(pred);

1060
1061
		if (live_outs[idx] != NULL) {
			/* already marked as live-out */
1062
1063
1064
1065
			return;
		}

		pred_block = get_nodes_block(pred);
1066
1067
		/* Phi nodes always refer to live-outs */
		if (is_Phi(irn) || this_block != pred_block) {
1068
1069
1070
1071
			/* pred is a live-out */
			live_outs[idx] = pred_block;
		}
	}
1072
}  /* find_liveouts */
1073
1074

/**
yb9976's avatar
yb9976 committed
1075
 * Check if the current block is the meet block of its predecessors.
1076
 */
1077
1078
static void check_for_cf_meet(ir_node *block, void *ctx)
{
1079
	environment_t *env = (environment_t*)ctx;
1080
	int           i, k, n;
1081
	pred_t        *preds;
1082

1083
	if (block == get_irg_end_block(get_irn_irg(block))) {
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
		/* always create a partition for the end block */
		partition_for_end_block(block, env);
		return;
	}

	n = get_Block_n_cfgpreds(block);
	if (n <= 1) {
		/* Must have at least two predecessors */
		return;
	}

1095
	NEW_ARR_A(pred_t, preds, n);
1096
1097
1098
1099
1100
	k = 0;
	for (i = n - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfgpred(block, i);

		/* pred must be a direct jump to us */
1101
		if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred))
1102
			continue;
1103

1104
1105
1106
		preds[k].pred  = pred;
		preds[k].index = i;
		++k;
1107
1108
1109
1110
1111
1112
1113
1114
1115
	}

	if (k > 1)
		partition_for_block(block, preds, k, env);
}  /* check_for_cf_meet */

/**
 * Compare two nodes for root ordering.
 */
1116
1117
static int cmp_nodes(const void *a, const void *b)
{
1118
1119
	const ir_node *const *pa = (const ir_node*const*)a;
	const ir_node *const *pb = (const ir_node*const*)b;
1120
1121
	const ir_node  *irn_a  = *pa;
	const ir_node  *irn_b  = *pb;
1122
1123
	unsigned       code_a  = get_irn_opcode(irn_a);
	unsigned       code_b  = get_irn_opcode(irn_b);
1124
1125
	ir_mode        *mode_a, *mode_b;
	unsigned       idx_a, idx_b;
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147

	/* try opcode first */
	if (code_a != code_b)
		return code_a - code_b;

	/* try mode */
	mode_a = get_irn_mode(irn_a);
	mode_b = get_irn_mode(irn_b);

	if (mode_a != mode_b)
		return mode_a < mode_b ? -1 : +1;

	/* last resort: index */
	idx_a = get_irn_idx(irn_a);
	idx_b = get_irn_idx(irn_b);

	return (idx_a > idx_b) - (idx_a < idx_b);
}  /* cmp_nodes */

/**
 * Add the roots to all blocks.
 */
1148
1149
static void add_roots(ir_graph *irg, environment_t *env)
{
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
	unsigned idx, n      = get_irg_last_idx(irg);
	ir_node  **live_outs = env->live_outs;
	block_t  *bl;

	for (idx = 0; idx < n; ++idx) {
		ir_node *block = live_outs[idx];

		if (block != NULL && is_Block(block)) {
			block_t *bl = get_Block_entry(block);

			if (bl != NULL) {
				ir_node *irn = get_idx_irn(irg, idx);

				if (!irn_visited_else_mark(irn)) {
					ARR_APP1(ir_node *, bl->roots, irn);
				}
			}
1167
1168
		}
	}
1169
1170
	/*
	 * Now sort the roots to normalize them as good as possible.
Michael Beck's avatar
Michael Beck committed
1171
     * Else, we will split identical blocks if we start which different roots.
1172
1173
	 */
	for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) {
1174
		size_t i, n = ARR_LEN(bl->roots);
1175

1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
#if 1
		/* TODO: is this really needed? The roots are already in
		   idx-order by construction, which might be good enough. */
		qsort(bl->roots, n, sizeof(bl->roots[0]), cmp_nodes);
#endif

		DB((dbg, LEVEL_2, " Adding Roots for block %+F\n  ", bl->block));
		/* ok, add them sorted */
		for (i = 0; i < n; ++i) {
			DB((dbg, LEVEL_2, "%+F, ", bl->roots[i]));
			create_node(bl->roots[i], bl, env);
		}
		DB((dbg, LEVEL_2, "\n"));
		DEL_ARR_F(bl->roots);
		bl->roots = NULL;
	}
}  /* add_roots */
1193
#endif /* GENERAL_SHAPE */
1194

Michael Beck's avatar
Michael Beck committed
1195
/* Combines congruent end blocks into one. */
1196
1197
int shape_blocks(ir_graph *irg)
{
1198
1199
	environment_t env;
	partition_t   *part;
Michael Beck's avatar
Michael Beck committed
1200
	block_t       *bl;
1201
	int           res, n;
1202
1203
1204
1205

	/* register a debug mask */
	FIRM_DBG_REGISTER(dbg, "firm.opt.blocks");

1206
	DEBUG_ONLY(part_nr = 0;)
1207
1208
1209
1210
	DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg));

	/* works better, when returns are placed at the end of the blocks */
	normalize_n_returns(irg);
1211
1212
1213
1214
1215
1216

	obstack_init(&env.obst);
	INIT_LIST_HEAD(&env.partitions);
	INIT_LIST_HEAD(&env.ready);
	env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);

1217
1218
1219
1220
1221
1222
1223
1224
	n             = get_irg_last_idx(irg);
	env.live_outs = NEW_ARR_F(ir_node *, n);
	memset(env.live_outs, 0, sizeof(*env.live_outs) * n);

	env.all_blocks = NULL;

	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);

1225
#ifdef GENERAL_SHAPE
1226
1227
1228
1229
1230
	/*
	 * Detect, which nodes are live-out only: these are the roots of our blocks.
	 * Build phi lists.
	 */
	irg_walk_graph(irg, clear_phi_links, find_liveouts, &env);
1231
#endif
1232
1233
1234
1235

	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);

	inc_irg_visited(irg);
1236
#ifdef GENERAL_SHAPE
1237
1238
1239
1240
1241
1242
1243
	/*
	 * Detect all control flow meets and create partitions.
	 */
	irg_block_walk_graph(irg, NULL, check_for_cf_meet, &env);

	/* add root nodes to the partition blocks */
	add_roots(irg, &env);
1244
1245
1246
#else
	partition_for_end_block(get_irg_end_block(irg), &env);
#endif
1247

1248
	propagate_live_troughs(&env);
1249
1250
1251
	while (! list_empty(&env.partitions))
		propagate(&env);

Michael Beck's avatar
Michael Beck committed
1252
	res = !list_empty(&env.ready);
1253
1254
	//if (res) dump_ir_block_graph(irg, "-before");

Michael Beck's avatar
Michael Beck committed
1255

1256
1257
	list_for_each_entry(partition_t, part, &env.ready, part_list) {
		dump_partition("Ready Partition", part);
Michael Beck's avatar
Michael Beck committed
1258
		apply(irg, part);
1259
	}
1260
1261
1262
1263
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);

	if (res) {
		/* control flow changed */
1264
1265
		clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
		                   | IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
1266
1267
1268
1269
1270

		/* Calls might be removed. */
		set_trouts_inconsistent();
	}

Michael Beck's avatar
Michael Beck committed
1271
1272
1273
1274
	for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) {
		DEL_ARR_F(bl->roots);
	}

1275
	DEL_ARR_F(env.live_outs);
1276
1277
	del_set(env.opcode2id_map);
	obstack_free(&env.obst, NULL);
Michael Beck's avatar
Michael Beck committed
1278
1279

	return res;
1280
}  /* shape_blocks */
Michael Beck's avatar
Michael Beck committed
1281

1282
1283
ir_graph_pass_t *shape_blocks_pass(const char *name)
{
Michael Beck's avatar
Michael Beck committed
1284
1285
	return def_graph_pass_ret(name ? name : "shape_blocks", shape_blocks);
}  /* shape_blocks_pass */