gvn_pre.c 53.4 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
9
/**
 * @file
 * @brief   Global Value Numbering Partial Redundancy Elimination
 *          (VanDrunen Hosking 2004)
Michael Beck's avatar
Michael Beck committed
10
 * @author  Michael Beck
yb9976's avatar
yb9976 committed
11
 * @brief
12
 */
yb9976's avatar
yb9976 committed
13
14
#include "debug.h"
#include "ircons.h"
15
#include "irdom.h"
yb9976's avatar
yb9976 committed
16
17
18
#include "iredges.h"
#include "irflag.h"
#include "irgmod.h"
19
#include "irgopt.h"
Michael Beck's avatar
Michael Beck committed
20
#include "irgwalk.h"
21
#include "irnodehashmap.h"
Michael Beck's avatar
Michael Beck committed
22
#include "irnodeset.h"
Michael Beck's avatar
Michael Beck committed
23
#include "iropt_dbg.h"
yb9976's avatar
yb9976 committed
24
25
26
#include "iroptimize.h"
#include "irouts.h"
#include "valueset.h"
Christian Helmer's avatar
Christian Helmer committed
27
#include "irloop.h"
28
#include "firmstat_t.h"
Michael Beck's avatar
Michael Beck committed
29

Michael Beck's avatar
Michael Beck committed
30
31
32
#include "irgraph_t.h"
#include "irnode_t.h"
#include "iropt_t.h"
Christian Helmer's avatar
Christian Helmer committed
33
34
#include "plist.h"

Christian Helmer's avatar
Christian Helmer committed
35
/* suggested by GVN-PRE authors */
Christian Helmer's avatar
Christian Helmer committed
36
37
38
#define MAX_ANTIC_ITER 10
#define MAX_INSERT_ITER 3

39
40
41
/* Stops antic iteration from processing endless loops. */
#define IGNORE_INF_LOOPS 1
/* Stops antic information to flow over infinite loop backedge */
Christian Helmer's avatar
Christian Helmer committed
42
43
44
45
#define NO_INF_LOOPS 0

/* Attempt to reduce register pressure and reduce code size
   for hoisted nodes. */
46
#define HOIST_HIGH 1
47
#define COMMON_DOM 1
Christian Helmer's avatar
Christian Helmer committed
48
49
50

/* Seamless implementation of handling loads and generally memory
   dependent nodes with GVN-PRE. */
51
#define LOADS 1
52
#define DIVMODS 0
Christian Helmer's avatar
Christian Helmer committed
53

Christian Helmer's avatar
Christian Helmer committed
54
/* Experimental */
55
56

/* Only optimize node directly after phi node if node is only successor. */
57
#define MIN_CUT 0
Christian Helmer's avatar
Christian Helmer committed
58

59
60
61
62
63
/* GVN is very limited. This enables optimize_node during value recognition.
   GVN ist still very limited, since a+1+b+1 doesn't equal a+b+2.
   TODO Broken for yet unknown reasons. */
#define OPTIMIZE_NODES 0

Christian Helmer's avatar
Christian Helmer committed
64

Michael Beck's avatar
Michael Beck committed
65
/** Additional info we need for every block. */
66
typedef struct block_info {
Christian Helmer's avatar
Christian Helmer committed
67
68
69
	ir_valueset_t     *exp_gen;    /* contains this blocks clean expressions */
	ir_valueset_t     *avail_out;  /* available values at block end */
	ir_valueset_t     *antic_in;   /* clean anticipated values at block entry */
Christian Helmer's avatar
Christian Helmer committed
70
	ir_valueset_t     *antic_done; /* keeps elements of antic_in after insert nodes phase */
Christian Helmer's avatar
Christian Helmer committed
71
	ir_valueset_t     *new_set;    /* new by hoisting made available values */
Christian Helmer's avatar
Christian Helmer committed
72
	ir_nodehashmap_t  *trans;      /* contains translated nodes translated into block */
Christian Helmer's avatar
Christian Helmer committed
73
74
	ir_node           *avail;      /* saves available node for insert node phase */
	int                found;      /* saves kind of availability for insert_node phase */
Christian Helmer's avatar
Christian Helmer committed
75
76
	ir_node           *block;      /* block of the block_info */
	struct block_info *next;       /* links all instances for easy access */
77
78
} block_info;

Michael Beck's avatar
Michael Beck committed
79
/**
Christian Helmer's avatar
Christian Helmer committed
80
 * A pair of nodes to be exchanged.
Christian Helmer's avatar
Christian Helmer committed
81
82
 * We have to defer the exchange because there are still needed references
 * to certain nodes.
Michael Beck's avatar
Michael Beck committed
83
 */
84
typedef struct elim_pair {
Christian Helmer's avatar
Christian Helmer committed
85
86
87
88
	ir_node *old_node;      /* node that will be replaced */
	ir_node *new_node;      /* replacement for old_node */
	struct elim_pair *next; /* links all instances for easy access */
	int     reason;         /* reason for the replacement */
89
90
} elim_pair;

Christian Helmer's avatar
Christian Helmer committed
91
/** environment for the GVN-PRE algorithm */
92
typedef struct pre_env {
Christian Helmer's avatar
Christian Helmer committed
93
	ir_graph       *graph;        /* current graph */
94
	struct obstack  obst;         /* obstack to allocate on */
Christian Helmer's avatar
Christian Helmer committed
95
96
97
98
99
100
101
102
103
	ir_node        *start_block;  /* start block of the current graph */
	ir_node        *end_block;    /* end block of the current graph */
	ir_node        *end_node;     /* end node of the current graph */
	block_info     *list;         /* block_info list head */
	elim_pair      *pairs;        /* elim_pair list head */
	ir_nodeset_t   *keeps;        /* a list of to be removed phis to kill their keep alive edges */
	unsigned        last_idx;     /* last node index of input graph */
	char            changes;      /* flag for fixed point iterations - non-zero if changes occurred */
	char            first_iter;   /* non-zero for first fixed point iteration */
Christian Helmer's avatar
Christian Helmer committed
104
	int             iteration;    /* iteration counter */
105
106
107
108
#if OPTIMIZE_NODES
	pset           *value_table;   /* standard value table*/
	pset           *gvnpre_values; /* gvnpre value table */
#endif
109
} pre_env;
110

