combo.c 93.1 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
8
9
 */

/**
 * @file
 * @brief   Cliff Click's Combined Analysis/Optimization
 * @author  Michael Beck
10
 *
11
 * This is a slightly enhanced version of Cliff Clicks combo algorithm
Michael Beck's avatar
Michael Beck committed
12
 * - support for commutative nodes is added, Add(a,b) and Add(b,a) ARE congruent
13
14
 * - supports all Firm direct (by a data edge) identities except Mux
 *   (Mux can be a 2-input or 1-input identity, only 2-input is implemented yet)
Michael Beck's avatar
Michael Beck committed
15
 * - supports Confirm nodes (handle them like Copies but do NOT remove them)
yb9976's avatar
yb9976 committed
16
 * - let Cmp nodes calculate Top like all other data nodes: this would let
Michael Beck's avatar
Michael Beck committed
17
 *   Mux nodes to calculate Unknown instead of taking the true result
yb9976's avatar
yb9976 committed
18
 * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reevaluated
Michael Beck's avatar
Michael Beck committed
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 *   IFF the predecessor changed its type. Because nodes are initialized with Top
 *   this never happens, let all Proj(Cond) be unreachable.
 *   We avoid this condition by the same way we work around Phi: whenever a Block
 *   node is placed on the list, place its Cond nodes (and because they are Tuple
 *   all its Proj-nodes either on the cprop list)
 *   Especially, this changes the meaning of Click's example:
 *
 *   int main() {
 *     int x;
 *
 *     if (x == 2)
 *       printf("x == 2\n");
 *     if (x == 3)
 *       printf("x == 3\n");
 *   }
 *
 *   Would print:
 *   x == 2
 *   x == 3
 *
 *   using Click's version while is silent with our.
40
41
 * - support for global congruences is implemented but not tested yet
 *
Michael Beck's avatar
Michael Beck committed
42
 * Note further that we use the terminology from Click's work here, which is different
43
 * in some cases from Firm terminology.  Especially, Click's type is a
44
 * Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
45
46
 */
#include <assert.h>
47
48
49

#include "iroptimize.h"
#include "irflag.h"
50
#include "ircons.h"
51
#include "list.h"
52
53
#include "set.h"
#include "pmap.h"
54
55
56
#include "obstack.h"
#include "irgraph_t.h"
#include "irnode_t.h"
57
#include "iropt_t.h"
58
59
60
61
#include "irgwalk.h"
#include "irop.h"
#include "irouts.h"
#include "irgmod.h"
62
#include "iropt_dbg.h"
63
#include "debug.h"
64
#include "array.h"
65
#include "error.h"
66
#include "irnodeset.h"
67
#include "tv_t.h"
68
#include "firmstat_t.h"
69

70
71
72
#include "irprintf.h"
#include "irdump.h"

73
/* define this to check that all type translations are monotone */
74
#define VERIFY_MONOTONE
75

76
77
78
/* define this to check the consistency of partitions */
#define CHECK_PARTITIONS

79
typedef struct node_t            node_t;
80
typedef struct partition_t       partition_t;
81
82
83
84
85
86
87
88
89
90
typedef struct opcode_key_t      opcode_key_t;
typedef struct listmap_entry_t   listmap_entry_t;

/** The type of the compute function. */
typedef void (*compute_func)(node_t *node);

/**
 * An opcode map key.
 */
struct opcode_key_t {
91
	ir_node *irn;    /**< An IR node representing this opcode. */
92
};
93

94
95
96
97
/**
 * An entry in the list_map.
 */
