gvn_pre.c 55.6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * 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.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
/**
 * @file
 * @brief   Global Value Numbering Partial Redundancy Elimination
 *          (VanDrunen Hosking 2004)
Michael Beck's avatar
Michael Beck committed
24
 * @author  Michael Beck
yb9976's avatar
yb9976 committed
25
 * @brief
26
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
28

yb9976's avatar
yb9976 committed
29
30
#include "debug.h"
#include "ircons.h"
31
#include "irdom.h"
yb9976's avatar
yb9976 committed
32
33
34
#include "iredges.h"
#include "irflag.h"
#include "irgmod.h"
35
#include "irgopt.h"
Michael Beck's avatar
Michael Beck committed
36
#include "irgwalk.h"
37
#include "irnodehashmap.h"
Michael Beck's avatar
Michael Beck committed
38
#include "irnodeset.h"
Michael Beck's avatar
Michael Beck committed
39
#include "iropt_dbg.h"
yb9976's avatar
yb9976 committed
40
41
#include "iroptimize.h"
#include "irouts.h"
42
#include "irpass.h"
yb9976's avatar
yb9976 committed
43
#include "valueset.h"
Christian Helmer's avatar
Christian Helmer committed
44
#include "irloop.h"
45
#include "firmstat_t.h"
Michael Beck's avatar
Michael Beck committed
46

Michael Beck's avatar
Michael Beck committed
47
48
49
#include "irgraph_t.h"
#include "irnode_t.h"
#include "iropt_t.h"
Christian Helmer's avatar
Christian Helmer committed
50
51
#include "plist.h"

Christian Helmer's avatar
Christian Helmer committed
52
/* suggested by GVN-PRE authors */
Christian Helmer's avatar
Christian Helmer committed
53
54
55
#define MAX_ANTIC_ITER 10
#define MAX_INSERT_ITER 3

56
57
58
/* 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
59
60
61
62
#define NO_INF_LOOPS 0

/* Attempt to reduce register pressure and reduce code size
   for hoisted nodes. */
63
#define HOIST_HIGH 1
64
#define COMMON_DOM 1
Christian Helmer's avatar
Christian Helmer committed
65
66
67

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

Christian Helmer's avatar
Christian Helmer committed
71
/* Experimental */
72
73

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

76
77
78
79
80
/* 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
81

Michael Beck's avatar
Michael Beck committed
82
/** Additional info we need for every block. */
83
typedef struct block_info {
Christian Helmer's avatar
Christian Helmer committed
84
85
86
	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
87
	ir_valueset_t     *antic_done; /* keeps elements of antic_in after insert nodes phase */
Christian Helmer's avatar
Christian Helmer committed
88
	ir_valueset_t     *new_set;    /* new by hoisting made available values */
Christian Helmer's avatar
Christian Helmer committed
89
	ir_nodehashmap_t  *trans;      /* contains translated nodes translated into block */
Christian Helmer's avatar
Christian Helmer committed
90
91
	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
92
93
	ir_node           *block;      /* block of the block_info */
	struct block_info *next;       /* links all instances for easy access */
94
95
} block_info;

Michael Beck's avatar
Michael Beck committed
96
/**
Christian Helmer's avatar
Christian Helmer committed
97
 * A pair of nodes to be exchanged.
Christian Helmer's avatar
Christian Helmer committed
98
99
 * We have to defer the exchange because there are still needed references
 * to certain nodes.
Michael Beck's avatar
Michael Beck committed
100
 */
101
typedef struct elim_pair {
Christian Helmer's avatar
Christian Helmer committed
102
103
104
105
	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 */
106
107
} elim_pair;

Christian Helmer's avatar
Christian Helmer committed
108
/** environment for the GVN-PRE algorithm */
109
typedef struct pre_env {
Christian Helmer's avatar
Christian Helmer committed
110
	ir_graph       *graph;        /* current graph */
111
	struct obstack  obst;         /* obstack to allocate on */
Christian Helmer's avatar
Christian Helmer committed
112
113
114
115
116
117
118
119
120
	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
121
	int             iteration;    /* iteration counter */
122
123
124
125
#if OPTIMIZE_NODES
	pset           *value_table;   /* standard value table*/
	pset           *gvnpre_values; /* gvnpre value table */
#endif
126
} pre_env;
127