Christian Helmer's avatar
Christian Helmer committed
111
static pre_env *environ;
Christian Helmer's avatar
Christian Helmer committed
112

Christian Helmer's avatar
Christian Helmer committed
113
114
115
116
/* custom GVN value map */
static ir_nodehashmap_t value_map;

/* debug module handle */
Michael Beck's avatar
Michael Beck committed
117
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
Michael Beck's avatar
Michael Beck committed
118

Christian Helmer's avatar
Christian Helmer committed
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#ifdef DEBUG_libfirm

/* --------------------------------------------------------
 * Statistics
 * --------------------------------------------------------
 */

typedef struct gvnpre_statistics {
	int replaced;
	int partially;
	int fully;
	int loads;
	int divmods;
	int hoist_high;
	int first_iter_found;
	int antic_iterations;
	int insert_iterations;
	int infinite_loops;
} gvnpre_statistics;

139
static gvnpre_statistics *gvnpre_stats = NULL;
Christian Helmer's avatar
Christian Helmer committed
140

Christoph Mallon's avatar
Christoph Mallon committed
141
static void init_stats(void)
Christian Helmer's avatar
Christian Helmer committed
142
143
144
145
{
	gvnpre_stats = XMALLOCZ(gvnpre_statistics);
}

Christoph Mallon's avatar
Christoph Mallon committed
146
static void free_stats(void)
Christian Helmer's avatar
Christian Helmer committed
147
148
149
150
151
{
	free(gvnpre_stats);
	gvnpre_stats = NULL;
}

Christoph Mallon's avatar
Christoph Mallon committed
152
static void print_stats(void)
Christian Helmer's avatar
Christian Helmer committed
153
154
155
156
157
158
159
160
161
162
163
164
165
{
	gvnpre_statistics *stats = gvnpre_stats;
	DB((dbg, LEVEL_1, "replaced             : %d\n", stats->replaced));
	DB((dbg, LEVEL_1, "antic_in iterations  : %d\n", stats->antic_iterations));
	DB((dbg, LEVEL_1, "insert iterations    : %d\n", stats->insert_iterations));
	DB((dbg, LEVEL_1, "infinite loops       : %d\n", stats->infinite_loops));
	DB((dbg, LEVEL_1, "fully redundant      : %d\n", stats->fully));
	DB((dbg, LEVEL_1, "partially redundant  : %d\n", stats->partially));
	DB((dbg, LEVEL_1, "  loads                : %d\n", stats->loads));
	DB((dbg, LEVEL_1, "  Divs/Mods            : %d\n", stats->divmods));
	DB((dbg, LEVEL_1, "  hoist high           : %d\n", stats->hoist_high));
	DB((dbg, LEVEL_1, "  first iteration      : %d\n", stats->first_iter_found));
}
Michael Beck's avatar
Michael Beck committed
166

Christian Helmer's avatar
Christian Helmer committed
167
168
169
170
171
172
173
#define set_stats(var, value) (var)=(value)
#define inc_stats(var)        ((var)+=1)

/* --------------------------------------------------------
 * Dump valuesets
 * --------------------------------------------------------
 */
174
175

/**
Christian Helmer's avatar
Christian Helmer committed
176
 * Dump a value set.
177
 *
Christian Helmer's avatar
Christian Helmer committed
178
179
180
 * @param set    the set to dump
 * @param txt    a text to describe the set
 * @param block  the owner block of the set
181
 */
Christian Helmer's avatar
Christian Helmer committed
182
static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
Michael Beck's avatar
Michael Beck committed
183
{
Christian Helmer's avatar
Christian Helmer committed
184
185
186
	ir_valueset_iterator_t iter;
	ir_node *value, *expr;
	int i;
Michael Beck's avatar
Michael Beck committed
187

Christian Helmer's avatar
Christian Helmer committed
188
189
190
191
192
193
194
195
196
197
198
199
	DB((dbg, LEVEL_2, "%s(%+F) = {\n", txt, block));
	i = 0;
	foreach_valueset(set, value, expr, iter) {
		if ((i & 3) == 3)
			DB((dbg, LEVEL_2, "\n"));
		if (value != expr)
			DB((dbg, LEVEL_2, " %+F(%+F),", expr, value));
		else
			DB((dbg, LEVEL_2, " %+F,", expr));
		++i;
	}
	DB((dbg, LEVEL_2, "\n}\n"));
200
}
Christian Helmer's avatar
Christian Helmer committed
201
202
203
204
205
206
207
208
209
210
211
212

/**
 * Dump all exp_gen value sets.
 *
 * @param list  the list of block infos to retrieve the sets from
 */
static void dump_all_expgen_sets(block_info *list)
{
	block_info *block_info;

	for (block_info = list; block_info != NULL; block_info = block_info->next) {
		dump_value_set(block_info->exp_gen, "[Exp_gen]", block_info->block);
Michael Beck's avatar
Michael Beck committed
213
	}
Michael Beck's avatar
Michael Beck committed
214
215
}

Christian Helmer's avatar
Christian Helmer committed
216
217
#else

yb9976's avatar
yb9976 committed
218
#define dump_all_expgen_sets(list) ((void)(list))
Christian Helmer's avatar
Christian Helmer committed
219
220
221
#define dump_value_set(set, txt, block)

#endif /* DEBUG_libfirm */
Michael Beck's avatar
Michael Beck committed
222

Christian Helmer's avatar
Christian Helmer committed
223
224
225
226
/* --------------------------------------------------------
 * GVN Functions
 * --------------------------------------------------------
 */