struct listmap_entry_t {
Michael Beck's avatar
Michael Beck committed
98
	void            *id;    /**< The id. */
99
100
101
102
103
104
105
106
107
108
	node_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;

109
110
111
112
113
/**
 * A lattice element. Because we handle constants and symbolic constants different, we
 * have to use this union.
 */
typedef union {
Matthias Braun's avatar
Matthias Braun committed
114
	ir_tarval      *tv;
115
	ir_entity      *ent;
116
} lattice_elem_t;
117
118
119
120
121

/**
 * A node.
 */
struct node_t {
122
	ir_node         *node;          /**< The IR-node itself. */
123
	list_head       node_list;      /**< Double-linked list of leader/follower entries. */
Michael Beck's avatar
BugFix:    
Michael Beck committed
124
	list_head       cprop_list;     /**< Double-linked partition.cprop list. */
125
126
	partition_t     *part;          /**< points to the partition this node belongs to */
	node_t          *next;          /**< Next node on local list (partition.touched, fallen). */
127
	node_t          *race_next;     /**< Next node on race list. */
128
129
	lattice_elem_t  type;           /**< The associated lattice element "type". */
	int             max_user_input; /**< Maximum input number of Def-Use edges. */
Matthias Braun's avatar
Matthias Braun committed
130
131
	unsigned        next_edge;      /**< Index of the next Def-Use edge to use. */
	unsigned        n_followers;    /**< Number of Follower in the outs set. */
132
133
	unsigned        on_touched:1;   /**< Set, if this node is on the partition.touched set. */
	unsigned        on_cprop:1;     /**< Set, if this node is on the partition.cprop list. */
134
	unsigned        on_fallen:1;    /**< Set, if this node is on the fallen list. */
135
	unsigned        is_follower:1;  /**< Set, if this node is a follower. */
Michael Beck's avatar
Michael Beck committed
136
	unsigned        flagged:2;      /**< 2 Bits, set if this node was visited by race 1 or 2. */
137
138
139
140
141
142
};

/**
 * A partition containing congruent nodes.
 */
struct partition_t {
143
144
	list_head         Leader;          /**< The head of partition Leader node list. */
	list_head         Follower;        /**< The head of partition Follower node list. */
Michael Beck's avatar
BugFix:    
Michael Beck committed
145
	list_head         cprop;           /**< The head of partition.cprop list. */
146
	list_head         cprop_X;         /**< The head of partition.cprop (Cond nodes and its Projs) list. */
147
148
149
	partition_t       *wl_next;        /**< Next entry in the work list if any. */
	partition_t       *touched_next;   /**< Points to the next partition in the touched set. */
	partition_t       *cprop_next;     /**< Points to the next partition in the cprop list. */
Michael Beck's avatar
Michael Beck committed
150
	partition_t       *split_next;     /**< Points to the next partition in the list that must be split by split_by(). */
151
	node_t            *touched;        /**< The partition.touched set of this partition. */
152
	unsigned          n_leader;        /**< Number of entries in this partition.Leader. */
153
154
155
156
157
	unsigned          n_touched;       /**< Number of entries in the partition.touched. */
	int               max_user_inputs; /**< Maximum number of user inputs of all entries. */
	unsigned          on_worklist:1;   /**< Set, if this partition is in the work list. */
	unsigned          on_touched:1;    /**< Set, if this partition is on the touched set. */
	unsigned          on_cprop:1;      /**< Set, if this partition is on the cprop list. */
158
	unsigned          type_is_T_or_C:1;/**< Set, if all nodes in this partition have type Top or Constant. */
Michael Beck's avatar
Michael Beck committed
159
#ifdef DEBUG_libfirm
160
161
	partition_t       *dbg_next;       /**< Link all partitions for debugging */
	unsigned          nr;              /**< A unique number for (what-)mapping, >0. */
Michael Beck's avatar
Michael Beck committed
162
#endif
163
164
165
};

typedef struct environment_t {
166
167
168
169
	struct obstack  obst;           /**< obstack to allocate data structures. */
	partition_t     *worklist;      /**< The work list. */
	partition_t     *cprop;         /**< The constant propagation list. */
	partition_t     *touched;       /**< the touched set. */
170
	partition_t     *initial;       /**< The initial partition. */
171
	set             *opcode2id_map; /**< The opcodeMode->id map. */
172
	ir_node         **kept_memory;  /**< Array of memory nodes that must be kept. */
173
174
	int             end_idx;        /**< -1 for local and 0 for global congruences. */
	int             lambda_input;   /**< Captured argument for lambda_partition(). */
175
176
	unsigned        modified:1;     /**< Set, if the graph was modified. */
	unsigned        unopt_cf:1;     /**< If set, control flow is not optimized due to Unknown. */
177
178
179
	/* options driving the optimization */
	unsigned        commutative:1;  /**< Set, if commutation nodes should be handled specially. */
	unsigned        opt_unknown:1;  /**< Set, if non-strict programs should be optimized. */
180
181
182
#ifdef DEBUG_libfirm
	partition_t     *dbg_list;      /**< List of all partitions. */
#endif
183
184
} environment_t;

185
/** Type of the what function. */
Michael Beck's avatar
Michael Beck committed
186
typedef void *(*what_func)(const node_t *node, environment_t *env);
187

188
189
#define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
#define set_irn_node(irn, node)   set_irn_link(irn, node)
190

191
192
193
194
195
/* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
#undef tarval_unreachable
#define tarval_unreachable tarval_top


196
197
198
/** The debug module handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

199
200
201
/** The what reason. */
DEBUG_ONLY(static const char *what_reason;)

Michael Beck's avatar
Michael Beck committed
202
/** Next partition number. */
203
DEBUG_ONLY(static unsigned part_nr = 0;)
204

205
/** The tarval returned by Unknown nodes: set to either tarval_bad OR tarval_top. */
Matthias Braun's avatar
Matthias Braun committed
206
static ir_tarval *tarval_UNKNOWN;
207

208
209
210
/* forward */
static node_t *identity(node_t *node);

211
212
213
214
215
216
217
218
219
220
/**
 * Compare two opcode representatives.
 */
static int cmp_irn_opcode(const ir_node *a, const ir_node *b)
{
	if ((get_irn_op(a) != get_irn_op(b)) ||
	    (get_irn_mode(a) != get_irn_mode(b)))
		return 1;

	/* compare if a's in and b's in are of equal length */
yb9976's avatar
yb9976 committed
221
	int arity = get_irn_arity(a);
222
223
224
225
226
227
228
229
230
231
232
233
234
235
	if (arity != get_irn_arity(b))
		return 1;

	if (is_Block(a)) {
		/*
		 * Some ugliness here: Two Blocks having the same
		 * IJmp predecessor would be congruent, which of course is wrong.
		 * We fix it by never letting blocks be congruent
		 * which cannot be detected by combo either.
		 */
		return 1;
	}

	/*
236
	 * here, we already know that the nodes are identical except their
237
238
239
240
241
242
	 * attributes
	 */
	if (a->op->ops.node_cmp_attr)
		return a->op->ops.node_cmp_attr(a, b);

	return 0;
243
}
244

245
246
247
248
#ifdef CHECK_PARTITIONS
/**
 * Check a partition.
 */
249
250
static void check_partition(const partition_t *T)
{
251
252
253
254
	unsigned n = 0;

	list_for_each_entry(node_t, node, &T->Leader, node_list) {
		assert(node->is_follower == 0);
Michael Beck's avatar
Michael Beck committed
255
		assert(node->flagged == 0);
256
257
258
		assert(node->part == T);
		++n;
	}
yb9976's avatar
yb9976 committed
259
	(void)n;
260
261
262
263
	assert(n == T->n_leader);

	list_for_each_entry(node_t, node, &T->Follower, node_list) {
		assert(node->is_follower == 1);
Michael Beck's avatar
Michael Beck committed
264
		assert(node->flagged == 0);
265
266
		assert(node->part == T);
	}
267
}
Michael Beck's avatar
Michael Beck committed
268

yb9976's avatar
yb9976 committed
269
#ifdef DEBUG_libfirm
270
271
272
/**
 * check that all leader nodes in the partition have the same opcode.
 */
273
274
static void check_opcode(const partition_t *Z)
{
275
	const ir_node *repr = NULL;
276
277
278
279

	list_for_each_entry(node_t, node, &Z->Leader, node_list) {
		ir_node *irn = node->node;

280
281
		if (repr == NULL) {
			repr = irn;
282
		} else {
283
			assert(cmp_irn_opcode(repr, irn) == 0);
284
285
		}
	}
286
}
yb9976's avatar
yb9976 committed
287
#endif
288

289
290
static void check_all_partitions(environment_t *env)
{
Michael Beck's avatar
Michael Beck committed
291
#ifdef DEBUG_libfirm
yb9976's avatar
yb9976 committed
292
	for (partition_t *P = env->dbg_list; P != NULL; P = P->dbg_next) {
Michael Beck's avatar
Michael Beck committed
293
		check_partition(P);
294
295
		if (! P->type_is_T_or_C)
			check_opcode(P);
Michael Beck's avatar
Michael Beck committed
296
297
298
299
300
301
		list_for_each_entry(node_t, node, &P->Follower, node_list) {
			node_t *leader = identity(node);

			assert(leader != node && leader->part == node->part);
		}
	}
302
#else
yb9976's avatar
yb9976 committed
303
	(void)env;
Matthias Braun's avatar
Matthias Braun committed
304
#endif
Michael Beck's avatar
Michael Beck committed
305
306
}

Michael Beck's avatar
Michael Beck committed
307
308
309
/**
 * Check list.
 */
310
311
static void do_check_list(const node_t *list, int ofs, const partition_t *Z)
{
Michael Beck's avatar
Michael Beck committed
312

313
#ifndef NDEBUG
Michael Beck's avatar
Michael Beck committed
314
#define NEXT(e)  *((const node_t **)((char *)(e) + (ofs)))
yb9976's avatar
yb9976 committed
315
	for (const node_t *e = list; e != NULL; e = NEXT(e)) {
Michael Beck's avatar
Michael Beck committed
316
317
318
		assert(e->part == Z);
	}
#undef NEXT
319
#else
yb9976's avatar
yb9976 committed
320
321
322
	(void)list;
	(void)ofs;
	(void)Z;
323
#endif
324
}
Michael Beck's avatar
Michael Beck committed
325
326
327
328

/**
 * Check a local list.
 */
329
330
static void check_list(const node_t *list, const partition_t *Z)
{
Michael Beck's avatar
Michael Beck committed
331
	do_check_list(list, offsetof(node_t, next), Z);
332
}
Michael Beck's avatar
Michael Beck committed
333

334
335
#else
#define check_partition(T)
Michael Beck's avatar
Michael Beck committed
336
#define check_list(list, Z)
Michael Beck's avatar
Michael Beck committed
337
#define check_all_partitions(env)
338
339
#endif /* CHECK_PARTITIONS */

340
#ifdef DEBUG_libfirm
341
static inline lattice_elem_t get_partition_type(const partition_t *X);
342

343
344
345
/**
 * Dump partition to output.
 */
346
347
static void dump_partition(const char *msg, const partition_t *part)
{
348
349
	int            first = 1;
	lattice_elem_t type = get_partition_type(part);
350

351
352
	DB((dbg, LEVEL_2, "%s part%u%s (%u, %+F) {\n  ",
		msg, part->nr, part->type_is_T_or_C ? "*" : "",
353
354
		part->n_leader, type));
	list_for_each_entry(node_t, node, &part->Leader, node_list) {
355
356
		DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
		first = 0;
357
	}
358
359
	if (! list_empty(&part->Follower)) {
		DB((dbg, LEVEL_2, "\n---\n  "));
360
		first = 1;
361
		list_for_each_entry(node_t, node, &part->Follower, node_list) {
362
363
364
365
			DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
			first = 0;
		}
	}
Michael Beck's avatar
Michael Beck committed
366
	DB((dbg, LEVEL_2, "\n}\n"));
367
}
Michael Beck's avatar
Michael Beck committed
368

369
370
371
/**
 * Dumps a list.
 */
372
373
static void do_dump_list(const char *msg, const node_t *node, int ofs)
{
374
375
376
377
378
379
380
381
382
383
384
385
386
	const node_t *p;
	int          first = 1;

#define GET_LINK(p, ofs)  *((const node_t **)((char *)(p) + (ofs)))

	DB((dbg, LEVEL_3, "%s = {\n  ", msg));
	for (p = node; p != NULL; p = GET_LINK(p, ofs)) {
		DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->node));
		first = 0;
	}
	DB((dbg, LEVEL_3, "\n}\n"));