Christian Helmer's avatar
Christian Helmer committed
128
static pre_env *environ;
Christian Helmer's avatar
Christian Helmer committed
129

Christian Helmer's avatar
Christian Helmer committed
130
131
132
133
/* custom GVN value map */
static ir_nodehashmap_t value_map;

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

Christian Helmer's avatar
Christian Helmer committed
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#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;

156
static gvnpre_statistics *gvnpre_stats = NULL;
Christian Helmer's avatar
Christian Helmer committed
157

Christoph Mallon's avatar
Christoph Mallon committed
158
static void init_stats(void)
Christian Helmer's avatar
Christian Helmer committed
159
160
161
162
{
	gvnpre_stats = XMALLOCZ(gvnpre_statistics);
}

Christoph Mallon's avatar
Christoph Mallon committed
163
static void free_stats(void)
Christian Helmer's avatar
Christian Helmer committed
164
165
166
167
168
{
	free(gvnpre_stats);
	gvnpre_stats = NULL;
}

Christoph Mallon's avatar
Christoph Mallon committed
169
static void print_stats(void)
Christian Helmer's avatar
Christian Helmer committed
170
171
172
173
174
175
176
177
178
179
180
181
182
{
	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
183

Christian Helmer's avatar
Christian Helmer committed
184
185
186
187
188
189
190
#define set_stats(var, value) (var)=(value)
#define inc_stats(var)        ((var)+=1)

/* --------------------------------------------------------
 * Dump valuesets
 * --------------------------------------------------------
 */
191
192

/**
Christian Helmer's avatar
Christian Helmer committed
193
 * Dump a value set.
194
 *
Christian Helmer's avatar
Christian Helmer committed
195
196
197
 * @param set    the set to dump
 * @param txt    a text to describe the set
 * @param block  the owner block of the set
198
 */
Christian Helmer's avatar
Christian Helmer committed
199
static void dump_value_set(ir_valueset_t *set, const char *txt, ir_node *block)
Michael Beck's avatar
Michael Beck committed
200
{
Christian Helmer's avatar
Christian Helmer committed
201
202
203
	ir_valueset_iterator_t iter;
	ir_node *value, *expr;
	int i;
Michael Beck's avatar
Michael Beck committed
204

Christian Helmer's avatar
Christian Helmer committed
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
	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"));
}  /* dump_value_set */

/**
 * 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
230
	}
Michael Beck's avatar
Michael Beck committed
231
232
}

Christian Helmer's avatar
Christian Helmer committed
233
234
235
236
237
238
#else

#define dump_all_expgen_sets(list)
#define dump_value_set(set, txt, block)

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

Christian Helmer's avatar
Christian Helmer committed
240
241
242
243
/* --------------------------------------------------------
 * GVN Functions
 * --------------------------------------------------------
 */
Michael Beck's avatar
Michael Beck committed
244
245

/**
Christian Helmer's avatar
Christian Helmer committed
246
247
 * Compares node collisions in valuetable.
 * Modified identities_cmp().
Michael Beck's avatar
Michael Beck committed
248
 */
Christian Helmer's avatar
Christian Helmer committed
249
static int compare_gvn_identities(const void *elt, const void *key)
Michael Beck's avatar
Michael Beck committed
250
{
Christian Helmer's avatar
Christian Helmer committed
251
252
253
	ir_node *a = (ir_node *)elt;
	ir_node *b = (ir_node *)key;
	int i, irn_arity_a;
254

Christian Helmer's avatar
Christian Helmer committed
255
	if (a == b) return 0;
256

Christian Helmer's avatar
Christian Helmer committed
257
258
259
260
	/* 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
261
	/* memops are not the same, even if we want to optimize them
Christian Helmer's avatar
Christian Helmer committed
262
	   we have to take the order in account */
263
264
265
	if (is_memop(a) || is_memop(b) ||
	    get_irn_mode(a) == mode_T ||
	    get_irn_mode(b) == mode_T) {
266
267
		/* Loads with the same predecessors are the same value;
		   this should only happen after phi translation. */
268
		if ((! is_Load(a) || ! is_Load(b)) && (! is_Store(a) || ! is_Store(b)))
269
270
			return 1;
	}
Christian Helmer's avatar
Christian Helmer committed
271

Christian Helmer's avatar
Christian Helmer committed
272
273
274
275
276
277
278
279
280
281
282
283
	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;

284
285
	/* should only be used with gcse enabled */
	assert(get_opt_global_cse());
Christian Helmer's avatar
Christian Helmer committed
286
287
288
289
290
291
292
293

	/* 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;
294
295
		}
	}
296

Christian Helmer's avatar
Christian Helmer committed
297
298
299
300
301
302
303
304
305
	/*
	 * 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
306
307

/**
Christian Helmer's avatar
Christian Helmer committed
308
309
 * 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
310
311
 *
 * @param e  a node representing an expression
Christian Helmer's avatar
Christian Helmer committed
312
 * @return a node representing the value
Michael Beck's avatar
Michael Beck committed
313
 */
Christian Helmer's avatar
Christian Helmer committed
314
static ir_node *identify(ir_node *irn)
Michael Beck's avatar
Michael Beck committed
315
{
Christian Helmer's avatar
Christian Helmer committed
316
317
318
	ir_node *value = ir_nodehashmap_get(ir_node, &value_map, irn);
	if (value)
		return value;
Christian Helmer's avatar
Christian Helmer committed
319
	/* irn represents a new value, so return the leader */
Christian Helmer's avatar
Christian Helmer committed
320
	return identify_remember(irn);
321
}
Michael Beck's avatar
Michael Beck committed
322
323

/**
Christian Helmer's avatar
Christian Helmer committed
324
325
326
 * 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
327
 * values/leaders, a true valuetree is built. Phis kill their predecessor value,
Christian Helmer's avatar
Christian Helmer committed
328
 * so no circular dependencies need to be resolved.
Michael Beck's avatar
Michael Beck committed
329
 *
Christian Helmer's avatar
Christian Helmer committed
330
331
332
333
 * 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
334
 * TODO This unnecessarily also handles nodes like calls, which are never equal.
Christian Helmer's avatar
Christian Helmer committed
335
336
337
 *
 * @param irn  a node representing an expression
 * @return     the value of the expression
Michael Beck's avatar
Michael Beck committed
338
 */
Christian Helmer's avatar
Christian Helmer committed
339
static ir_node *remember(ir_node *irn)
340
{
Christian Helmer's avatar
Christian Helmer committed
341
342
343
344
345
346
347
348
	int       arity   = get_irn_arity(irn);
	int       i;
	int       changed = 0;
	ir_node **in      = XMALLOCN(ir_node *, arity);
	ir_node  *value;

	for (i = 0; i < arity; ++i) {
		ir_node *pred       = get_irn_n(irn, i);
Christian Helmer's avatar
Christian Helmer committed
349
		/* value and leader at the same time */
Christian Helmer's avatar
Christian Helmer committed
350
351
352
		ir_node *pred_value = identify(pred);

		/* phi will be translated anyway, so kill the predecessor values
Christian Helmer's avatar
Christian Helmer committed
353
		   this also prevents circular dependencies */
Christian Helmer's avatar
Christian Helmer committed
354
355
356
357
358
359
		if (is_Phi(pred)) {
			/* every phi represents its own value */
			in[i] = pred;
			continue;
		}

Christian Helmer's avatar
Christian Helmer committed
360
		/* predecessor is not its value representation/the leader */
Christian Helmer's avatar
Christian Helmer committed
361
362
363
364
365
		if (pred != pred_value)
			changed = 1;
		in[i] = pred_value;
	}

366
	if (changed && !is_memop(irn) && get_irn_mode(irn) != mode_X) {
Christian Helmer's avatar
Christian Helmer committed
367
368
369
370
371
372
373
374
375
376
377
		/* create representative for */
		ir_node *nn = new_ir_node(
			get_irn_dbg_info(irn),
			get_irn_irg(irn),
			get_nodes_block(irn),
			get_irn_op(irn),
			get_irn_mode(irn),
			get_irn_arity(irn),
			in);
		copy_node_attr(environ->graph, irn, nn);

378
379
380
381
382
383
384
385
#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
386
387
		/* now the value can be determined because the
		   predecessors are the leaders */
Christian Helmer's avatar
Christian Helmer committed
388
389
390
391
392
393
		value = identify_remember(nn);
	} else {
		value = identify_remember(irn);
	}
	free(in);

Christian Helmer's avatar
Christian Helmer committed
394
	DB((dbg, LEVEL_4, "Remember %+F as value %+F\n", irn, value));
Christian Helmer's avatar
Christian Helmer committed
395
396
397
398
399
	ir_nodehashmap_insert(&value_map, irn, value);

	return value;
}

Christian Helmer's avatar
Christian Helmer committed
400
401
402
/**
 * When the value map has been built we may lookup expressions
 * and remember them if new.
Christian Helmer's avatar
Christian Helmer committed
403
404
405
406
407
408
409
410
 */
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);
411
}
Michael Beck's avatar
Michael Beck committed
412