Michael Beck's avatar
Michael Beck committed
227
228

/**
Christian Helmer's avatar
Christian Helmer committed
229
230
 * Compares node collisions in valuetable.
 * Modified identities_cmp().
Michael Beck's avatar
Michael Beck committed
231
 */
Christian Helmer's avatar
Christian Helmer committed
232
static int compare_gvn_identities(const void *elt, const void *key)
Michael Beck's avatar
Michael Beck committed
233
{
Christian Helmer's avatar
Christian Helmer committed
234
235
236
	ir_node *a = (ir_node *)elt;
	ir_node *b = (ir_node *)key;
	int i, irn_arity_a;
237

Christian Helmer's avatar
Christian Helmer committed
238
	if (a == b) return 0;
239

Christian Helmer's avatar
Christian Helmer committed
240
241
242
243
	/* phi nodes kill predecessor values and are always different */
	if (is_Phi(a) || is_Phi(b))
		return 1;

Christian Helmer's avatar
Christian Helmer committed
244
	/* memops are not the same, even if we want to optimize them
Christian Helmer's avatar
Christian Helmer committed
245
	   we have to take the order in account */
246
247
248
	if (is_memop(a) || is_memop(b) ||
	    get_irn_mode(a) == mode_T ||
	    get_irn_mode(b) == mode_T) {
249
250
		/* Loads with the same predecessors are the same value;
		   this should only happen after phi translation. */
251
		if ((! is_Load(a) || ! is_Load(b)) && (! is_Store(a) || ! is_Store(b)))
252
253
			return 1;
	}
Christian Helmer's avatar
Christian Helmer committed
254

Christian Helmer's avatar
Christian Helmer committed
255
256
257
258
259
260
261
262
263
264
265
266
	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 */
	irn_arity_a = get_irn_arity(a);
	if (irn_arity_a != get_irn_arity(b))
		return 1;

	/* blocks are never the same */
	if (is_Block(a) || is_Block(b))
		return 1;

267
268
	/* should only be used with gcse enabled */
	assert(get_opt_global_cse());
Christian Helmer's avatar
Christian Helmer committed
269
270
271
272
273
274
275
276

	/* compare a->in[0..ins] with b->in[0..ins] */
	for (i = 0; i < irn_arity_a; ++i) {
		ir_node *pred_a = get_irn_n(a, i);
		ir_node *pred_b = get_irn_n(b, i);
		if (pred_a != pred_b) {
			if (!is_irn_cse_neutral(pred_a) || !is_irn_cse_neutral(pred_b))
				return 1;
277
278
		}
	}
279

Christian Helmer's avatar
Christian Helmer committed
280
281
282
283
284
285
286
287
288
	/*
	 * here, we already now that the nodes are identical except their
	 * attributes
	 */
	if (a->op->ops.node_cmp_attr)
		return a->op->ops.node_cmp_attr(a, b);

	return 0;
}
Michael Beck's avatar
Michael Beck committed
289
290

/**
Christian Helmer's avatar
Christian Helmer committed
291
292
 * Identify does a lookup in the GVN valuetable.
 * To be used when no new GVN values are to be created.
Michael Beck's avatar
Michael Beck committed
293
294
 *
 * @param e  a node representing an expression
Christian Helmer's avatar
Christian Helmer committed
295
 * @return a node representing the value
Michael Beck's avatar
Michael Beck committed
296
 */
Christian Helmer's avatar
Christian Helmer committed
297
static ir_node *identify(ir_node *irn)
Michael Beck's avatar
Michael Beck committed
298
{
Christian Helmer's avatar
Christian Helmer committed
299
300
301
	ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
	if (value)
		return value;
Christian Helmer's avatar
Christian Helmer committed
302
	/* irn represents a new value, so return the leader */
Christian Helmer's avatar
Christian Helmer committed
303
	return identify_remember(irn);
304
}
Michael Beck's avatar
Michael Beck committed
305
306

/**
Christian Helmer's avatar
Christian Helmer committed
307
308
309
 * remember() adds node irn to the GVN valuetable.
 * Identify_remember only identifies values of nodes with the
 * same predecessor nodes (not values). By creating a node from the predecessor
Christian Helmer's avatar
Christian Helmer committed
310
 * values/leaders, a true valuetree is built. Phis kill their predecessor value,
Christian Helmer's avatar
Christian Helmer committed
311
 * so no circular dependencies need to be resolved.
Michael Beck's avatar
Michael Beck committed
312
 *
Christian Helmer's avatar
Christian Helmer committed
313
314
315
316
 * TODO Improvement:
 *      Maybe this could be implemented with a custom node hash that takes
 *      phi nodes and true values (instead of predecessors) into account,
 *      resulting in value numbers.
Christian Helmer's avatar
Christian Helmer committed
317
 * TODO This unnecessarily also handles nodes like calls, which are never equal.
Christian Helmer's avatar
Christian Helmer committed
318
319
320
 *
 * @param irn  a node representing an expression
 * @return     the value of the expression
Michael Beck's avatar
Michael Beck committed
321
 */