#undef GET_LINK
387
}
388
389
390
391

/**
 * Dumps a race list.
 */
392
393
static void dump_race_list(const char *msg, const node_t *list)
{
394
	do_dump_list(msg, list, offsetof(node_t, race_next));
395
}
396
397
398
399

/**
 * Dumps a local list.
 */
400
401
static void dump_list(const char *msg, const node_t *list)
{
402
	do_dump_list(msg, list, offsetof(node_t, next));
403
}
404

Michael Beck's avatar
Michael Beck committed
405
406
407
/**
 * Dump all partitions.
 */
408
409
static void dump_all_partitions(const environment_t *env)
{
Michael Beck's avatar
Michael Beck committed
410
	DB((dbg, LEVEL_2, "All partitions\n===============\n"));
yb9976's avatar
yb9976 committed
411
	for (const partition_t *P = env->dbg_list; P != NULL; P = P->dbg_next)
Michael Beck's avatar
Michael Beck committed
412
		dump_partition("", P);
413
}
Michael Beck's avatar
Michael Beck committed
414

415
416
417
/**
 * Sump a split list.
 */
418
419
static void dump_split_list(const partition_t *list)
{
yb9976's avatar
yb9976 committed
420
	char split = ' ';
421
422

	DB((dbg, LEVEL_2, "Split by %s produced = {\n", what_reason));
yb9976's avatar
yb9976 committed
423
	for (const partition_t *p = list; p != NULL; p = p->split_next) {
yb9976's avatar
yb9976 committed
424
425
426
		DB((dbg, LEVEL_2, "%c part%u", split, p->nr));
		split = ',';
	}
427
	DB((dbg, LEVEL_2, "\n}\n"));
428
}
429

