combo.c 95.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * 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   Cliff Click's Combined Analysis/Optimization
 * @author  Michael Beck
 * @version $Id$
25
 *
26
 * This is a slightly enhanced version of Cliff Clicks combo algorithm
Michael Beck's avatar
Michael Beck committed
27
 * - support for commutative nodes is added, Add(a,b) and Add(b,a) ARE congruent
28
29
 * - 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
30
 * - supports Confirm nodes (handle them like Copies but do NOT remove them)
Michael Beck's avatar
Michael Beck committed
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 * - let Cmp nodes calculate Top like all othe data nodes: this would let
 *   Mux nodes to calculate Unknown instead of taking the true result
 * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reavaluated
 *   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.
55
56
 * - support for global congruences is implemented but not tested yet
 *
Michael Beck's avatar
Michael Beck committed
57
 * Note further that we use the terminology from Click's work here, which is different
58
 * in some cases from Firm terminology.  Especially, Click's type is a
59
 * Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
60
 */
Matthias Braun's avatar
Matthias Braun committed
61
#include "config.h"
62
63

#include <assert.h>
64
65
66

#include "iroptimize.h"
#include "irflag.h"
67
#include "ircons.h"
68
#include "list.h"
69
70
#include "set.h"
#include "pmap.h"
71
72
73
#include "obstack.h"
#include "irgraph_t.h"
#include "irnode_t.h"
74
#include "iropt_t.h"
75
76
77
78
#include "irgwalk.h"
#include "irop.h"
#include "irouts.h"
#include "irgmod.h"
79
#include "iropt_dbg.h"
80
#include "debug.h"
81
#include "array_t.h"
82
#include "error.h"
83
#include "irnodeset.h"
84

85
86
#include "tv_t.h"

87
88
89
#include "irprintf.h"
#include "irdump.h"

90
/* define this to check that all type translations are monotone */
91
#define VERIFY_MONOTONE
92

93
94
95
/* define this to check the consistency of partitions */
#define CHECK_PARTITIONS

96
typedef struct node_t            node_t;
97
typedef struct partition_t       partition_t;
98
99
100
101
102
103
104
105
106
107
108
109
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 {
	ir_opcode   code;   /**< The Firm opcode. */
	ir_mode     *mode;  /**< The mode of all nodes in the partition. */
110
	int         arity;  /**< The arity of this opcode (needed for Phi etc. */
111
112
113
	union {
		long      proj;   /**< For Proj nodes, its proj number */
		ir_entity *ent;   /**< For Sel Nodes, its entity */
114
		int       intVal; /**< For Conv/Div Nodes: strict/remainderless */
115
		unsigned  uintVal;/**< for Builtin: the kind */
116
117
		ir_node   *block; /**< for Block: itself */
		void      *ptr;   /**< generic pointer for hash/cmp */
118
	} u;
119
};
120

121
122
123
124
/**
 * An entry in the list_map.
 */