Christian Helmer's avatar
Christian Helmer committed
322
static ir_node *remember(ir_node *irn)
323
{
Christian Helmer's avatar
Christian Helmer committed
324
325
326
327
328
	int       arity   = get_irn_arity(irn);
	int       changed = 0;
	ir_node **in      = XMALLOCN(ir_node *, arity);
	ir_node  *value;

329
	foreach_irn_in(irn, i, pred) {
Christian Helmer's avatar
Christian Helmer committed
330
		/* value and leader at the same time */
Christian Helmer's avatar
Christian Helmer committed
331
332
333
		ir_node *pred_value = identify(pred);

		/* phi will be translated anyway, so kill the predecessor values
Christian Helmer's avatar
Christian Helmer committed
334
		   this also prevents circular dependencies */
Christian Helmer's avatar
Christian Helmer committed
335
336
337
338
339
340
		if (is_Phi(pred)) {
			/* every phi represents its own value */
			in[i] = pred;
			continue;
		}

Christian Helmer's avatar
Christian Helmer committed
341
		/* predecessor is not its value representation/the leader */
Christian Helmer's avatar
Christian Helmer committed
342
343
344
345
346
		if (pred != pred_value)
			changed = 1;
		in[i] = pred_value;
	}

347
	if (changed && !is_memop(irn) && get_irn_mode(irn) != mode_X) {
Christian Helmer's avatar
Christian Helmer committed
348
		/* create representative for */
349
		ir_node *nn = new_similar_node(irn, get_nodes_block(irn), in);
Christian Helmer's avatar
Christian Helmer committed
350

351
352
353
354
355
356
357
358
#if OPTIMIZE_NODES
		/* TODO optimize_node() uses the valuetable and thus the custom
		   identify_cmp() and will fail trying. */
		environ->graph->value_table = environ->value_table;
		nn = optimize_node(nn);
		environ->graph->value_table = environ->gvnpre_values;
#endif

Christian Helmer's avatar
Christian Helmer committed
359
360
		/* now the value can be determined because the
		   predecessors are the leaders */
Christian Helmer's avatar
Christian Helmer committed
361
362
363
364
365
366
		value = identify_remember(nn);
	} else {
		value = identify_remember(irn);
	}
	free(in);

Christian Helmer's avatar
Christian Helmer committed
367
	DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
Christian Helmer's avatar
Christian Helmer committed
368
369
370
371
372
	ir_nodehashmap_insert(&value_map, irn, value);

	return value;
}

Christian Helmer's avatar
Christian Helmer committed
373
374
375
/**
 * When the value map has been built we may lookup expressions
 * and remember them if new.
Christian Helmer's avatar
Christian Helmer committed
376
377
378
379
380
381
382
383
 */
static ir_node *identify_or_remember(ir_node *irn)
{
	ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
	if (value)
		return value;
	else
		return remember(irn);
384
}
Michael Beck's avatar
Michael Beck committed
385

Christian Helmer's avatar
Christian Helmer committed
386
387
388
389
390
/* --------------------------------------------------------
 * Block info
 * --------------------------------------------------------
 */

Michael Beck's avatar
Michael Beck committed
391
/**
392
 * Allocate block info for block block.
Michael Beck's avatar
Michael Beck committed
393
394
395
 *
 * @param block   the block
 * @param env     the environment
Michael Beck's avatar
Michael Beck committed
396
 */
yb9976's avatar
yb9976 committed
397
static void alloc_block_info(ir_node *block, pre_env *env)
398
{
399
	block_info *info = OALLOC(&env->obst, block_info);
Michael Beck's avatar
Michael Beck committed
400
401

	set_irn_link(block, info);
Christian Helmer's avatar
Christian Helmer committed
402
403
404
405
	info->exp_gen    = ir_valueset_new(16);
	info->avail_out  = ir_valueset_new(16);
	info->antic_in   = ir_valueset_new(16);
	info->antic_done = ir_valueset_new(16);
406
407
408
409
410
411
412
413
414
415
	info->trans = XMALLOC(ir_nodehashmap_t);
	ir_nodehashmap_init(info->trans);

	info->new_set = NULL;
	info->avail   = NULL;
	info->block   = block;
	info->found   = 1;

	info->next = env->list;
	env->list  = info;
416
}
417

418
419
420
421
422
423
424
425
426
427
428
429
430
static void free_block_info(block_info *block_info)
{
	ir_valueset_del(block_info->exp_gen);
	ir_valueset_del(block_info->avail_out);
	ir_valueset_del(block_info->antic_in);
	if (block_info->trans) {
		ir_nodehashmap_destroy(block_info->trans);
		free(block_info->trans);
	}
	if (block_info->new_set)
		ir_valueset_del(block_info->new_set);
}

431
/**
Christian Helmer's avatar
Christian Helmer committed
432
 * Bottom up walker that ensures that every block gets a block info.
Michael Beck's avatar
Michael Beck committed
433
 *
Christian Helmer's avatar
Christian Helmer committed
434
435
 * @param irn   the node
 * @param ctx   the environment
436
 */
Christian Helmer's avatar
Christian Helmer committed
437
static void block_info_walker(ir_node *irn, void *ctx)
438
{
Christian Helmer's avatar
Christian Helmer committed
439
440
441
442
443
	if (is_Block(irn)) {
		pre_env *env = (pre_env*)ctx;
		alloc_block_info(irn, env);
	}
}
Michael Beck's avatar
Michael Beck committed
444

Christian Helmer's avatar
Christian Helmer committed
445
446
447
448
449
450
451
/**
 * Returns the block info of a block.
 */
static block_info *get_block_info(ir_node *block)
{
	return (block_info*)get_irn_link(block);
}
452

Christian Helmer's avatar
Christian Helmer committed
453
454
455
456
/* --------------------------------------------------------
 * Infinite loop analysis
 * --------------------------------------------------------
 */
457

Christian Helmer's avatar
Christian Helmer committed
458
459
460
461
462
463
/**
 * Walker to set block marks and loop links to 0.
 */
static void clear_block_mark_loop_link(ir_node *block, void *env)
{
	(void) env;
464

Christian Helmer's avatar
Christian Helmer committed
465
466
467
468
469
	if (is_Block(block)) {
		set_Block_mark(block, 0);
		set_loop_link(get_irn_loop(block), NULL);
	}
}
470

Christian Helmer's avatar
Christian Helmer committed
471
472
473
474
475
476
477
478
479
480
481
482
/**
 * Returns non-zero if block is part of real loop loop.
 */

static unsigned in_loop(ir_node *block, ir_loop *loop)
{
	ir_loop *l     = get_irn_loop(block);
	ir_loop *outer = get_irg_loop(environ->graph);

	while (l != loop) {
		/* loop tree root is not a loop */
		if (l == NULL || l == outer)
483
			return 0;
Christian Helmer's avatar
Christian Helmer committed
484
		l = get_loop_outer_loop(l);
485
486
	}
	return 1;
Christian Helmer's avatar
Christian Helmer committed
487
}
488