Michael Beck's avatar
Michael Beck committed
430
431
432
/**
 * Dump partition and type for a node.
 */
433
static int dump_partition_hook(FILE *F, const ir_node *n, const ir_node *local)
434
{
yb9976's avatar
yb9976 committed
435
436
	const ir_node *irn  = local != NULL ? local : n;
	const node_t  *node = get_irn_node(irn);
Michael Beck's avatar
Michael Beck committed
437
438
439

	ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
	return 1;
440
}
Michael Beck's avatar
Michael Beck committed
441

442
#else
yb9976's avatar
yb9976 committed
443
444
445
446
447
#define dump_partition(msg, part) (void)(msg), (void)(part)
#define dump_race_list(msg, list) (void)(msg), (void)(list)
#define dump_list(msg, list) (void)(msg), (void)(list)
#define dump_all_partitions(env) (void)(env)
#define dump_split_list(list) (void)(list)
448
449
#endif

450
451
452
453
#if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
/**
 * Verify that a type transition is monotone
 */
454
455
static void verify_type(const lattice_elem_t old_type, node_t *node)
{
456
	if (old_type.tv == node->type.tv) {
457
458
459
460
461
462
463
		/* no change */
		return;
	}
	if (old_type.tv == tarval_top) {
		/* from Top down-to is always allowed */
		return;
	}
464
	if (node->type.tv == tarval_bottom || node->type.tv == tarval_reachable) {
465
466
467
		/* bottom reached */
		return;
	}
468
	panic("wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node);
469
}
470

471
#else
yb9976's avatar
yb9976 committed
472
#define verify_type(old_type, node) (void)(old_type), (void)node
473
474
#endif

475
/**
476
 * Compare two pointer values of a listmap.
477
 */
478
479
static int listmap_cmp_ptr(const void *elt, const void *key, size_t size)
{
480
481
	const listmap_entry_t *e1 = (listmap_entry_t*)elt;
	const listmap_entry_t *e2 = (listmap_entry_t*)key;
482

yb9976's avatar
yb9976 committed
483
	(void)size;
484
	return e1->id != e2->id;
485
}
486
487

/**
488
489
490
 * Initializes a listmap.
 *
 * @param map  the listmap
491
 */
492
493
static void listmap_init(listmap_t *map)
{
494
	map->map    = new_set(listmap_cmp_ptr, 16);
495
	map->values = NULL;
496
}
497
498

/**
499
500
501
 * Terminates a listmap.
 *
 * @param map  the listmap
502
 */
503
504
static void listmap_term(listmap_t *map)
{
505
	del_set(map->map);
506
}
507
508
509

/**
 * Return the associated listmap entry for a given id.
510
511
512
513
 *
 * @param map  the listmap
 * @param id   the id to search for
 *
Michael Beck's avatar
Michael Beck committed
514
 * @return the associated listmap entry for the given id
515
 */
516
517
static listmap_entry_t *listmap_find(listmap_t *map, void *id)
{
yb9976's avatar
yb9976 committed
518
519
	listmap_entry_t  key   = { .id = id, .list = NULL, .next = NULL };
	listmap_entry_t *entry = set_insert(listmap_entry_t, map->map, &key, sizeof(key), hash_ptr(id));
520
521
522
523
524
525
526

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

/**
530
531
532
533
534
 * 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
535
 */
536
537
static unsigned opcode_hash(const opcode_key_t *entry)
{
538
539
	/* we cannot use the ir ops hash function here, because it hashes the
	 * predecessors. */
yb9976's avatar
yb9976 committed
540
541
542
543
	const ir_node *n    = entry->irn;
	ir_opcode      code = (ir_opcode)get_irn_opcode(n);
	ir_mode       *mode = get_irn_mode(n);
	unsigned       hash = (unsigned)(PTR_TO_INT(mode) *9 + code) + get_irn_arity(n);
544
545

	if (code == iro_Const)
546
		hash ^= (unsigned)hash_ptr(get_Const_tarval(n));
547
548
549
	else if (code == iro_Proj)
		hash += (unsigned)get_Proj_proj(n);
	return hash;
550
}
551
552
553
554

/**
 * Compare two entries in the opcode map.
 */
555
556
static int cmp_opcode(const void *elt, const void *key, size_t size)
{
557
558
	const opcode_key_t *o1 = (opcode_key_t*)elt;
	const opcode_key_t *o2 = (opcode_key_t*)key;
559

yb9976's avatar
yb9976 committed
560
	(void)size;
561
562

	return cmp_irn_opcode(o1->irn, o2->irn);
563
}
564

565
566
567
/**
 * Compare two Def-Use edges for input position.
 */
568
569
static int cmp_def_use_edge(const void *a, const void *b)
{
570
571
	const ir_def_use_edge *ea = (const ir_def_use_edge*)a;
	const ir_def_use_edge *eb = (const ir_def_use_edge*)b;
572
573
574

	/* no overrun, because range is [-1, MAXINT] */
	return ea->pos - eb->pos;
575
}
576
577
578
579

/**
 * We need the Def-Use edges sorted.
 */
580
581
static void sort_irn_outs(node_t *node)
{
yb9976's avatar
yb9976 committed
582
583
	ir_node  *irn    = node->node;
	unsigned  n_outs = get_irn_n_outs(irn);
Matthias Braun's avatar
Matthias Braun committed
584
585
	qsort(irn->o.out->edges, n_outs, sizeof(irn->o.out->edges[0]),
		  cmp_def_use_edge);
Matthias Braun's avatar
Matthias Braun committed
586
	node->max_user_input = n_outs > 0 ? irn->o.out->edges[n_outs-1].pos : -1;
587
}
588

589
590
591
592
593
594
595
/**
 * Return the type of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
596
597
static inline lattice_elem_t get_node_type(const ir_node *irn)
{
598
	return get_irn_node(irn)->type;
599
}
600
601
602
603
604
605
606
607

/**
 * Return the tarval of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
Matthias Braun's avatar
Matthias Braun committed
608
static inline ir_tarval *get_node_tarval(const ir_node *irn)
609
{
610
611
	lattice_elem_t type = get_node_type(irn);

612
	if (is_tarval(type.tv))
613
614
		return type.tv;
	return tarval_bottom;
615
}
616

617
618
619
/**
 * Add a partition to the worklist.
 */
620
621
static inline void add_to_worklist(partition_t *X, environment_t *env)
{
622
	assert(X->on_worklist == 0);
623
	DB((dbg, LEVEL_2, "Adding part%d to worklist\n", X->nr));
624
625
626
	X->wl_next     = env->worklist;
	X->on_worklist = 1;
	env->worklist  = X;
627
}
628

629
630
/**
 * Create a new empty partition.
631
632
633
634
 *
 * @param env   the environment
 *
 * @return a newly allocated partition
635
 */
636
637
static inline partition_t *new_partition(environment_t *env)
{
638
	partition_t *part = OALLOC(&env->obst, partition_t);
639

640
641
	INIT_LIST_HEAD(&part->Leader);
	INIT_LIST_HEAD(&part->Follower);
Michael Beck's avatar
BugFix:    
Michael Beck committed
642
	INIT_LIST_HEAD(&part->cprop);
643
	INIT_LIST_HEAD(&part->cprop_X);
644
645
646
	part->wl_next         = NULL;
	part->touched_next    = NULL;
	part->cprop_next      = NULL;
Michael Beck's avatar
Michael Beck committed
647
	part->split_next      = NULL;
648
	part->touched         = NULL;
649
	part->n_leader        = 0;
650
651
652
653
654
	part->n_touched       = 0;
	part->max_user_inputs = 0;
	part->on_worklist     = 0;
	part->on_touched      = 0;
	part->on_cprop        = 0;
655
	part->type_is_T_or_C  = 0;
Michael Beck's avatar
Michael Beck committed
656
#ifdef DEBUG_libfirm
657
658
659
	part->dbg_next        = env->dbg_list;
	env->dbg_list         = part;
	part->nr              = part_nr++;
Michael Beck's avatar
Michael Beck committed
660
#endif
661
662

	return part;
663
}
664
665

/**
666
 * Get the first node from a partition.
667
 */
668
669
static inline node_t *get_first_node(const partition_t *X)
{
670
	return list_entry(X->Leader.next, node_t, node_list);
671
}
672
673
674
675
676
677
678
679
680

/**
 * Return the type of a partition (assuming partition is non-empty and
 * all elements have the same type).
 *
 * @param X  a partition
 *
 * @return the type of the first element of the partition
 */
681
682
static inline lattice_elem_t get_partition_type(const partition_t *X)
{
683
	const node_t *first = get_first_node(X);
684
	return first->type;
685
}
686
687
688
689

/**
 * Creates a partition node for the given IR-node and place it
 * into the given partition.
690
691
692
693
 *
 * @param irn   an IR-node
 * @param part  a partition to place the node in
 * @param env   the environment
694
695
 *
 * @return the created node
696
 */
697
698
static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env)
{
699
	/* create a partition node and place it in the partition */
700
	node_t *node = OALLOC(&env->obst, node_t);
701
702

	INIT_LIST_HEAD(&node->node_list);
Michael Beck's avatar
BugFix:    
Michael Beck committed
703
	INIT_LIST_HEAD(&node->cprop_list);
704
705
706
	node->node           = irn;
	node->part           = part;
	node->next           = NULL;
707
	node->race_next      = NULL;
708
	node->type.tv        = tarval_top;
709
710
	node->max_user_input = 0;
	node->next_edge      = 0;
711
	node->n_followers    = 0;
712
713
	node->on_touched     = 0;
	node->on_cprop       = 0;
714
	node->on_fallen      = 0;
715
	node->is_follower    = 0;
Michael Beck's avatar
Michael Beck committed
716
	node->flagged        = 0;
717
718
	set_irn_node(irn, node);

719
720
	list_add_tail(&node->node_list, &part->Leader);
	++part->n_leader;
721

722
	return node;
723
}
724
725

/**
726
 * Pre-Walker, initialize all Nodes' type to U or top and place
727
 * all nodes into the TOP partition.
728
 */
729
730
static void create_initial_partitions(ir_node *irn, void *ctx)
{
731
	environment_t *env  = (environment_t*)ctx;
732
	partition_t   *part = env->initial;
yb9976's avatar
yb9976 committed
733
	node_t        *node = create_partition_node(irn, part, env);
734
	sort_irn_outs(node);
735
736
	if (node->max_user_input > part->max_user_inputs)
		part->max_user_inputs = node->max_user_input;
Michael Beck's avatar
BugFix:    
Michael Beck committed
737

738
739
740
	if (is_Block(irn)) {
		set_Block_phis(irn, NULL);
	}
741
}
742
743
744
745

/**
 * Post-Walker, collect  all Block-Phi lists, set Cond.
 */
746
747
static void init_block_phis(ir_node *irn, void *ctx)
{
yb9976's avatar
yb9976 committed
748
	(void)ctx;
749

Michael Beck's avatar
BugFix:    
Michael Beck committed
750
	if (is_Phi(irn)) {
751
752
		ir_node *block = get_nodes_block(irn);
		add_Block_phi(block, irn);
Michael Beck's avatar
BugFix:    
Michael Beck committed
753
	}
754
}
755
756

/**
757
758
 * Add a node to the entry.partition.touched set and
 * node->partition to the touched set if not already there.
759
 *
760
761
 * @param y    a node
 * @param env  the environment
762
 */
763
764
static inline void add_to_touched(node_t *y, environment_t *env)
{
765
766
767
	if (y->on_touched == 0) {
		partition_t *part = y->part;

768
769
770
		y->next       = part->touched;
		part->touched = y;
		y->on_touched = 1;
771
		++part->n_touched;
772
773
774
775
776
777

		if (part->on_touched == 0) {
			part->touched_next = env->touched;
			env->touched       = part;
			part->on_touched   = 1;
		}
Michael Beck's avatar
Michael Beck committed
778
779

		check_list(part->touched, part);
780
	}
781
}
782
783
784
785
786
787
788

/**
 * Place a node on the cprop list.
 *
 * @param y    the node
 * @param env  the environment
 */
789
790
static void add_to_cprop(node_t *y, environment_t *env)
{
791
792
	/* Add y to y.partition.cprop. */
	if (y->on_cprop == 0) {
yb9976's avatar
yb9976 committed
793
794
795
		partition_t *Y       = y->part;
		ir_node     *irn     = y->node;
		ir_node     *skipped = skip_Proj(irn);
796

797
		/* place Conds and all its Projs on the cprop_X list */
Matthias Braun's avatar
Matthias Braun committed
798
		if (is_Cond(skipped) || is_Switch(skipped))
799
800
801
			list_add_tail(&y->cprop_list, &Y->cprop_X);
		else
			list_add_tail(&y->cprop_list, &Y->cprop);
yb9976's avatar
yb9976 committed
802
		y->on_cprop = 1;
803
804
805
806
807
808
809
810
811
812

		DB((dbg, LEVEL_3, "Add %+F to part%u.cprop\n", y->node, Y->nr));

		/* place its partition on the cprop list */
		if (Y->on_cprop == 0) {
			Y->cprop_next = env->cprop;
			env->cprop    = Y;
			Y->on_cprop   = 1;
		}
	}
yb9976's avatar
yb9976 committed
813
	ir_node *irn = y->node;
814
	if (get_irn_mode(irn) == mode_T) {
815
		/* mode_T nodes always produce tarval_bottom, so we must explicitly
816
		 * add its Projs to get constant evaluation to work */
Matthias Braun's avatar
Matthias Braun committed
817
		for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) {
818
			node_t *proj = get_irn_node(get_irn_out(irn, i));
819
820
821

			add_to_cprop(proj, env);
		}
822
	} else if (is_Block(irn)) {
823
824
825
		/* Due to the way we handle Phi's, we must place all Phis of a block on the list
		 * if someone placed the block. The Block is only placed if the reachability
		 * changes, and this must be re-evaluated in compute_Phi(). */
yb9976's avatar
yb9976 committed
826
		for (ir_node *phi = get_Block_phis(irn); phi != NULL; phi = get_Phi_next(phi)) {
827
828
829
830
			node_t *p = get_irn_node(phi);
			add_to_cprop(p, env);
		}
	}
831
}
832
833