struct listmap_entry_t {
Michael Beck's avatar
Michael Beck committed
125
	void            *id;    /**< The id. */
126
127
128
129
130
131
132
133
134
135
	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;

136
137
138
139
140
141
142
143
/**
 * A lattice element. Because we handle constants and symbolic constants different, we
 * have to use this union.
 */
typedef union {
	tarval          *tv;
	symconst_symbol sym;
} lattice_elem_t;
144
145
146
147
148

/**
 * A node.
 */
struct node_t {
149
	ir_node         *node;          /**< The IR-node itself. */
150
	list_head       node_list;      /**< Double-linked list of leader/follower entries. */
Michael Beck's avatar
BugFix:    
Michael Beck committed
151
	list_head       cprop_list;     /**< Double-linked partition.cprop list. */
152
153
	partition_t     *part;          /**< points to the partition this node belongs to */
	node_t          *next;          /**< Next node on local list (partition.touched, fallen). */
154
	node_t          *race_next;     /**< Next node on race list. */
155
156
157
	lattice_elem_t  type;           /**< The associated lattice element "type". */
	int             max_user_input; /**< Maximum input number of Def-Use edges. */
	int             next_edge;      /**< Index of the next Def-Use edge to use. */
158
	int             n_followers;    /**< Number of Follower in the outs set. */
159
160
	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. */
161
	unsigned        on_fallen:1;    /**< Set, if this node is on the fallen list. */
162
	unsigned        is_follower:1;  /**< Set, if this node is a follower. */
Michael Beck's avatar
Michael Beck committed
163
	unsigned        flagged:2;      /**< 2 Bits, set if this node was visited by race 1 or 2. */
164
165
166
167
168
169
};

/**
 * A partition containing congruent nodes.
 */
struct partition_t {
170
171
	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
172
	list_head         cprop;           /**< The head of partition.cprop list. */
173
	list_head         cprop_X;         /**< The head of partition.cprop (Cond nodes and its Projs) list. */
174
175
176
	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
177
	partition_t       *split_next;     /**< Points to the next partition in the list that must be split by split_by(). */
178
	node_t            *touched;        /**< The partition.touched set of this partition. */
179
	unsigned          n_leader;        /**< Number of entries in this partition.Leader. */
180
181
182
183
184
	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. */
185
	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
186
#ifdef DEBUG_libfirm
187
188
	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
189
#endif
190
191
192
};

typedef struct environment_t {
193
194
195
196
	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. */
197
	partition_t     *initial;       /**< The initial partition. */
198
199
	set             *opcode2id_map; /**< The opcodeMode->id map. */
	pmap            *type2id_map;   /**< The type->id map. */
200
	ir_node         **kept_memory;  /**< Array of memory nodes that must be kept. */
201
202
	int             end_idx;        /**< -1 for local and 0 for global congruences. */
	int             lambda_input;   /**< Captured argument for lambda_partition(). */
203
204
	unsigned        modified:1;     /**< Set, if the graph was modified. */
	unsigned        unopt_cf:1;     /**< If set, control flow is not optimized due to Unknown. */
205
206
207
	/* 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. */
208
209
210
#ifdef DEBUG_libfirm
	partition_t     *dbg_list;      /**< List of all partitions. */
#endif
211
212
} environment_t;

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

216
217
#define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
#define set_irn_node(irn, node)   set_irn_link(irn, node)
218

219
220
221
222
223
/* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
#undef tarval_unreachable
#define tarval_unreachable tarval_top


224
225
226
/** The debug module handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

227
228
229
/** The what reason. */
DEBUG_ONLY(static const char *what_reason;)

Michael Beck's avatar
Michael Beck committed
230
231
/** Next partition number. */
DEBUG_ONLY(static unsigned part_nr = 0);
232

233
234
/** The tarval returned by Unknown nodes: set to either tarval_bad OR tarval_top. */
static tarval *tarval_UNKNOWN;
235

236
237
238
239
240
241
242
243
244
245
246
247
248
/* forward */
static node_t *identity(node_t *node);

#ifdef CHECK_PARTITIONS
/**
 * Check a partition.
 */
static void check_partition(const partition_t *T) {
	node_t   *node;
	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
249
		assert(node->flagged == 0);
250
251
252
253
254
255
256
		assert(node->part == T);
		++n;
	}
	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
257
		assert(node->flagged == 0);
258
259
260
		assert(node->part == T);
	}
}  /* check_partition */
Michael Beck's avatar
Michael Beck committed
261

262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
/**
 * check that all leader nodes in the partition have the same opcode.
 */