Christian Helmer's avatar
Christian Helmer committed
413
414
415
416
417
/* --------------------------------------------------------
 * Block info
 * --------------------------------------------------------
 */

Michael Beck's avatar
Michael Beck committed
418
/**
419
 * Allocate block info for block block.
Michael Beck's avatar
Michael Beck committed
420
421
422
 *
 * @param block   the block
 * @param env     the environment
Michael Beck's avatar
Michael Beck committed
423
 */
yb9976's avatar
yb9976 committed
424
static void alloc_block_info(ir_node *block, pre_env *env)
425
{
426
	block_info *info = OALLOC(&env->obst, block_info);
Michael Beck's avatar
Michael Beck committed
427
428

	set_irn_link(block, info);
Christian Helmer's avatar
Christian Helmer committed
429
430
431
432
	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);
433
434
435
436
437
438
439
440
441
442
	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;
yb9976's avatar
yb9976 committed
443
}  /* alloc_block_info */
444

445
446
447
448
449
450
451
452
453
454
455
456
457
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);
}

458
/**
Christian Helmer's avatar
Christian Helmer committed
459
 * Bottom up walker that ensures that every block gets a block info.
Michael Beck's avatar
Michael Beck committed
460
 *
Christian Helmer's avatar
Christian Helmer committed
461
462
 * @param irn   the node
 * @param ctx   the environment
463
 */