/**
834
835
836
837
838
839
 * Update the worklist: If Z is on worklist then add Z' to worklist.
 * Else add the smaller of Z and Z' to worklist.
 *
 * @param Z        the Z partition
 * @param Z_prime  the Z' partition, a previous part of Z
 * @param env      the environment
840
 */
841
842
static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env)
{
843
	if (Z->on_worklist || Z_prime->n_leader < Z->n_leader) {
844
		add_to_worklist(Z_prime, env);
845
	} else {
846
		add_to_worklist(Z, env);
847
	}
848
}
849

850
851
852
853
854
/**
 * Make all inputs to x no longer be F.def_use edges.
 *
 * @param x  the node
 */
855
856
static void move_edges_to_leader(node_t *x)
{
Matthias Braun's avatar
Matthias Braun committed
857
858
	ir_node *irn = x->node;
	for (int i = get_irn_arity(irn) - 1; i >= 0; --i) {
859
		node_t  *pred = get_irn_node(get_irn_n(irn, i));
Matthias Braun's avatar
Matthias Braun committed
860
861
862
863
864
		ir_node *p    = pred->node;
		unsigned n    = get_irn_n_outs(p);
		for (unsigned j = 0; j < pred->n_followers; ++j) {
			ir_def_use_edge edge = p->o.out->edges[j];
			if (edge.pos == i && edge.use == irn) {
865
866
867
				/* found a follower edge to x, move it to the Leader */
				/* remove this edge from the Follower set */
				--pred->n_followers;
Matthias Braun's avatar
Matthias Braun committed
868
				p->o.out->edges[j] = p->o.out->edges[pred->n_followers];
869
870

				/* sort it into the leader set */
Matthias Braun's avatar
Matthias Braun committed
871
872
873
				unsigned k;
				for (k = pred->n_followers+1; k < n; ++k) {
					if (p->o.out->edges[k].pos >= edge.pos)
874
						break;
Matthias Braun's avatar
Matthias Braun committed
875
					p->o.out->edges[k-1] = p->o.out->edges[k];
876
877
				}
				/* place the new edge here */
Matthias Braun's avatar
Matthias Braun committed
878
				p->o.out->edges[k-1] = edge;
879
880
881
882
883
884

				/* edge found and moved */
				break;
			}
		}
	}
885
}
886

887
/**
888
 * Split a partition that has NO followers by a local list.
889
 *
890
 * @param Z    partition to split
891
892
893
894
 * @param g    a (non-empty) node list
 * @param env  the environment
 *
 * @return  a new partition containing the nodes of g
895
 */
896
897
static partition_t *split_no_followers(partition_t *Z, node_t *g, environment_t *env)
{
yb9976's avatar
yb9976 committed
898
	unsigned n = 0;
899
900

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

903
904
	assert(g != NULL);

905
	/* Remove g from Z. */
yb9976's avatar
yb9976 committed
906
	for (node_t *node = g; node != NULL; node = node->next) {
907