static void check_opcode(const partition_t *Z) {
	node_t       *node;
	opcode_key_t key;
	int          first = 1;

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

		if (first) {
			key.code   = get_irn_opcode(irn);
			key.mode   = get_irn_mode(irn);
			key.arity  = get_irn_arity(irn);
			key.u.proj = 0;
			key.u.ent  = NULL;

			switch (get_irn_opcode(irn)) {
			case iro_Proj:
				key.u.proj = get_Proj_proj(irn);
				break;
			case iro_Sel:
				key.u.ent = get_Sel_entity(irn);
				break;
287
288
289
290
291
292
			case iro_Conv:
				key.u.intVal = get_Conv_strict(irn);
				break;
			case iro_Div:
				key.u.intVal = is_Div_remainderless(irn);
				break;
293
294
295
296
297
298
			case iro_Block:
				key.u.block = irn;
				break;
			case iro_Load:
				key.mode = get_Load_mode(irn);
				break;
299
			case iro_Builtin:
Michael Beck's avatar
Michael Beck committed
300
				key.u.intVal = get_Builtin_kind(irn);
301
				break;
302
303
304
305
306
			default:
				break;
			}
			first = 0;
		} else {
Michael Beck's avatar
Michael Beck committed
307
			assert((unsigned)key.code  == get_irn_opcode(irn));
Michael Beck's avatar
Michael Beck committed
308
309
			assert(key.mode  == get_irn_mode(irn));
			assert(key.arity == get_irn_arity(irn));
310
311
312
313
314
315
316
317

			switch (get_irn_opcode(irn)) {
			case iro_Proj:
				assert(key.u.proj == get_Proj_proj(irn));
				break;
			case iro_Sel:
				assert(key.u.ent == get_Sel_entity(irn));
				break;
318
319
320
321
322
323
			case iro_Conv:
				assert(key.u.intVal == get_Conv_strict(irn));
				break;
			case iro_Div:
				assert(key.u.intVal == is_Div_remainderless(irn));
				break;
324
325
326
327
328
329
			case iro_Block:
				assert(key.u.block == irn);
				break;
			case iro_Load:
				assert(key.mode == get_Load_mode(irn));
				break;
330
			case iro_Builtin:
Matthias Braun's avatar
Matthias Braun committed
331
				assert(key.u.intVal == (int) get_Builtin_kind(irn));
332
				break;
333
334
335
336
337
338
339
			default:
				break;
			}
		}
	}
}  /* check_opcode */

Michael Beck's avatar
Michael Beck committed
340
static void check_all_partitions(environment_t *env) {
Michael Beck's avatar
Michael Beck committed
341
#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
342
343
344
345
346
	partition_t *P;
	node_t      *node;

	for (P = env->dbg_list; P != NULL; P = P->dbg_next) {
		check_partition(P);
347
348
		if (! P->type_is_T_or_C)
			check_opcode(P);
Michael Beck's avatar
Michael Beck committed
349
350
351
352
353
354
		list_for_each_entry(node_t, node, &P->Follower, node_list) {
			node_t *leader = identity(node);

			assert(leader != node && leader->part == node->part);
		}
	}
Matthias Braun's avatar
Matthias Braun committed
355
#endif
Michael Beck's avatar
Michael Beck committed
356
357
}

Michael Beck's avatar
Michael Beck committed
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
/**
 * Check list.
 */
static void do_check_list(const node_t *list, int ofs, const partition_t *Z) {
	const node_t *e;

#define NEXT(e)  *((const node_t **)((char *)(e) + (ofs)))
	for (e = list; e != NULL; e = NEXT(e)) {
		assert(e->part == Z);
	}
#undef NEXT
}  /* ido_check_list */

/**
 * Check a local list.
 */
static void check_list(const node_t *list, const partition_t *Z) {
	do_check_list(list, offsetof(node_t, next), Z);
}  /* check_list */

378
379
#else
#define check_partition(T)
Michael Beck's avatar
Michael Beck committed
380
#define check_list(list, Z)
Michael Beck's avatar
Michael Beck committed
381
#define check_all_partitions(env)
382
383
#endif /* CHECK_PARTITIONS */