Christian Helmer's avatar
Christian Helmer committed
464
static void block_info_walker(ir_node *irn, void *ctx)
465
{
Christian Helmer's avatar
Christian Helmer committed
466
467
468
469
470
	if (is_Block(irn)) {
		pre_env *env = (pre_env*)ctx;
		alloc_block_info(irn, env);
	}
}
Michael Beck's avatar
Michael Beck committed
471

Christian Helmer's avatar
Christian Helmer committed
472
473
474
475
476
477
478
/**
 * Returns the block info of a block.
 */
static block_info *get_block_info(ir_node *block)
{
	return (block_info*)get_irn_link(block);
}
479

Christian Helmer's avatar
Christian Helmer committed
480
481
482
483
/* --------------------------------------------------------
 * Infinite loop analysis
 * --------------------------------------------------------
 */
484

Christian Helmer's avatar
Christian Helmer committed
485
486
487
488
489
490
/**
 * Walker to set block marks and loop links to 0.
 */
static void clear_block_mark_loop_link(ir_node *block, void *env)
{
	(void) env;
491

Christian Helmer's avatar
Christian Helmer committed
492
493
494
495
496
	if (is_Block(block)) {
		set_Block_mark(block, 0);
		set_loop_link(get_irn_loop(block), NULL);
	}
}
497

Christian Helmer's avatar
Christian Helmer committed
498
499
500
501
502
503
504
505
506
507
508
509
/**
 * 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)
510
			return 0;
Christian Helmer's avatar
Christian Helmer committed
511
		l = get_loop_outer_loop(l);
512
513
	}
	return 1;
Christian Helmer's avatar
Christian Helmer committed
514
}
515

Michael Beck's avatar
Michael Beck committed
516
/**
Christian Helmer's avatar
Christian Helmer committed
517
 * Returns the outermost real loop of loop.
Michael Beck's avatar
Michael Beck committed
518
 */
Christian Helmer's avatar
Christian Helmer committed
519
static ir_loop *get_loop_outermost(ir_loop *loop)
520
{
Christian Helmer's avatar
Christian Helmer committed
521
522
523
	ir_loop *outer = get_irg_loop(environ->graph);
	ir_loop *l     = loop;
	ir_loop *last  = NULL;
Michael Beck's avatar
Michael Beck committed
524

Christian Helmer's avatar
Christian Helmer committed
525
526
527
	while(l != outer) {
		last = l;
		l = get_loop_outer_loop(l);
Michael Beck's avatar
Michael Beck committed
528
	}
Christian Helmer's avatar
Christian Helmer committed
529
530
	return last;
}
Michael Beck's avatar
Michael Beck committed
531