Michael Beck's avatar
Michael Beck committed
489
/**
Christian Helmer's avatar
Christian Helmer committed
490
 * Returns the outermost real loop of loop.
Michael Beck's avatar
Michael Beck committed
491
 */
Christian Helmer's avatar
Christian Helmer committed
492
static ir_loop *get_loop_outermost(ir_loop *loop)
493
{
Christian Helmer's avatar
Christian Helmer committed
494
495
496
	ir_loop *outer = get_irg_loop(environ->graph);
	ir_loop *l     = loop;
	ir_loop *last  = NULL;
Michael Beck's avatar
Michael Beck committed
497

Christian Helmer's avatar
Christian Helmer committed
498
499
500
	while(l != outer) {
		last = l;
		l = get_loop_outer_loop(l);
Michael Beck's avatar
Michael Beck committed
501
	}
Christian Helmer's avatar
Christian Helmer committed
502
503
	return last;
}
Michael Beck's avatar
Michael Beck committed
504

505
/**
Christian Helmer's avatar
Christian Helmer committed
506
507
508
 * Topologic bottom-up walker sets links of infinite loops to non-zero.
 * Block marks are used to flag blocks reachable (from end) on the one hand,
 * on the other hand they are set if the block is not part of an infinite loop.
509
 */
Christian Helmer's avatar
Christian Helmer committed
510
static void infinite_loop_walker(ir_node *block, void *env)
511
{
Christian Helmer's avatar
Christian Helmer committed
512
513
514
515
516
517
518
519
520
521
	int arity;
	int i;
	(void) env;

	if (! is_Block(block))
		return;

	/* start block has no predecessors */
	if (block == environ->start_block)
		return;
522

Christian Helmer's avatar
Christian Helmer committed
523
524
525
526
527
528
529
530
531
532
	arity = get_irn_arity(block);

	/* block not part of a real loop: no infinite loop */
	if (get_irn_loop(block) == get_irg_loop(environ->graph))
		set_Block_mark(block, 1);

	if (get_Block_mark(block)) {
		/* reachable block: mark all cf predecessors */
		for (i = 0; i < arity; ++i) {
			ir_node *pred = get_Block_cfgpred_block(block, i);
533
			if (pred == NULL)
Christian Helmer's avatar
Christian Helmer committed
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
				continue;
			set_Block_mark(pred, 1);
		}
	} else {
		/* We are in a real loop and see an unreachable block. */
		ir_loop *outermost_loop = get_loop_outermost(get_irn_loop(block));

		/* flag loop as infinite */
		set_loop_link(outermost_loop, outermost_loop);
		DEBUG_ONLY(inc_stats(gvnpre_stats->infinite_loops);)

		/* The cf predecessors are unreachable, but can never be part of
		   an infinite loop, because we just reached them. So we set the
		   blockmark to prevent triggering the infinite loop detection. */

		/* passing information to the cf predecessors */
		for (i = 0; i < arity; ++i) {
			ir_node *pred = get_Block_cfgpred_block(block, i);
552
			if (pred == NULL)
Christian Helmer's avatar
Christian Helmer committed
553
554
555
556
557
558
559
560
561
562
563
564
				continue;

			/* If our cf predecessor is in the same endless loop,
			   it is also unreachable. */
			if (in_loop(pred, outermost_loop)) {
				set_Block_mark(pred, 0);
			} else {
				/* When we leave the unreachable loop, we artificially
				   declare the cf predecessor reachable. */
				set_Block_mark(pred, 1);
			}
		}
565
566
567
	}
}

568
/**
Christian Helmer's avatar
Christian Helmer committed
569
 * Sets loop links of outermost infinite loops to non-zero.
570
 */
Christian Helmer's avatar
Christian Helmer committed
571
static void analyse_loops(ir_graph *irg)
572
{
Christian Helmer's avatar
Christian Helmer committed
573
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
yb9976's avatar
yb9976 committed
574

Christian Helmer's avatar
Christian Helmer committed
575
576
577
578
579
580
	/* reset block mark and loop links */
	irg_walk_blkwise_graph(irg, clear_block_mark_loop_link, NULL, NULL);

	/* mark end block reachable */
	set_Block_mark(get_irg_end_block(irg), 1);
	irg_walk_blkwise_graph(irg, infinite_loop_walker, NULL, NULL);
581

Christian Helmer's avatar
Christian Helmer committed
582
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
583
584
}

585
#if IGNORE_INF_LOOPS || NO_INF_LOOPS
586
/**
Christian Helmer's avatar
Christian Helmer committed
587
 * Returns non-zero if block is part of an infinite loop.
588
 */
Christian Helmer's avatar
Christian Helmer committed
589
static unsigned is_in_infinite_loop(ir_node *block)
590
{
Christian Helmer's avatar
Christian Helmer committed
591
592
593
594
595
	ir_loop *loop;

	assert(is_Block(block));
	loop = get_irn_loop(block);
	assert(loop);
596

Christian Helmer's avatar
Christian Helmer committed
597
598
599
600
601
	loop = get_loop_outermost(loop);
	if (loop)
		return (get_loop_link(loop) != NULL);
	else
		return 0;
602
}
Christian Helmer's avatar
Christian Helmer committed
603
604
605
606
607
608
#endif

/* --------------------------------------------------------
 * GVN-PRE Exp_gen
 * --------------------------------------------------------
 */
609
610

/**
Christian Helmer's avatar
Christian Helmer committed
611
 * Returns non-zero if a node is movable and a possible candidate for PRE.
612
 */