384
#ifdef DEBUG_libfirm
385
static inline lattice_elem_t get_partition_type(const partition_t *X);
386

387
388
389
/**
 * Dump partition to output.
 */
390
391
392
393
static void dump_partition(const char *msg, const partition_t *part) {
	const node_t   *node;
	int            first = 1;
	lattice_elem_t type = get_partition_type(part);
394

395
396
	DB((dbg, LEVEL_2, "%s part%u%s (%u, %+F) {\n  ",
		msg, part->nr, part->type_is_T_or_C ? "*" : "",
397
398
		part->n_leader, type));
	list_for_each_entry(node_t, node, &part->Leader, node_list) {
399
400
		DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
		first = 0;
401
	}
402
403
	if (! list_empty(&part->Follower)) {
		DB((dbg, LEVEL_2, "\n---\n  "));
404
		first = 1;
405
		list_for_each_entry(node_t, node, &part->Follower, node_list) {
406
407
408
409
			DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
			first = 0;
		}
	}
Michael Beck's avatar
Michael Beck committed
410
	DB((dbg, LEVEL_2, "\n}\n"));
411
}  /* dump_partition */
Michael Beck's avatar
Michael Beck committed
412

413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
/**
 * Dumps a list.
 */
static void do_dump_list(const char *msg, const node_t *node, int ofs) {
	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
Michael Beck's avatar
Michael Beck committed
430
}  /* do_dump_list */
431
432
433
434
435
436

/**
 * Dumps a race list.
 */
static void dump_race_list(const char *msg, const node_t *list) {
	do_dump_list(msg, list, offsetof(node_t, race_next));
Michael Beck's avatar
Michael Beck committed
437
}  /* dump_race_list */
438
439
440
441
442
443

/**
 * Dumps a local list.
 */
static void dump_list(const char *msg, const node_t *list) {
	do_dump_list(msg, list, offsetof(node_t, next));
Michael Beck's avatar
Michael Beck committed
444
}  /* dump_list */
445

Michael Beck's avatar
Michael Beck committed
446
447
448
/**
 * Dump all partitions.
 */
449
450
static void dump_all_partitions(const environment_t *env) {
	const partition_t *P;
Michael Beck's avatar
Michael Beck committed
451
452
453
454

	DB((dbg, LEVEL_2, "All partitions\n===============\n"));
	for (P = env->dbg_list; P != NULL; P = P->dbg_next)
		dump_partition("", P);
Michael Beck's avatar
Michael Beck committed
455
}  /* dump_all_partitions */
Michael Beck's avatar
Michael Beck committed
456

457
458
459
460
461
462
463
464
465
466
/**
 * Sump a split list.
 */
static void dump_split_list(const partition_t *list) {
	const partition_t *p;

	DB((dbg, LEVEL_2, "Split by %s produced = {\n", what_reason));
	for (p = list; p != NULL; p = p->split_next)
		DB((dbg, LEVEL_2, "part%u, ", p->nr));
	DB((dbg, LEVEL_2, "\n}\n"));
Michael Beck's avatar
Michael Beck committed
467
}  /* dump_split_list */
468

Michael Beck's avatar
Michael Beck committed
469
470
471
472
473
474
475
476
477
478
479
/**
 * Dump partition and type for a node.
 */
static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
	ir_node *irn = local != NULL ? local : n;
	node_t *node = get_irn_node(irn);

	ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
	return 1;
}  /* dump_partition_hook */

480
#else
481
#define dump_partition(msg, part)
482
483
#define dump_race_list(msg, list)
#define dump_list(msg, list)
Michael Beck's avatar
Michael Beck committed
484
#define dump_all_partitions(env)
485
#define dump_split_list(list)
486
487
#endif

488
489
490
491
#if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
/**
 * Verify that a type transition is monotone
 */