532
/**
Christian Helmer's avatar
Christian Helmer committed
533
534
535
 * 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.
536
 */
Christian Helmer's avatar
Christian Helmer committed
537
static void infinite_loop_walker(ir_node *block, void *env)
538
{
Christian Helmer's avatar
Christian Helmer committed
539
540
541
542
543
544
545
546
547
548
	int arity;
	int i;
	(void) env;

	if (! is_Block(block))
		return;

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

Christian Helmer's avatar
Christian Helmer committed
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
	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);
			if (is_Bad(pred))
				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);

			if (is_Bad(pred))
				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);
			}
		}
593
594
595
	}
}

596
/**
Christian Helmer's avatar
Christian Helmer committed
597
 * Sets loop links of outermost infinite loops to non-zero.
598
 */
Christian Helmer's avatar
Christian Helmer committed
599
static void analyse_loops(ir_graph *irg)
600
{
Christian Helmer's avatar
Christian Helmer committed
601
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK);
yb9976's avatar
yb9976 committed
602

Christian Helmer's avatar
Christian Helmer committed
603
604
605
606
607
608
	/* 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);
609

Christian Helmer's avatar
Christian Helmer committed
610
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK);
611
612
}

613
#if IGNORE_INF_LOOPS || NO_INF_LOOPS
614
/**
Christian Helmer's avatar
Christian Helmer committed
615
 * Returns non-zero if block is part of an infinite loop.
616
 */
Christian Helmer's avatar
Christian Helmer committed
617
static unsigned is_in_infinite_loop(ir_node *block)
618
{
Christian Helmer's avatar
Christian Helmer committed
619
620
621
622
623
	ir_loop *loop;

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

Christian Helmer's avatar
Christian Helmer committed
625
626
627
628
629
	loop = get_loop_outermost(loop);
	if (loop)
		return (get_loop_link(loop) != NULL);
	else
		return 0;
630
}
Christian Helmer's avatar
Christian Helmer committed
631
632
633
634
635
636
#endif

/* --------------------------------------------------------
 * GVN-PRE Exp_gen
 * --------------------------------------------------------
 */
637
638

/**
Christian Helmer's avatar
Christian Helmer committed
639
 * Returns non-zero if a node is movable and a possible candidate for PRE.
640
 */
Christian Helmer's avatar
Christian Helmer committed
641
static unsigned is_nice_value(ir_node *n)
642
{
Christian Helmer's avatar
Christian Helmer committed
643
	ir_mode *mode = get_irn_mode(n);
644

Christian Helmer's avatar
Christian Helmer committed
645
	if (is_Phi(n))
646
647
		return 1;

Christian Helmer's avatar
Christian Helmer committed
648
#if LOADS || DIVMODS
649
	if (is_Proj(n) && mode != mode_X && mode != mode_T)
650
		return 1;
Christian Helmer's avatar
Christian Helmer committed
651
652
653
#else
	if (is_Proj(n))
		return 0;
Christian Helmer's avatar
Christian Helmer committed
654
#endif
655

Christian Helmer's avatar
Christian Helmer committed
656
657
#if LOADS
	if (is_Load(n))
658
		return get_Load_volatility(n) == volatility_non_volatile;
659
660
	if (is_Store(n))
		return get_Store_volatility(n) == volatility_non_volatile;
Christian Helmer's avatar
Christian Helmer committed
661
#endif
662

Christian Helmer's avatar
Christian Helmer committed
663
664
	if (get_irn_pinned(n) == op_pin_state_pinned)
		return 0;
665

Christian Helmer's avatar
Christian Helmer committed
666
667
	if (! mode_is_data(mode)) {
		if (! is_Div(n) && ! is_Mod(n))
668
669
670
			return 0;
	}
	return 1;
Christian Helmer's avatar
Christian Helmer committed
671
}
672
673
674
675
676
677
678
679

/**
 * 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
 */