Christian Helmer's avatar
Christian Helmer committed
613
static unsigned is_nice_value(ir_node *n)
614
{
Christian Helmer's avatar
Christian Helmer committed
615
	ir_mode *mode = get_irn_mode(n);
616

Christian Helmer's avatar
Christian Helmer committed
617
	if (is_Phi(n))
618
619
		return 1;

Christian Helmer's avatar
Christian Helmer committed
620
#if LOADS || DIVMODS
621
	if (is_Proj(n) && mode != mode_X && mode != mode_T)
622
		return 1;
Christian Helmer's avatar
Christian Helmer committed
623
624
625
#else
	if (is_Proj(n))
		return 0;
Christian Helmer's avatar
Christian Helmer committed
626
#endif
627

Christian Helmer's avatar
Christian Helmer committed
628
629
#if LOADS
	if (is_Load(n))
630
		return get_Load_volatility(n) == volatility_non_volatile;
631
632
	if (is_Store(n))
		return get_Store_volatility(n) == volatility_non_volatile;
Christian Helmer's avatar
Christian Helmer committed
633
#endif
634

Christian Helmer's avatar
Christian Helmer committed
635
636
	if (get_irn_pinned(n) == op_pin_state_pinned)
		return 0;
637

Christian Helmer's avatar
Christian Helmer committed
638
639
	if (! mode_is_data(mode)) {
		if (! is_Div(n) && ! is_Mod(n))
640
641
642
			return 0;
	}
	return 1;
Christian Helmer's avatar
Christian Helmer committed
643
}
644
645
646
647
648
649
650
651

/**
 * Checks if a node n is clean in block block for exp_gen.
 *
 * @param n      the node
 * @param block  the block
 * @return non-zero value for clean node
 */
652
static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
653
654
655
656
657
658
659
{
	if (is_Phi(n))
		return 1;

	if (! is_nice_value(n))
		return 0;

Christian Helmer's avatar
Christian Helmer committed
660
#if LOADS
Christian Helmer's avatar
Christian Helmer committed
661
	/* filter loads with no phi predecessor from antic_in */
662
663
	if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
		return 0;
664
665
	if (is_Store(n) && ! is_Phi(get_Store_mem(n)))
		return 0;
Christian Helmer's avatar
Christian Helmer committed
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
#endif

#if DIVMODS
	if (is_Div(n)) {
		ir_node *mem = get_Div_mem(n);

		mem = skip_Pin(mem);

		if (! is_Phi(mem) && ! is_NoMem(mem))
			return 0;
	}

	if (is_Mod(n) && ! is_Phi(get_Mod_mem(n)))
		return 0;
#endif
681

682
	foreach_irn_in(n, i, pred) {
683
		if (is_Phi(pred))
684
685
			continue;

686
687
		/* we only handle current block */
		if (get_nodes_block(pred) != block)
688
			continue;
689
690

		if (! is_nice_value(pred))
Christian Helmer's avatar
Christian Helmer committed
691
			return 0;
692

693
		ir_node *const value = identify(pred);
694
695
		if (! ir_valueset_lookup(valueset, value))
			return 0;
696
697
698
699
700
701
	}
	return 1;
}

/**
 * Topological walker puts nodes in top-down topological order into exp_gen set.
Christian Helmer's avatar
Christian Helmer committed
702
 * Assumed to walk blockwise and nodewise topologically top-down.
703
704
705
 *
 * @param irn    the node
 * @param ctx    the environment
Michael Beck's avatar
Michael Beck committed
706
 */
707
708
static void topo_walker(ir_node *irn, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
709
710
711
	ir_node    *block;
	block_info *info;
	ir_node    *value;
712
	(void) ctx;
Michael Beck's avatar
Michael Beck committed
713

Christian Helmer's avatar
Christian Helmer committed
714
	if (is_Block(irn))
Michael Beck's avatar
Michael Beck committed
715
716
		return;

717
718
719
720
721
722
#if OPTIMIZE_NODES
	environ->graph->value_table = environ->value_table;
	identify_remember(irn);
	environ->graph->value_table = environ->gvnpre_values;
#endif

723
	/* GVN step: remember the value. */
Christian Helmer's avatar
Christian Helmer committed
724
	value = remember(irn);
725

726
727
728
	if (is_irn_constlike(irn))
		return;

Michael Beck's avatar
Michael Beck committed
729
730
731
	block = get_nodes_block(irn);
	info  = get_block_info(block);

732
733
734
735
736
737
738
	if (get_irn_mode(irn) != mode_X)
		ir_valueset_insert(info->avail_out, value, irn);

	/* values that are not in antic_in also dont't need to be in any other set */

	if (! is_nice_value(irn))
		return;
739

740
	if (is_clean_in_block(irn, block, info->exp_gen)) {
Christian Helmer's avatar
Christian Helmer committed
741
		DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));
742
743
744

		ir_valueset_insert(info->exp_gen, value, irn);
	}
745
}
746

Christian Helmer's avatar
Christian Helmer committed
747
748
749
750
751
/* --------------------------------------------------------
 * GVN-PRE Antic_in
 * --------------------------------------------------------
 */

752
/**
Christian Helmer's avatar
Christian Helmer committed
753
 * Gets result of nodes phi translation into block.
754
 *
Christian Helmer's avatar
Christian Helmer committed
755
756
 * @param node   the node
 * @param block  the target block
Michael Beck's avatar
Michael Beck committed
757
 *
Christian Helmer's avatar
Christian Helmer committed
758
 * @return a phi translation of node node into block block or NULL
759
 */
Christian Helmer's avatar
Christian Helmer committed
760
static ir_node *get_translated(ir_node *block, ir_node *node)
761
{
Christian Helmer's avatar
Christian Helmer committed
762
763
764
	if (is_irn_constlike(node))
		return node;

765
	return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
Christian Helmer's avatar
Christian Helmer committed
766
767
}

Christian Helmer's avatar
Christian Helmer committed
768
769
770
771
772
773
774
775
776
777
778
779
780
/**
 * Saves result of phi translation of node into predecessor
 * at pos of block succ.
 *
 * @param node   the node
 * @param succ   the successor of the translation target block
 * @param pos    the position of the predecessor block
 * @param trans  the translation result
 *
 */