492
static void verify_type(const lattice_elem_t old_type, node_t *node) {
493
	if (old_type.tv == node->type.tv) {
494
495
496
497
498
499
500
		/* no change */
		return;
	}
	if (old_type.tv == tarval_top) {
		/* from Top down-to is always allowed */
		return;
	}
501
	if (node->type.tv == tarval_bottom || node->type.tv == tarval_reachable) {
502
503
504
		/* bottom reached */
		return;
	}
505
	panic("combo: wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node);
Michael Beck's avatar
Michael Beck committed
506
}  /* verify_type */
507

508
#else
509
#define verify_type(old_type, node)
510
511
#endif

512
/**
513
 * Compare two pointer values of a listmap.
514
 */
515
static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
516
517
518
	const listmap_entry_t *e1 = elt;
	const listmap_entry_t *e2 = key;

Michael Beck's avatar
Michael Beck committed
519
	(void) size;
520
	return e1->id != e2->id;
521
}  /* listmap_cmp_ptr */
522
523

/**
524
525
526
 * Initializes a listmap.
 *
 * @param map  the listmap
527
 */
528
529
static void listmap_init(listmap_t *map) {
	map->map    = new_set(listmap_cmp_ptr, 16);
530
	map->values = NULL;
531
}  /* listmap_init */
532
533

/**
534
535
536
 * Terminates a listmap.
 *
 * @param map  the listmap
537
 */
538
static void listmap_term(listmap_t *map) {
539
	del_set(map->map);
540
}  /* listmap_term */
541
542
543

/**
 * Return the associated listmap entry for a given id.
544
545
546
547
 *
 * @param map  the listmap
 * @param id   the id to search for
 *
Michael Beck's avatar
Michael Beck committed
548
 * @return the associated listmap entry for the given id
549
 */
Michael Beck's avatar
Michael Beck committed
550
static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
551
552
553
554
555
	listmap_entry_t key, *entry;

	key.id   = id;
	key.list = NULL;
	key.next = NULL;
Michael Beck's avatar
Michael Beck committed
556
	entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
557
558
559
560
561
562
563

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

/**
567
568
569
570
571
 * 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
572
573
 */
static unsigned opcode_hash(const opcode_key_t *entry) {
574
	return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ptr) + entry->arity;
575
}  /* opcode_hash */
576
577
578
579
580
581
582
583

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

Michael Beck's avatar
Michael Beck committed
584
	(void) size;
585
	return o1->code != o2->code || o1->mode != o2->mode ||
586
	       o1->arity != o2->arity ||
587
	       o1->u.proj != o2->u.proj ||
588
	       o1->u.intVal != o2->u.intVal || /* this already checks uIntVal */
589
	       o1->u.ptr != o2->u.ptr;
590
}  /* cmp_opcode */
591

592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
/**
 * Compare two Def-Use edges for input position.
 */
static int cmp_def_use_edge(const void *a, const void *b) {
	const ir_def_use_edge *ea = a;
	const ir_def_use_edge *eb = b;

	/* no overrun, because range is [-1, MAXINT] */
	return ea->pos - eb->pos;
}  /* cmp_def_use_edge */

/**
 * We need the Def-Use edges sorted.
 */
static void sort_irn_outs(node_t *node) {
	ir_node *irn = node->node;
	int n_outs = get_irn_n_outs(irn);

	if (n_outs > 1) {
		qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge);
	}
Michael Beck's avatar
Michael Beck committed
613
	node->max_user_input = irn->out[n_outs].pos;
614
615
}  /* sort_irn_outs */

616
617
618
619
620
621
622
/**
 * Return the type of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
623
static inline lattice_elem_t get_node_type(const ir_node *irn) {
624
	return get_irn_node(irn)->type;
625
626
627
628
629
630
631
632
633
}  /* get_node_type */

/**
 * Return the tarval of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
634
static inline tarval *get_node_tarval(const ir_node *irn) {
635
636
	lattice_elem_t type = get_node_type(irn);

637
	if (is_tarval(type.tv))
638
639
640
641
		return type.tv;
	return tarval_bottom;
}  /* get_node_type */