680
static unsigned is_clean_in_block(ir_node *n, ir_node *block, ir_valueset_t *valueset)
681
{
682
	int         i, arity;
683
684
685
686
687
688
689

	if (is_Phi(n))
		return 1;

	if (! is_nice_value(n))
		return 0;

Christian Helmer's avatar
Christian Helmer committed
690
#if LOADS
Christian Helmer's avatar
Christian Helmer committed
691
	/* filter loads with no phi predecessor from antic_in */
692
693
	if (is_Load(n) && ! is_Phi(get_Load_mem(n)))
		return 0;
694
695
	if (is_Store(n) && ! is_Phi(get_Store_mem(n)))
		return 0;
Christian Helmer's avatar
Christian Helmer committed
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
#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
711

Christian Helmer's avatar
Christian Helmer committed
712
713
	arity = get_irn_arity(n);
	for (i = 0; i < arity; ++i) {
714
715
		ir_node *pred   = get_irn_n(n, i);
		ir_node *value;
716

717
		if (is_Phi(pred))
718
719
			continue;

720
721
		/* we only handle current block */
		if (get_nodes_block(pred) != block)
722
			continue;
723
724

		if (! is_nice_value(pred))
Christian Helmer's avatar
Christian Helmer committed
725
			return 0;
726
727
728
729
730

		value = identify(pred);
		if (! ir_valueset_lookup(valueset, value))
			return 0;

731
732
733
734
735
736
	}
	return 1;
}

/**
 * Topological walker puts nodes in top-down topological order into exp_gen set.
Christian Helmer's avatar
Christian Helmer committed
737
 * Assumed to walk blockwise and nodewise topologically top-down.
738
739
740
 *
 * @param irn    the node
 * @param ctx    the environment
Michael Beck's avatar
Michael Beck committed
741
 */
742
743
static void topo_walker(ir_node *irn, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
744
745
746
	ir_node    *block;
	block_info *info;
	ir_node    *value;
747
	(void) ctx;
Michael Beck's avatar
Michael Beck committed
748

Christian Helmer's avatar
Christian Helmer committed
749
	if (is_Block(irn))
Michael Beck's avatar
Michael Beck committed
750
751
		return;

752
753
754
755
756
757
#if OPTIMIZE_NODES
	environ->graph->value_table = environ->value_table;
	identify_remember(irn);
	environ->graph->value_table = environ->gvnpre_values;
#endif

758
	/* GVN step: remember the value. */
Christian Helmer's avatar
Christian Helmer committed
759
	value = remember(irn);
760

761
762
763
	if (is_irn_constlike(irn))
		return;

Michael Beck's avatar
Michael Beck committed
764
765
766
	block = get_nodes_block(irn);
	info  = get_block_info(block);

767
768
769
770
771
772
773
	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;
774

775
	if (is_clean_in_block(irn, block, info->exp_gen)) {
Christian Helmer's avatar
Christian Helmer committed
776
		DB((dbg, LEVEL_3, "%+F clean in block %+F\n", irn, block));
777
778
779

		ir_valueset_insert(info->exp_gen, value, irn);
	}
780
}
781

Christian Helmer's avatar
Christian Helmer committed
782
783
784
785
786
/* --------------------------------------------------------
 * GVN-PRE Antic_in
 * --------------------------------------------------------
 */

787
/**
Christian Helmer's avatar
Christian Helmer committed
788
 * Gets result of nodes phi translation into block.
789
 *
Christian Helmer's avatar
Christian Helmer committed
790
791
 * @param node   the node
 * @param block  the target block
Michael Beck's avatar
Michael Beck committed
792
 *
Christian Helmer's avatar
Christian Helmer committed
793
 * @return a phi translation of node node into block block or NULL
794
 */
Christian Helmer's avatar
Christian Helmer committed
795
static ir_node *get_translated(ir_node *block, ir_node *node)
796
{
Christian Helmer's avatar
Christian Helmer committed
797
798
799
	if (is_irn_constlike(node))
		return node;

800
	return ir_nodehashmap_get(ir_node, get_block_info(block)->trans, node);
Christian Helmer's avatar
Christian Helmer committed
801
802
}

Christian Helmer's avatar
Christian Helmer committed
803
804
805
806
807
808
809
810
811
812
813
814
815
/**
 * 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
816
		return;
Christian Helmer's avatar
Christian Helmer committed
817
818
819
	/* insert or replace */
	ir_nodehashmap_insert(map, node, trans);
}
Michael Beck's avatar
Michael Beck committed
820

821
/**
822
 * Translates an expression above a Phi.
Michael Beck's avatar
Michael Beck committed
823
 *
824
 * @param node        the node
825
 * @param block       the block the node is translated into
826
 * @param pos         the input number of the destination block
Michael Beck's avatar
Michael Beck committed
827
828
 *
 * @return a node representing the translated value
829
 */