static void set_translated(ir_nodehashmap_t *map, ir_node *node, ir_node *trans)
{
	if (is_irn_constlike(node))
Michael Beck's avatar
Michael Beck committed
781
		return;
Christian Helmer's avatar
Christian Helmer committed
782
783
784
	/* insert or replace */
	ir_nodehashmap_insert(map, node, trans);
}
Michael Beck's avatar
Michael Beck committed
785

786
/**
787
 * Translates an expression above a Phi.
Michael Beck's avatar
Michael Beck committed
788
 *
789
 * @param node        the node
790
 * @param block       the block the node is translated into
791
 * @param pos         the input number of the destination block
Michael Beck's avatar
Michael Beck committed
792
793
 *
 * @return a node representing the translated value
794
 */
795
static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
796
{
yb9976's avatar
yb9976 committed
797
	int       arity;
798
	ir_node **in;
799
800
	ir_node  *pred_block = get_Block_cfgpred_block(block, pos);
	unsigned  needed;
Michael Beck's avatar
Michael Beck committed
801
802

	if (is_Phi(node)) {
Christian Helmer's avatar
Christian Helmer committed
803
		if (get_nodes_block(node) == block)
Michael Beck's avatar
Michael Beck committed
804
			return get_Phi_pred(node, pos);
Christian Helmer's avatar
Christian Helmer committed
805
		/* this phi does not need translation */
Michael Beck's avatar
Michael Beck committed
806
807
		return node;
	}
808
	arity = get_irn_arity(node);
Christian Helmer's avatar
Christian Helmer committed
809
810

	needed = 0;
811
	in = ALLOCANZ(ir_node *, arity);
Michael Beck's avatar
Michael Beck committed
812

Christian Helmer's avatar
Christian Helmer committed
813
814
815
816
	/* A value has several representatives. The anti leader is chosen to be
	   the main representative. If we access a node as representative of a
	   value we always use the anti leader. The anti leader can be found by
	   antic_in(identify(node)). */
817
	foreach_irn_in(node, i, pred) {
818
819
820
821
822
823
824
825
		ir_node *value  = identify(pred);
		/* get leader for pred to lookup its translated value */
		ir_node *leader = ir_valueset_lookup(leaderset, value);
		ir_node *pred_trans;
		ir_node *new_pred;

		if (! leader)
			leader = pred;
Christian Helmer's avatar
Christian Helmer committed
826

Christian Helmer's avatar
Christian Helmer committed
827
828
		/* we cannot find this value in antic_in, because the value
		   has (possibly) changed! */
829
		pred_trans  = get_translated(pred_block, leader);
Christian Helmer's avatar
Christian Helmer committed
830

Christian Helmer's avatar
Christian Helmer committed
831
832
833
834
835
836
837
838
839
840
841
842

#if DIVMODS
		if (is_Div(node)) {
			ir_node *mem = get_Div_mem(node);

			mem = skip_Pin(mem);

			if (! is_Phi(mem))
				pred_trans = get_Div_mem(node);
		}
#endif

843
		DB((dbg, LEVEL_3, "trans %+F of %+F is  %+F\n", leader, pred_block, pred_trans));
Christian Helmer's avatar
Christian Helmer committed
844
		if (pred_trans == NULL) {
845
			new_pred = pred;
Christian Helmer's avatar
Christian Helmer committed
846
		} else {
847
848
			new_pred = pred_trans;

Christian Helmer's avatar
Christian Helmer committed
849
850
851
			/* loads: Predecessor is a memory phi, which translated yields a proj or
			   another phi. In case of projection and a load predecessor,
			   skip them and use the loads memory. */
852
			if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
Christian Helmer's avatar
Christian Helmer committed
853
#if LOADS || DIVMODS
854
				ir_node *loadstore = get_Proj_pred(pred_trans);
Christian Helmer's avatar
Christian Helmer committed
855
				/* If we do not translate this node, we will get its value wrong. */
Christian Helmer's avatar
Christian Helmer committed
856
				needed |= 1;
857

858
				if (is_Load(loadstore)) {
Christian Helmer's avatar
Christian Helmer committed
859
					/* Put new load under the adjacent loads memory edge
860
					   such that GVN may compare them. */
861
862
863
					new_pred = get_Load_mem(loadstore);
				} else if (is_Store(loadstore)) {
					new_pred = get_Store_mem(loadstore);
864
				}
Christian Helmer's avatar
Christian Helmer committed
865
#endif
866
867
868
869
870
			} else {
				/* predecessor value changed, so translation is needed */
				if (identify(new_pred) != identify(pred))
					needed |= 1;
			}
Christian Helmer's avatar
Christian Helmer committed
871
		}
Michael Beck's avatar
Michael Beck committed
872

873
874
		DB((dbg, LEVEL_4, "in %+F\n", new_pred));
		in[i] = new_pred;
Michael Beck's avatar
Michael Beck committed
875
	}
876

Christian Helmer's avatar
Christian Helmer committed
877
878
	if (! needed)
		return node;
879

Christian Helmer's avatar
Christian Helmer committed
880
	DB((dbg, LEVEL_3, "Translate\n"));
Christian Helmer's avatar
Christian Helmer committed
881
882

	if (is_Proj(node))
883
		pred_block = get_nodes_block(in[0]);
Christian Helmer's avatar
Christian Helmer committed
884

Christian Helmer's avatar
Christian Helmer committed
885
886
887
888
	/* copy node to represent the new value.
	   We do not translate nodes that do not need translation,
	   so we use the newly created nodes as value representatives only.
	   Their block is not important, because we create new ones during
889
	   the insert node phase. */
890
	ir_node *const nn = new_similar_node(node, pred_block, in);
Christian Helmer's avatar
Christian Helmer committed
891
892
	/* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
	   because it already uses availability. */
893