642
643
644
/**
 * Add a partition to the worklist.
 */
645
static inline void add_to_worklist(partition_t *X, environment_t *env) {
646
	assert(X->on_worklist == 0);
647
	DB((dbg, LEVEL_2, "Adding part%d to worklist\n", X->nr));
648
649
650
	X->wl_next     = env->worklist;
	X->on_worklist = 1;
	env->worklist  = X;
651
}  /* add_to_worklist */
652

653
654
/**
 * Create a new empty partition.
655
656
657
658
 *
 * @param env   the environment
 *
 * @return a newly allocated partition
659
 */
660
static inline partition_t *new_partition(environment_t *env) {
661
662
	partition_t *part = obstack_alloc(&env->obst, sizeof(*part));

663
664
	INIT_LIST_HEAD(&part->Leader);
	INIT_LIST_HEAD(&part->Follower);
Michael Beck's avatar
BugFix:    
Michael Beck committed
665
	INIT_LIST_HEAD(&part->cprop);
666
	INIT_LIST_HEAD(&part->cprop_X);
667
668
669
	part->wl_next         = NULL;
	part->touched_next    = NULL;
	part->cprop_next      = NULL;
Michael Beck's avatar
Michael Beck committed
670
	part->split_next      = NULL;
671
	part->touched         = NULL;
672
	part->n_leader        = 0;
673
674
675
676
677
	part->n_touched       = 0;
	part->max_user_inputs = 0;
	part->on_worklist     = 0;
	part->on_touched      = 0;
	part->on_cprop        = 0;
678
	part->type_is_T_or_C  = 0;
Michael Beck's avatar
Michael Beck committed
679
#ifdef DEBUG_libfirm
680
681
682
	part->dbg_next        = env->dbg_list;
	env->dbg_list         = part;
	part->nr              = part_nr++;
Michael Beck's avatar
Michael Beck committed
683
#endif
684
685

	return part;
686
}  /* new_partition */
687
688

/**
689
 * Get the first node from a partition.
690
 */
691
static inline node_t *get_first_node(const partition_t *X) {
692
	return list_entry(X->Leader.next, node_t, node_list);
693
}  /* get_first_node */
694
695
696
697
698
699
700
701
702

/**
 * 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
 */
703
static inline lattice_elem_t get_partition_type(const partition_t *X) {
704
	const node_t *first = get_first_node(X);
705
706
	return first->type;
}  /* get_partition_type */
707
708
709
710

/**
 * Creates a partition node for the given IR-node and place it
 * into the given partition.
711
712
713
714
 *
 * @param irn   an IR-node
 * @param part  a partition to place the node in
 * @param env   the environment
715
716
 *
 * @return the created node
717
 */
718
static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env) {
719
	/* create a partition node and place it in the partition */
720
	node_t *node = obstack_alloc(&env->obst, sizeof(*node));
721
722

	INIT_LIST_HEAD(&node->node_list);
Michael Beck's avatar
BugFix:    
Michael Beck committed
723
	INIT_LIST_HEAD(&node->cprop_list);
724
725
726
	node->node           = irn;
	node->part           = part;
	node->next           = NULL;
727
	node->race_next      = NULL;
728
	node->type.tv        = tarval_top;
729
730
	node->max_user_input = 0;
	node->next_edge      = 0;
731
	node->n_followers    = 0;
732
733
	node->on_touched     = 0;
	node->on_cprop       = 0;
734
	node->on_fallen      = 0;
735
	node->is_follower    = 0;
Michael Beck's avatar
Michael Beck committed
736
	node->flagged        = 0;
737
738
	set_irn_node(irn, node);

739
740
	list_add_tail(&node->node_list, &part->Leader);
	++part->n_leader;
741

742
	return node;
743
}  /* create_partition_node */
744
745