830
static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, ir_valueset_t *leaderset)
831
{
yb9976's avatar
yb9976 committed
832
833
	int       i;
	int       arity;
834
	ir_node **in;
835
	ir_node  *pred_block = get_Block_cfgpred_block(block, pos);
836
	ir_node  *nn;
837
	unsigned  needed;
Michael Beck's avatar
Michael Beck committed
838
839

	if (is_Phi(node)) {
Christian Helmer's avatar
Christian Helmer committed
840
		if (get_nodes_block(node) == block)
Michael Beck's avatar
Michael Beck committed
841
			return get_Phi_pred(node, pos);
Christian Helmer's avatar
Christian Helmer committed
842
		/* this phi does not need translation */
Michael Beck's avatar
Michael Beck committed
843
844
		return node;
	}
845
	arity = get_irn_arity(node);
Christian Helmer's avatar
Christian Helmer committed
846
847

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

Christian Helmer's avatar
Christian Helmer committed
850
851
852
853
	/* 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)). */
Michael Beck's avatar
Michael Beck committed
854
	for (i = 0; i < arity; ++i) {
855
856
857
858
859
860
861
862
863
		ir_node *pred   = get_irn_n(node, i);
		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
864

Christian Helmer's avatar
Christian Helmer committed
865
866
		/* we cannot find this value in antic_in, because the value
		   has (possibly) changed! */
867
		pred_trans  = get_translated(pred_block, leader);
Christian Helmer's avatar
Christian Helmer committed
868

Christian Helmer's avatar
Christian Helmer committed
869
870
871
872
873
874
875
876
877
878
879
880

#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

881
		DB((dbg, LEVEL_3, "trans %+F of %+F is  %+F\n", leader, pred_block, pred_trans));
Christian Helmer's avatar
Christian Helmer committed
882
		if (pred_trans == NULL) {
883
			new_pred = pred;
Christian Helmer's avatar
Christian Helmer committed
884
		} else {
885
886
			new_pred = pred_trans;

Christian Helmer's avatar
Christian Helmer committed
887
888
889
			/* 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. */
890
			if (is_Proj(pred_trans) && get_irn_mode(pred_trans) == mode_M) {
Christian Helmer's avatar
Christian Helmer committed
891
#if LOADS || DIVMODS
892
				ir_node *loadstore = get_Proj_pred(pred_trans);
Christian Helmer's avatar
Christian Helmer committed
893
				/* If we do not translate this node, we will get its value wrong. */
Christian Helmer's avatar
Christian Helmer committed
894
				needed |= 1;
895

896
				if (is_Load(loadstore)) {
Christian Helmer's avatar
Christian Helmer committed
897
					/* Put new load under the adjacent loads memory edge
898
					   such that GVN may compare them. */
899
900
901
					new_pred = get_Load_mem(loadstore);
				} else if (is_Store(loadstore)) {
					new_pred = get_Store_mem(loadstore);
902
				}
Christian Helmer's avatar
Christian Helmer committed
903
#endif
904
905
906
907
908
			} else {
				/* predecessor value changed, so translation is needed */
				if (identify(new_pred) != identify(pred))
					needed |= 1;
			}
Christian Helmer's avatar
Christian Helmer committed
909
		}
Michael Beck's avatar
Michael Beck committed
910

911
912
		DB((dbg, LEVEL_4, "in %+F\n", new_pred));
		in[i] = new_pred;
Michael Beck's avatar
Michael Beck committed
913
	}
914

Christian Helmer's avatar
Christian Helmer committed
915
916
	if (! needed)
		return node;
917

Christian Helmer's avatar
Christian Helmer committed
918
	DB((dbg, LEVEL_3, "Translate\n"));
Christian Helmer's avatar
Christian Helmer committed
919
920

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

Christian Helmer's avatar
Christian Helmer committed
923
924
925
926
	/* 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
927
	   the insert node phase. */
Michael Beck's avatar
Michael Beck committed
928
929
	nn = new_ir_node(
		get_irn_dbg_info(node),
Christian Helmer's avatar
Christian Helmer committed
930
		environ->graph,
931
		pred_block,
Michael Beck's avatar
Michael Beck committed
932
933
934
		get_irn_op(node),
		get_irn_mode(node),
		arity,
935
		in);
Michael Beck's avatar
Michael Beck committed
936
	/* We need the attribute copy here, because the Hash value of a
Christian Helmer's avatar
Christian Helmer committed
937
938
939
940
	   node might depend on it. */
	copy_node_attr(environ->graph, node, nn);
	/* Optimizing nn here is tempting but might be against the GVN-PRE algorithm
	   because it already uses availability. */
941

Christian Helmer's avatar
Christian Helmer committed
942
	DB((dbg, LEVEL_3, "New node %+F in %+F origin %+F\n", nn, get_Block_cfgpred_block(block, pos), node));
943
	return nn;
Christian Helmer's avatar
Christian Helmer committed
944
}
Michael Beck's avatar
Michael Beck committed
945