Christian Helmer's avatar
Christian Helmer committed
894
	DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
895
	return nn;
Christian Helmer's avatar
Christian Helmer committed
896
}
Michael Beck's avatar
Michael Beck committed
897

Michael Beck's avatar
Michael Beck committed
898
/**
Michael Beck's avatar
Michael Beck committed
899
 * Block-walker, computes Antic_in(block).
Christian Helmer's avatar
Christian Helmer committed
900
901
 * Builds a value tree out of the graph by translating values
 * over phi nodes.
Michael Beck's avatar
Michael Beck committed
902
903
904
 *
 * @param block  the block
 * @param ctx    the walker environment
Michael Beck's avatar
Michael Beck committed
905
 */
906
907
static void compute_antic(ir_node *block, void *ctx)
{
yb9976's avatar
yb9976 committed
908
909
910
911
912
913
914
	pre_env                *env       = (pre_env*)ctx;
	block_info             *succ_info;
	block_info             *info;
	ir_node                *succ;
	ir_node                *value;
	ir_node                *expr;
	size_t                  size;
Michael Beck's avatar
Michael Beck committed
915
	ir_valueset_iterator_t  iter;
Christian Helmer's avatar
Christian Helmer committed
916
	int                     n_succ;
Michael Beck's avatar
Michael Beck committed
917

yb9976's avatar
yb9976 committed
918
	/* filter blocks from topological walker */
919
920
921
	if (! is_Block(block))
		return;

Michael Beck's avatar
Michael Beck committed
922
	/* the end block has no successor */
923
924
925
926
	if (block == env->end_block)
		return;

	info = get_block_info(block);
Christian Helmer's avatar
Christian Helmer committed
927
	/* track changes */
928
	size = ir_valueset_size(info->antic_in);
Christian Helmer's avatar
Christian Helmer committed
929
	n_succ = get_Block_n_cfg_outs(block);
930

931
	/* add exp_gen */
932
	if (env->first_iter) {
933
#if IGNORE_INF_LOOPS
934
		/* keep antic_in of infinite loops empty */
Christian Helmer's avatar
Christian Helmer committed
935
936
937
938
939
940
		if (! is_in_infinite_loop(block)) {
			foreach_valueset(info->exp_gen, value, expr, iter) {
				ir_valueset_insert(info->antic_in, value, expr);
			}
		}
#else
941
942
		foreach_valueset(info->exp_gen, value, expr, iter) {
			ir_valueset_insert(info->antic_in, value, expr);
943
		}
Christian Helmer's avatar
Christian Helmer committed
944
#endif
945
	}
946

Christian Helmer's avatar
Christian Helmer committed
947
948
949
950
951
	/* successor might have phi nodes */
	if (n_succ == 1 && get_irn_arity(get_Block_cfg_out(block, 0)) > 1) {
		succ      = get_Block_cfg_out(block, 0);
		int pos   = get_Block_cfgpred_pos(succ, block);
		succ_info = get_block_info(succ);
952

Christian Helmer's avatar
Christian Helmer committed
953
954
955
956
957
		/* initialize translated set */
		if (env->first_iter) {
			info->trans = XMALLOC(ir_nodehashmap_t);
			ir_nodehashmap_init(info->trans);
		}
958
959

		foreach_valueset(succ_info->antic_in, value, expr, iter) {
960
961
			ir_node *trans = get_translated(block, expr);
			ir_node *trans_value;
Christian Helmer's avatar
Christian Helmer committed
962
963
			ir_node *represent;

964
965
			if (trans == NULL)
				trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);
966

967
968
969
			/* create new value if necessary */
			trans_value = identify_or_remember(trans);

Christian Helmer's avatar
Christian Helmer committed
970
971
			DB((dbg, LEVEL_3, "Translate %+F %+F to %d = %+F (%+F)\n", expr, succ, pos, trans, trans_value));

Christian Helmer's avatar
Christian Helmer committed
972
			/* On value change (phi present) we need the translated node
Christian Helmer's avatar
Christian Helmer committed
973
974
975
976
977
978
			   to represent the new value for possible further translation. */
			if (value != trans_value)
				represent = trans;
			else
				represent = expr;

Christian Helmer's avatar
Christian Helmer committed
979
			if (is_clean_in_block(expr, block, info->antic_in)) {
980
981
982
#if NO_INF_LOOPS
				/* Prevent information flow over the backedge of endless loops. */
				if (env->iteration <= 2 || (is_backedge(succ, pos) && !is_in_infinite_loop(succ))) {
983
					ir_valueset_replace(info->antic_in, trans_value, represent);
984
				}
985
#else
986
				ir_valueset_replace(info->antic_in, trans_value, represent);
987
#endif
988
			}
Christian Helmer's avatar
Christian Helmer committed
989
990
			set_translated(info->trans, expr, represent);
		}
Christian Helmer's avatar
Christian Helmer committed
991

Christian Helmer's avatar
Christian Helmer committed
992
993
994
995
996
997
998
999
1000
1001
1002
1003
	} else if (n_succ > 1) {
		int         i;
		ir_node    *common     = NULL;
		ir_node    *succ0      = get_Block_cfg_out(block, 0);
		block_info *succ0_info = get_block_info(succ0);

		/* disjoint of antic_ins */
		foreach_valueset(succ0_info->antic_in, value, expr, iter) {
			/* iterate over remaining successors */
			for (i = 1; i < n_succ; ++i) {
				ir_node    *succ      = get_Block_cfg_out(block, i);
				block_info *succ_info = get_block_info(succ);
Michael Beck's avatar
Michael Beck committed
1004

Christian Helmer's avatar
Christian Helmer committed
1005
1006
1007
1008
1009
1010
				/* value in antic_in? */
				common = ir_valueset_lookup(succ_info->antic_in, value);
				if (common == NULL)
					break;
			}

1011
1012
			if (common && is_clean_in_block(expr, block, info->antic_in))
				ir_valueset_replace(info