/**
746
 * Pre-Walker, initialize all Nodes' type to U or top and place
747
 * all nodes into the TOP partition.
748
749
750
 */
static void create_initial_partitions(ir_node *irn, void *ctx) {
	environment_t *env  = ctx;
751
	partition_t   *part = env->initial;
752
	node_t        *node;
753

754
755
	node = create_partition_node(irn, part, env);
	sort_irn_outs(node);
756
757
	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
758

759
760
761
762
763
764
765
766
767
768
769
	if (is_Block(irn)) {
		set_Block_phis(irn, NULL);
	}
}  /* create_initial_partitions */

/**
 * Post-Walker, collect  all Block-Phi lists, set Cond.
 */
static void init_block_phis(ir_node *irn, void *ctx) {
	(void) ctx;

Michael Beck's avatar
BugFix:    
Michael Beck committed
770
771
772
	if (is_Phi(irn)) {
		add_Block_phi(get_nodes_block(irn), irn);
	}
773
}  /* init_block_phis */
774
775

/**
776
777
 * Add a node to the entry.partition.touched set and
 * node->partition to the touched set if not already there.
778
 *
779
780
 * @param y    a node
 * @param env  the environment
781
 */
782
static inline void add_to_touched(node_t *y, environment_t *env) {
783
784
785
	if (y->on_touched == 0) {
		partition_t *part = y->part;

786
787
788
		y->next       = part->touched;
		part->touched = y;
		y->on_touched = 1;
789
		++part->n_touched;
790
791
792
793
794
795

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

		check_list(part->touched, part);
798
	}
799
800
801
802
803
804
805
806
807
}  /* add_to_touched */

/**
 * Place a node on the cprop list.
 *
 * @param y    the node
 * @param env  the environment
 */
static void add_to_cprop(node_t *y, environment_t *env) {
808
809
	ir_node *irn;

810
811
812
	/* Add y to y.partition.cprop. */
	if (y->on_cprop == 0) {
		partition_t *Y = y->part;
813
		ir_node *irn   = y->node;
814

815
816
		/* place Conds and all its Projs on the cprop_X list */
		if (is_Cond(skip_Proj(irn)))
817
818
819
			list_add_tail(&y->cprop_list, &Y->cprop_X);
		else
			list_add_tail(&y->cprop_list, &Y->cprop);
820
821
822
823
824
825
826
827
828
829
830
		y->on_cprop   = 1;

		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;
		}
	}
831
832
	irn = y->node;
	if (get_irn_mode(irn) == mode_T) {
833
834
835
836
		/* mode_T nodes always produce tarval_bottom, so we must explicitly
		   add it's Proj's to get constant evaluation to work */
		int i;

837
838
		for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
			node_t *proj = get_irn_node(get_irn_out(irn, i));
839
840
841

			add_to_cprop(proj, env);
		}
842
	} else if (is_Block(irn)) {
843
844
845
846
		/* 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(). */
		ir_node *phi;
847
		for (phi = get_Block_phis(irn); phi != NULL; phi = get_Phi_next(phi)) {
848
849
850
851
852
			node_t *p = get_irn_node(phi);
			add_to_cprop(p, env);
		}
	}
}  /* add_to_cprop */
853
854

/**
855
856
857
858
859
860
 * 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
861
 */
862
static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env) {
863
	if (Z->on_worklist || Z_prime->n_leader < Z->n_leader) {
864
		add_to_worklist(Z_prime, env);
865
	} else {
866
		add_to_worklist(Z, env);
867
	}
868
}  /* update_worklist */
869

870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
/**
 * Make all inputs to x no longer be F.def_use edges.
 *
 * @param x  the node
 */