Michael Beck's avatar
Michael Beck committed
946
/**
Michael Beck's avatar
Michael Beck committed
947
 * Block-walker, computes Antic_in(block).
Christian Helmer's avatar
Christian Helmer committed
948
949
 * Builds a value tree out of the graph by translating values
 * over phi nodes.
Michael Beck's avatar
Michael Beck committed
950
951
952
 *
 * @param block  the block
 * @param ctx    the walker environment
Michael Beck's avatar
Michael Beck committed
953
 */
954
955
static void compute_antic(ir_node *block, void *ctx)
{
yb9976's avatar
yb9976 committed
956
957
958
959
960
961
962
	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
963
	ir_valueset_iterator_t  iter;
Christian Helmer's avatar
Christian Helmer committed
964
	int                     n_succ;
Michael Beck's avatar
Michael Beck committed
965

yb9976's avatar
yb9976 committed
966
	/* filter blocks from topological walker */
967
968
969
	if (! is_Block(block))
		return;

Michael Beck's avatar
Michael Beck committed
970
	/* the end block has no successor */
971
972
973
974
	if (block == env->end_block)
		return;

	info = get_block_info(block);
Christian Helmer's avatar
Christian Helmer committed
975
	/* track changes */
976
	size = ir_valueset_size(info->antic_in);
Christian Helmer's avatar
Christian Helmer committed
977
	n_succ = get_Block_n_cfg_outs(block);
978

979
	/* add exp_gen */
980
	if (env->first_iter) {
981
#if IGNORE_INF_LOOPS
982
		/* keep antic_in of infinite loops empty */
Christian Helmer's avatar
Christian Helmer committed
983
984
985
986
987
988
		if (! is_in_infinite_loop(block)) {
			foreach_valueset(info->exp_gen, value, expr, iter) {
				ir_valueset_insert(info->antic_in, value, expr);
			}
		}
#else
989
990
		foreach_valueset(info->exp_gen, value, expr, iter) {
			ir_valueset_insert(info->antic_in, value, expr);
991
		}
Christian Helmer's avatar
Christian Helmer committed
992
#endif
993
	}
994

Christian Helmer's avatar
Christian Helmer committed
995
996
997
998
999
	/* 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);
1000

Christian Helmer's avatar
Christian Helmer committed
1001
1002
1003
1004
1005
		/* initialize translated set */
		if (env->first_iter) {
			info->trans = XMALLOC(ir_nodehashmap_t);
			ir_nodehashmap_init(info->trans);
		}
1006
1007

		foreach_valueset(succ_info->antic_in, value, expr, iter) {
1008
1009
			ir_node *trans = get_translated(block, expr);
			ir_node *trans_value;
Christian Helmer's avatar
Christian Helmer committed
1010
1011
			ir_node *represent;

1012
1013
			if (trans == NULL)
				trans = phi_translate(expr, succ, pos, get_block_info(succ)->antic_in);
1014

1015
1016
1017
			/* create new value if necessary */
			trans_value = identify_or_remember(trans);

Christian Helmer's avatar
Christian Helmer committed
1018
1019
			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
1020
			/* On value change (phi present) we need the translated node
Christian Helmer's avatar
Christian Helmer committed
1021
1022
1023
1024
1025
1026
			   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
1027
			if (is_clean_in_block(expr, block, info->antic_in)) {
1028
1029
1030
#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))) {
1031
					ir_valueset_replace(info->antic_in, trans_value, represent);
1032
				}
1033
#else
1034
				ir_valueset_replace(info->antic_in, trans_value, represent);
1035
#endif
1036
			}