static void move_edges_to_leader(node_t *x) {
	ir_node     *irn = x->node;
	int         i, j, k;

	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
		node_t  *pred = get_irn_node(get_irn_n(irn, i));
		ir_node *p;
		int     n;

		p = pred->node;
		n = get_irn_n_outs(p);
		for (j = 1; j <= pred->n_followers; ++j) {
			if (p->out[j].pos == i && p->out[j].use == irn) {
				/* found a follower edge to x, move it to the Leader */
				ir_def_use_edge edge = p->out[j];

				/* remove this edge from the Follower set */
				p->out[j] = p->out[pred->n_followers];
				--pred->n_followers;

				/* sort it into the leader set */
				for (k = pred->n_followers + 2; k <= n; ++k) {
					if (p->out[k].pos >= edge.pos)
						break;
					p->out[k - 1] = p->out[k];
				}
				/* place the new edge here */
				p->out[k - 1] = edge;

				/* edge found and moved */
				break;
			}
		}
	}
}  /* move_edges_to_leader */

911
/**
912
 * Split a partition that has NO followers by a local list.
913
 *
914
 * @param Z    partition to split
915
916
917
918
 * @param g    a (non-empty) node list
 * @param env  the environment
 *
 * @return  a new partition containing the nodes of g
919
 */
920
static partition_t *split_no_followers(partition_t *Z, node_t *g, environment_t *env) {
921
922
923
	partition_t *Z_prime;
	node_t      *node;
	unsigned    n = 0;
924
	int         max_input;
925
926

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

929
930
	assert(g != NULL);

931
	/* Remove g from Z. */
932
	for (node = g; node != NULL; node = node->next) {
933
		assert(node->part == Z);
934
		list_del(&node->node_list);
935
936
		++n;
	}
937
938
	assert(n < Z->n_leader);
	Z->n_leader -= n;
939

940
	/* Move g to a new partition, Z'. */
941
	Z_prime = new_partition(env);
942
	max_input = 0;
943
	for (node = g; node != NULL; node = node->next) {
Michael Beck's avatar
Michael Beck committed
944
		list_add_tail(&node->node_list, &Z_prime->Leader);
945
		node->part = Z_prime;
946
947
		if (node->max_user_input > max_input)
			max_input = node->max_user_input;
948
	}
949
	Z_prime->max_user_inputs = max_input;
950
	Z_prime->n_leader        = n;
951

952
953
954
	check_partition(Z);
	check_partition(Z_prime);

955
	/* for now, copy the type info tag, it will be adjusted in split_by(). */
956
	Z_prime->type_is_T_or_C = Z->type_is_T_or_C;
957

958
959
960
961
	update_worklist(Z, Z_prime, env);

	dump_partition("Now ", Z);
	dump_partition("Created new ", Z_prime);
962
	return Z_prime;
963
964
}  /* split_no_followers */

Michael Beck's avatar
Michael Beck committed
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
/**
 * Make the Follower -> Leader transition for a node.
 *
 * @param n  the node
 */
static void follower_to_leader(node_t *n) {
	assert(n->is_follower == 1);

	DB((dbg, LEVEL_2, "%+F make the follower -> leader transition\n", n->node));
	n->is_follower = 0;
	move_edges_to_leader(n);
	list_del(&n->node_list);
	list_add_tail(&n->node_list, &n->part->Leader);
	++n->part->n_leader;
}  /* follower_to_leader */

981
982
983
984
/**
 * The environment for one race step.
 */
typedef struct step_env {
985
986
987
988
	node_t   *initial;    /**< The initial node list. */
	node_t   *unwalked;   /**< The unwalked node list. */
	node_t   *walked;     /**< The walked node list. */
	int      index;       /**< Next index of Follower use_def edge. */
Michael Beck's avatar
Michael Beck committed
989
	unsigned side;        /**< side number. */
990
991
} step_env;

992
993
994
995
996
997
998
/**
 * Return non-zero, if a input is a real follower
 *
 * @param irn    the node to check
 * @param input  number of the input
 */
static int is_real_follower(const ir_node *irn, int input) {
999
1000
	node_t *pred;