bespillremat.c 115 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
25
26
27
28
29
30
31
/** vim: set sw=4 ts=4:
 * @file   bespillremat.c
 * @date   2006-04-06
 * @author Adam M. Szalkowski & Sebastian Hack
 *
 * ILP based spilling & rematerialization
 *
 * Copyright (C) 2006 Universitaet Karlsruhe
 * Released under the GPL
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef WITH_ILP

#include <math.h>

#include "hashptr.h"
#include "debug.h"
#include "obst.h"
#include "set.h"
#include "list.h"
#include "pmap.h"

#include "irprintf.h"
#include "irgwalk.h"
#include "irdump_t.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "irloop_t.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
32
#include "phiclass_t.h"
33
#include "iredges.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
34
#include "execfreq.h"
35
#include "irvrfy.h"
36
37

#include <lpp/lpp.h>
Sebastian Hack's avatar
Sebastian Hack committed
38
#include <lpp/mps.h>
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <lpp/lpp_net.h>
#include <lpp/lpp_cplex.h>
//#include <lc_pset.h>
#include <libcore/lc_bitset.h>

#include "be_t.h"
#include "belive_t.h"
#include "besched_t.h"
#include "beirgmod.h"
#include "bearch.h"
#include "benode_t.h"
#include "beutil.h"
#include "bespillremat.h"
#include "bespill.h"
Adam Szalkowski's avatar
Adam Szalkowski committed
53
#include "bepressurestat.h"
54
55
56

#include "bechordal_t.h"

Sebastian Hack's avatar
Sebastian Hack committed
57
58
59
60
61
#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#endif /* WITH_LIBCORE */

Adam Szalkowski's avatar
Adam Szalkowski committed
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#define DUMP_PROBLEM       1
#define DUMP_MPS           2
#define DUMP_SOLUTION      4

#define KEEPALIVE_REMATS   1
#define KEEPALIVE_SPILLS   2
#define KEEPALIVE_RELOADS  4

#define VERIFY_MEMINTERF   1
#define VERIFY_DOMINANCE   2

#define REMATS_NONE        0
#define REMATS_BRIGGS      1
#define REMATS_NOINVERSE   2
#define REMATS_ALL         3

static int opt_dump_flags   = 0;
static int opt_log = 0;
static int opt_keep_alive   = 0;
static int opt_goodwin = 1;
static int opt_memcopies = 1;
static int opt_memoperands = 1;
static int opt_verify = VERIFY_MEMINTERF;
static int opt_remats = REMATS_ALL;
static int opt_repair_schedule = 0;
static int opt_no_enlarge_liveness = 0;
static int opt_remat_while_live = 1;
static int opt_timeout = 300;
Adam Szalkowski's avatar
Adam Szalkowski committed
90
91
92
93
static double opt_cost_reload = 8.0;
static double opt_cost_memoperand =  7.0;
static double opt_cost_spill =  50.0;
static double opt_cost_remat =  1.0;
Sebastian Hack's avatar
Sebastian Hack committed
94
95
96
97
98
99
100


#ifdef WITH_LIBCORE
static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "problem",  DUMP_PROBLEM  },
	{ "mps",      DUMP_MPS      },
	{ "solution", DUMP_SOLUTION },
Adam Szalkowski's avatar
Adam Szalkowski committed
101
102
103
104
105
106
107
108
109
110
111
	{ NULL,       0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&opt_dump_flags, dump_items
};

static const lc_opt_enum_mask_items_t keepalive_items[] = {
	{ "remats",  KEEPALIVE_REMATS  },
	{ "spills",  KEEPALIVE_SPILLS  },
	{ "reloads", KEEPALIVE_RELOADS },
Sebastian Hack's avatar
Sebastian Hack committed
112
113
114
	{ NULL,      0 }
};

Adam Szalkowski's avatar
Adam Szalkowski committed
115
static lc_opt_enum_mask_var_t keep_alive_var = {
Adam Szalkowski's avatar
Adam Szalkowski committed
116
117
118
119
120
121
122
123
124
125
126
	&opt_keep_alive, keepalive_items
};

static const lc_opt_enum_mask_items_t remats_items[] = {
	{ "none",      REMATS_NONE      },
	{ "briggs",    REMATS_BRIGGS    },
	{ "noinverse", REMATS_NOINVERSE },
	{ "ALL",       REMATS_ALL       },
	{ NULL,        0 }
};

Adam Szalkowski's avatar
Adam Szalkowski committed
127
static lc_opt_enum_mask_var_t remats_var = {
Adam Szalkowski's avatar
Adam Szalkowski committed
128
	&opt_remats, remats_items
Sebastian Hack's avatar
Sebastian Hack committed
129
130
131
};

static const lc_opt_table_entry_t options[] = {
Adam Szalkowski's avatar
Adam Szalkowski committed
132
133
134
135
136
	LC_OPT_ENT_ENUM_MASK("keepalive", "keep alive remats, spills or reloads",                   &keep_alive_var),

	LC_OPT_ENT_BOOL     ("goodwin",  "activate goodwin reduction",                              &opt_goodwin),
	LC_OPT_ENT_BOOL     ("memcopies",  "activate memcopy handling",                             &opt_memcopies),
	LC_OPT_ENT_BOOL     ("memoperands",  "activate memoperands",                                &opt_memoperands),
Adam Szalkowski's avatar
Adam Szalkowski committed
137
	LC_OPT_ENT_ENUM_INT ("remats",  "type of remats to insert (none, briggs, noinverse or all)",&remats_var),
Adam Szalkowski's avatar
Adam Szalkowski committed
138
	LC_OPT_ENT_BOOL     ("repair_schedule",  "repair the schedule by rematting once used nodes",&opt_repair_schedule),
Adam Szalkowski's avatar
Adam Szalkowski committed
139
	LC_OPT_ENT_BOOL     ("no_enlage_liveness",  "do not enlarge liveness of operands of remats",&opt_no_enlarge_liveness),
Adam Szalkowski's avatar
Adam Szalkowski committed
140
141
142
143
144
145
146
147
148
149
	LC_OPT_ENT_BOOL     ("remat_while_live",  "remat only values that can be used by real ops", &opt_remat_while_live),

	LC_OPT_ENT_ENUM_MASK("dump", "dump ifg before, after or after each cloud",                  &dump_var),
	LC_OPT_ENT_BOOL     ("log",  "activate the lpp log",                                        &opt_log),
	LC_OPT_ENT_INT      ("timeout",  "ILP solver timeout",                                      &opt_timeout),

	LC_OPT_ENT_DBL      ("cost_reload",  "cost of a reload",                                    &opt_cost_reload),
	LC_OPT_ENT_DBL      ("cost_memoperand",  "cost of a memory operand",                        &opt_cost_memoperand),
	LC_OPT_ENT_DBL      ("cost_spill",  "cost of a spill instruction",                          &opt_cost_spill),
	LC_OPT_ENT_DBL      ("cost_remat",  "cost of a rematerialization",                          &opt_cost_remat),
Sebastian Hack's avatar
Sebastian Hack committed
150
151
152
153
154
155
156
157
158
159
	{ NULL }
};

void be_spill_remat_register_options(lc_opt_entry_t *grp)
{
	lc_opt_entry_t *my_grp = lc_opt_get_grp(grp, "remat");
	lc_opt_add_table(my_grp, options);
}
#endif

Adam Szalkowski's avatar
Adam Szalkowski committed
160

Adam Szalkowski's avatar
Adam Szalkowski committed
161
//#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */
162
163

#define  SOLVE
164
//#define  SOLVE_LOCAL
165
166
167
168
#define LPP_SERVER "i44pc52"
#define LPP_SOLVER "cplex"


Adam Szalkowski's avatar
Adam Szalkowski committed
169
#define MAX_PATHS      16
170
171
172
173
174
175
#define ILP_UNDEF		-1

typedef struct _spill_ilp_t {
	const arch_register_class_t  *cls;
	int                           n_regs;
	const be_chordal_env_t       *chordal_env;
Sebastian Hack's avatar
Sebastian Hack committed
176
	be_lv_t                      *lv;
177
178
179
180
	lpp_t                        *lpp;
	struct obstack               *obst;
	set                          *remat_info;
	pset                         *all_possible_remats;
181
	pset                         *inverse_ops;
182
183
	ir_node                      *keep;
	set                          *values; /**< for collecting all definitions of values before running ssa-construction */
184
	pset                         *spills;
185
	set                          *interferences;
186
	ir_node                      *m_unknown;
187
	set                          *memoperands;
188
189
190
191
192
193
194
	DEBUG_ONLY(firm_dbg_module_t * dbg);
} spill_ilp_t;

typedef int ilp_var_t;
typedef int ilp_cst_t;

typedef struct _spill_bb_t {
195
196
	set      *ilp;
	set      *reloads;
197
198
199
} spill_bb_t;

typedef struct _remat_t {
Christian Würdig's avatar
Christian Würdig committed
200
201
	const ir_node        *op;      /**< for copy_irn */
	const ir_node        *value;   /**< the value which is being recomputed by this remat */
Adam Szalkowski's avatar
Adam Szalkowski committed
202
	const ir_node        *proj;    /**< not NULL if the above op produces a tuple */
Christian Würdig's avatar
Christian Würdig committed
203
	int                   cost;    /**< cost of this remat */
204
	int                   inverse; /**< nonzero if this is an inverse remat */
205
206
207
208
209
210
211
212
213
214
215
216
} remat_t;

/**
 * Data to be attached to each IR node. For remats this contains the ilp_var
 * for this remat and for normal ops this contains the ilp_vars for
 * reloading each operand
 */
typedef struct _op_t {
	int             is_remat;
	union {
		struct {
			ilp_var_t       ilp;
Adam Szalkowski's avatar
Adam Szalkowski committed
217
			const remat_t  *remat; /** the remat this op belongs to */
218
219
220
221
222
			int             pre; /** 1, if this is a pressure-increasing remat */
		} remat;
		struct {
			ilp_var_t       ilp;
			ir_node        *op; /** the operation this live range belongs to */
223
224
225
226
			union {
				ilp_var_t      *reloads;
				ilp_var_t      *copies;
			} args;
227
228
229
230
231
		} live_range;
	} attr;
} op_t;

typedef struct _defs_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
232
233
234
	const ir_node   *value;
	ir_node         *spills;  /**< points to the first spill for this value (linked by link field) */
	ir_node         *remats;  /**< points to the first definition for this value (linked by link field) */
235
236
237
238
239
240
241
242
243
244
245
246
247
248
} defs_t;

typedef struct _remat_info_t {
	const ir_node       *irn; /**< the irn to which these remats belong */
	pset                *remats; /**< possible remats for this value */
	pset                *remats_by_operand; /**< remats with this value as operand */
} remat_info_t;

typedef struct _keyval_t {
	const void          *key;
	const void          *val;
} keyval_t;

typedef struct _spill_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
249
250
251
252
253
254
	ir_node            *irn;
	ilp_var_t           reg_in;
	ilp_var_t           mem_in;
	ilp_var_t           reg_out;
	ilp_var_t           mem_out;
	ilp_var_t           spill;
255
256
} spill_t;

257
typedef struct _memoperand_t {
Adam Szalkowski's avatar
Adam Szalkowski committed
258
	ir_node             *irn; /**< the irn */
259
260
261
262
	unsigned int         pos; /**< the position of the argument */
	ilp_var_t            ilp; /**< the ilp var for this memory operand */
} memoperand_t;

263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
static INLINE int
has_reg_class(const spill_ilp_t * si, const ir_node * irn)
{
	return chordal_has_class(si->chordal_env, irn);
}

#if 0
static int
cmp_remat(const void *a, const void *b)
{
	const keyval_t *p = a;
	const keyval_t *q = b;
	const remat_t  *r = p->val;
	const remat_t  *s = q->val;

	assert(r && s);

	return !(r == s || r->op == s->op);
}
#endif
static int
cmp_remat(const void *a, const void *b)
{
	const remat_t  *r = a;
	const remat_t  *s = a;

	return !(r == s || r->op == s->op);
}

static int
cmp_spill(const void *a, const void *b, size_t size)
{
	const spill_t *p = a;
	const spill_t *q = b;

//	return !(p->irn == q->irn && p->bb == q->bb);
	return !(p->irn == q->irn);
}

302
303
304
305
306
307
308
309
310
static int
cmp_memoperands(const void *a, const void *b, size_t size)
{
	const memoperand_t *p = a;
	const memoperand_t *q = b;

	return !(p->irn == q->irn && p->pos == q->pos);
}

311
static keyval_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
312
set_find_keyval(set * set, const void * key)
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
{
	keyval_t     query;

	query.key = key;
	return set_find(set, &query, sizeof(query), HASH_PTR(key));
}

static keyval_t *
set_insert_keyval(set * set, void * key, void * val)
{
	keyval_t     query;

	query.key = key;
	query.val = val;
	return set_insert(set, &query, sizeof(query), HASH_PTR(key));
}

static defs_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
331
set_find_def(set * set, const ir_node * value)
332
333
334
335
336
337
338
339
{
	defs_t     query;

	query.value = value;
	return set_find(set, &query, sizeof(query), HASH_PTR(value));
}

static defs_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
340
set_insert_def(set * set, const ir_node * value)
341
342
343
344
345
346
347
348
349
{
	defs_t     query;

	query.value = value;
	query.spills = NULL;
	query.remats = NULL;
	return set_insert(set, &query, sizeof(query), HASH_PTR(value));
}

350
351
352
353
354
355
356
357
358
359
360
361
static memoperand_t *
set_insert_memoperand(set * set, ir_node * irn, unsigned int pos, ilp_var_t ilp)
{
	memoperand_t     query;

	query.irn = irn;
	query.pos = pos;
	query.ilp = ilp;
	return set_insert(set, &query, sizeof(query), HASH_PTR(irn)+pos);
}

static memoperand_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
362
set_find_memoperand(set * set, const ir_node * irn, unsigned int pos)
363
364
365
{
	memoperand_t     query;

Adam Szalkowski's avatar
Adam Szalkowski committed
366
	query.irn = (ir_node*)irn;
367
368
369
370
371
	query.pos = pos;
	return set_find(set, &query, sizeof(query), HASH_PTR(irn)+pos);
}


372
static spill_t *
Adam Szalkowski's avatar
Adam Szalkowski committed
373
set_find_spill(set * set, const ir_node * value)
374
375
376
{
	spill_t     query;

Adam Szalkowski's avatar
Adam Szalkowski committed
377
	query.irn = (ir_node*)value;
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
	return set_find(set, &query, sizeof(query), HASH_PTR(value));
}

#define pset_foreach(s,i) for((i)=pset_first((s)); (i); (i)=pset_next((s)))
#define set_foreach(s,i) for((i)=set_first((s)); (i); (i)=set_next((s)))
#define foreach_post_remat(s,i) for((i)=next_post_remat((s)); (i); (i)=next_post_remat((i)))
#define foreach_pre_remat(si,s,i) for((i)=next_pre_remat((si),(s)); (i); (i)=next_pre_remat((si),(i)))
#define	sched_foreach_op(s,i) for((i)=sched_next_op((s));!sched_is_end((i));(i)=sched_next_op((i)))

static int
cmp_remat_info(const void *a, const void *b, size_t size)
{
	const remat_info_t *p = a;
	const remat_info_t *q = b;

	return !(p->irn == q->irn);
}

static int
cmp_defs(const void *a, const void *b, size_t size)
{
	const defs_t *p = a;
	const defs_t *q = b;

	return !(p->value == q->value);
}

static int
cmp_keyval(const void *a, const void *b, size_t size)
{
	const keyval_t *p = a;
	const keyval_t *q = b;

	return !(p->key == q->key);
}

Sebastian Hack's avatar
Sebastian Hack committed
414
static double
415
execution_frequency(const spill_ilp_t *si, const ir_node * irn)
416
{
417
#define FUDGE 0.001
418
#ifndef EXECFREQ_LOOPDEPH
419
	return get_block_execfreq(si->chordal_env->exec_freq, get_block(irn)) + FUDGE;
420
421
422
423
424
425
#else
	if(is_Block(irn))
		return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
	else
		return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE;
#endif
426
427
}

428
429
430
431
static double
get_cost(const spill_ilp_t * si, const ir_node * irn)
{
	if(be_is_Spill(irn)) {
Adam Szalkowski's avatar
Adam Szalkowski committed
432
		return opt_cost_spill;
433
	} else if(be_is_Reload(irn)){
Adam Szalkowski's avatar
Adam Szalkowski committed
434
		return opt_cost_reload;
435
436
437
438
439
	} else {
		return arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, irn);
	}
}

440
441
442
443
444
445
/**
 * Checks, whether node and its operands have suitable reg classes
 */
static INLINE int
is_rematerializable(const spill_ilp_t * si, const ir_node * irn)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
446
	int               n;
447
448
449
450
451
452
453
454
	const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
	int               remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;

#if 0
	if(!remat)
		ir_fprintf(stderr, "  Node %+F is not rematerializable\n", irn);
#endif

Adam Szalkowski's avatar
Adam Szalkowski committed
455
456
	for (n = get_irn_arity(irn)-1; n>=0 && remat; --n) {
		ir_node        *op = get_irn_n(irn, n);
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
		remat &= has_reg_class(si, op) || arch_irn_get_flags(arch_env, op) & arch_irn_flags_ignore || (get_irn_op(op) == op_NoMem);

//		if(!remat)
//			ir_fprintf(stderr, "  Argument %d (%+F) of Node %+F has wrong regclass\n", i, op, irn);
	}

	return remat;
}

/**
 * Try to create a remat from @p op with destination value @p dest_value
 */
static INLINE remat_t *
get_remat_from_op(spill_ilp_t * si, const ir_node * dest_value, const ir_node * op)
{
	remat_t  *remat = NULL;

//	if(!mode_is_datab(get_irn_mode(dest_value)))
//		return NULL;

	if(dest_value == op) {
		const ir_node *proj = NULL;

		if(is_Proj(dest_value)) {
			op = get_irn_n(op, 0);
			proj = dest_value;
		}

		if(!is_rematerializable(si, op))
			return NULL;

		remat = obstack_alloc(si->obst, sizeof(*remat));
		remat->op = op;
490
		remat->cost = get_cost(si, op);
491
492
		remat->value = dest_value;
		remat->proj = proj;
493
		remat->inverse = 0;
494
495
	} else {
		arch_inverse_t     inverse;
Adam Szalkowski's avatar
Adam Szalkowski committed
496
		int                n;
497
498

		/* get the index of the operand we want to retrieve by the inverse op */
Adam Szalkowski's avatar
Adam Szalkowski committed
499
500
		for (n = get_irn_arity(op)-1; n>=0; --n) {
			ir_node        *arg = get_irn_n(op, n);
501
502
503

			if(arg == dest_value) break;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
504
		if(n<0) return NULL;
505

Adam Szalkowski's avatar
Adam Szalkowski committed
506
		DBG((si->dbg, LEVEL_5, "\t  requesting inverse op for argument %d of op %+F\n", n, op));
507
508

		/* else ask the backend to give an inverse op */
Adam Szalkowski's avatar
Adam Szalkowski committed
509
		if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, n, &inverse, si->obst)) {
510
511
			int   i;

512
513
514
515
			DBG((si->dbg, LEVEL_4, "\t  backend gave us an inverse op with %d nodes and cost %d\n", inverse.n, inverse.costs));

			assert(inverse.n > 0 && "inverse op should have at least one node");

Adam Szalkowski's avatar
Adam Szalkowski committed
516
			for(i=inverse.n-1; i>=0; --i) {
517
518
519
				pset_insert_ptr(si->inverse_ops, inverse.nodes[i]);
			}

520
521
522
523
524
525
			if(inverse.n <= 2) {
				remat = obstack_alloc(si->obst, sizeof(*remat));
				remat->op = inverse.nodes[0];
				remat->cost = inverse.costs;
				remat->value = dest_value;
				remat->proj = (inverse.n==2)?inverse.nodes[1]:NULL;
526
				remat->inverse = 1;
527
528
529

				assert(is_Proj(remat->proj));
			} else {
530
				assert(0 && "I can not handle remats with more than 2 nodes");
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
			}
		}
	}

	if(remat) {
		if(remat->proj) {
			DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F with %+F\n", remat->op, dest_value, op, remat->proj));
		} else {
			DBG((si->dbg, LEVEL_3, "\t >Found remat %+F for %+F from %+F\n", remat->op, dest_value, op));
		}
	}
	return remat;
}


static INLINE void
add_remat(const spill_ilp_t * si, const remat_t * remat)
{
	remat_info_t    *remat_info,
                     query;
Adam Szalkowski's avatar
Adam Szalkowski committed
551
	int              n;
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566

	assert(remat->op);
	assert(remat->value);

	query.irn = remat->value;
	query.remats = NULL;
	query.remats_by_operand = NULL;
	remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(remat->value));

	if(remat_info->remats == NULL) {
		remat_info->remats = new_pset(cmp_remat, 4096);
	}
	pset_insert(remat_info->remats, remat, HASH_PTR(remat->op));

	/* insert the remat into the remats_be_operand set of each argument of the remat op */
Adam Szalkowski's avatar
Adam Szalkowski committed
567
568
	for (n = get_irn_arity(remat->op)-1; n>=0; --n) {
		ir_node        *arg = get_irn_n(remat->op, n);
569
570
571
572
573
574
575
576
577
578
579
580
581

		query.irn = arg;
		query.remats = NULL;
		query.remats_by_operand = NULL;
		remat_info = set_insert(si->remat_info, &query, sizeof(query), HASH_PTR(arg));

		if(remat_info->remats_by_operand == NULL) {
			remat_info->remats_by_operand = new_pset(cmp_remat, 4096);
		}
		pset_insert(remat_info->remats_by_operand, remat, HASH_PTR(remat->op));
	}
}

582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
static int
get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn)
{
	const ir_edge_t   *edge = get_irn_out_edge_first(irn);
	int                i = 0;

	while(edge) {
		if(!pset_find_ptr(si->inverse_ops, edge->src)) {
			++i;
		}
		edge = get_irn_out_edge_next(irn, edge);
	}

	return i;
}
597
598
599
600
601
602
603
604
605
606
607
608
609

static int
get_irn_n_nonignore_args(const spill_ilp_t * si, const ir_node * irn)
{
	int n;
	unsigned int ret = 0;

	for(n=get_irn_arity(irn)-1; n>=0; --n) {
		if(has_reg_class(si, irn)) ++ret;
	}

	return ret;
}
610

611
612
613
static INLINE void
get_remats_from_op(spill_ilp_t * si, const ir_node * op)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
614
	int      n;
615
616
	remat_t *remat;

617
	if( has_reg_class(si, op)
Adam Szalkowski's avatar
Adam Szalkowski committed
618
619
	&& (opt_repair_schedule || get_irn_n_nonremat_edges(si, op) > 1)
	&& (opt_remats !=  REMATS_BRIGGS || get_irn_n_nonignore_args(si, op) == 0)
620
	) {
621
622
623
624
625
626
		remat = get_remat_from_op(si, op, op);
		if(remat) {
			add_remat(si, remat);
		}
	}

Adam Szalkowski's avatar
Adam Szalkowski committed
627
628
629
630
631
632
633
634
635
636
637
638
	if(opt_remats == REMATS_ALL) {
		/* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg)
		   for each arg */
		for (n = get_irn_arity(op)-1; n>=0; --n) {
			ir_node        *arg = get_irn_n(op, n);

			if(has_reg_class(si, arg)) {
				/* try to get an inverse remat */
				remat = get_remat_from_op(si, arg, op);
				if(remat) {
					add_remat(si, remat);
				}
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
			}
		}
	}
}

static INLINE int
value_is_defined_before(const spill_ilp_t * si, const ir_node * pos, const ir_node * val)
{
	ir_node *block;
	ir_node *def_block = get_nodes_block(val);
	int      ret;

	if(val == pos)
		return 0;

	/* if pos is at end of a basic block */
	if(is_Block(pos)) {
		ret = (pos == def_block || block_dominates(def_block, pos));
//		ir_fprintf(stderr, "(def(bb)=%d) ", ret);
		return ret;
	}

	/* else if this is a normal operation */
	block = get_nodes_block(pos);
	if(block == def_block) {
664
665
		if(!sched_is_scheduled(val)) return 1;

666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
		ret = sched_comes_after(val, pos);
//		ir_fprintf(stderr, "(def(same block)=%d) ",ret);
		return ret;
	}

	ret = block_dominates(def_block, block);
//	ir_fprintf(stderr, "(def(other block)=%d) ", ret);
	return ret;
}

static INLINE ir_node *
sched_block_last_noncf(const spill_ilp_t * si, const ir_node * bb)
{
    return sched_skip((ir_node*)bb, 0, sched_skip_cf_predicator, (void *) si->chordal_env->birg->main_env->arch_env);
}

/**
 * Returns first non-Phi node of block @p bb
 */
static INLINE ir_node *
sched_block_first_nonphi(const ir_node * bb)
{
	return sched_skip((ir_node*)bb, 1, sched_skip_phi_predicator, NULL);
}

static int
sched_skip_proj_predicator(const ir_node * irn, void * data)
{
	return (is_Proj(irn));
}

static INLINE ir_node *
sched_next_nonproj(const ir_node * irn, int forward)
{
	return sched_skip((ir_node*)irn, forward, sched_skip_proj_predicator, NULL);
}

/**
 * Returns next operation node (non-Proj) after @p irn
 * or the basic block of this node
 */
static INLINE ir_node *
sched_next_op(const ir_node * irn)
{
	ir_node *next = sched_next(irn);

	if(is_Block(next))
		return next;

	return sched_next_nonproj(next, 1);
}

/**
 * Returns previous operation node (non-Proj) before @p irn
 * or the basic block of this node
 */
static INLINE ir_node *
sched_prev_op(const ir_node * irn)
{
	ir_node *prev = sched_prev(irn);

	if(is_Block(prev))
		return prev;

	return sched_next_nonproj(prev, 0);
}

static void
sched_put_after(ir_node * insert, ir_node * irn)
{
	if(is_Block(insert)) {
		insert = sched_block_first_nonphi(insert);
	} else {
		insert = sched_next_op(insert);
	}
	sched_add_before(insert, irn);
}

static void
sched_put_before(const spill_ilp_t * si, ir_node * insert, ir_node * irn)
{
  if(is_Block(insert)) {
	  insert = sched_block_last_noncf(si, insert);
  } else {
	  insert = sched_next_nonproj(insert, 0);
	  insert = sched_prev(insert);
  }
  sched_add_after(insert, irn);
}

/**
 * Tells you whether a @p remat can be placed before the irn @p pos
 */
static INLINE int
can_remat_before(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
{
	const ir_node   *op = remat->op;
	const ir_node   *prev;
Adam Szalkowski's avatar
Adam Szalkowski committed
764
	int        n,
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
			   res = 1;

	if(is_Block(pos)) {
		prev = sched_block_last_noncf(si, pos);
		prev = sched_next_nonproj(prev, 0);
	} else {
		prev = sched_prev_op(pos);
	}
	/* do not remat if the rematted value is defined immediately before this op */
	if(prev == remat->op) {
		return 0;
	}

#if 0
	/* this should be just fine, the following OP will be using this value, right? */

	/* only remat AFTER the real definition of a value (?) */
	if(!value_is_defined_before(si, pos, remat->value)) {
//		ir_fprintf(stderr, "error(not defined)");
		return 0;
	}
#endif

Adam Szalkowski's avatar
Adam Szalkowski committed
788
789
	for(n=get_irn_arity(op)-1; n>=0 && res; --n) {
		const ir_node   *arg = get_irn_n(op, n);
790

Adam Szalkowski's avatar
Adam Szalkowski committed
791
792
793
794
795
796
		if(opt_no_enlarge_liveness) {
			if(has_reg_class(si, arg) && live) {
				res &= pset_find_ptr(live, arg)?1:0;
			} else {
				res &= value_is_defined_before(si, pos, arg);
			}
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
		} else {
			res &= value_is_defined_before(si, pos, arg);
		}
	}

	return res;
}

/**
 * Tells you whether a @p remat can be placed after the irn @p pos
 */
static INLINE int
can_remat_after(const spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
{
	if(is_Block(pos)) {
		pos = sched_block_first_nonphi(pos);
	} else {
		pos = sched_next_op(pos);
	}

	/* only remat AFTER the real definition of a value (?) */
	if(!value_is_defined_before(si, pos, remat->value)) {
		return 0;
	}

	return can_remat_before(si, remat, pos, live);
}

/**
 * Collect potetially rematerializable OPs
 */
static void
walker_remat_collector(ir_node * irn, void * data)
{
	spill_ilp_t    *si = data;

	if(!is_Block(irn) && !is_Phi(irn)) {
		DBG((si->dbg, LEVEL_4, "\t  Processing %+F\n", irn));
		get_remats_from_op(si, irn);
	}
}

/**
 * Inserts a copy of @p irn before @p pos
 */
static ir_node *
insert_copy_before(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
{
	ir_node     *bb;
	ir_node     *copy;

	bb = is_Block(pos)?pos:get_nodes_block(pos);
	copy = exact_copy(irn);
Adam Szalkowski's avatar
Adam Szalkowski committed
850
851

	_set_phi_class(copy, NULL);
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
	set_nodes_block(copy, bb);
	sched_put_before(si, pos, copy);

	return copy;
}

/**
 * Inserts a copy of @p irn after @p pos
 */
static ir_node *
insert_copy_after(const spill_ilp_t * si, const ir_node * irn, ir_node * pos)
{
	ir_node     *bb;
	ir_node     *copy;

	bb = is_Block(pos)?pos:get_nodes_block(pos);
	copy = exact_copy(irn);
Adam Szalkowski's avatar
Adam Szalkowski committed
869
870

	_set_phi_class(copy, NULL);
871
872
873
874
875
876
	set_nodes_block(copy, bb);
	sched_put_after(pos, copy);

	return copy;
}

Adam Szalkowski's avatar
Adam Szalkowski committed
877
static ir_node *
Adam Szalkowski's avatar
Adam Szalkowski committed
878
insert_remat_after(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
{
	char     buf[256];

	if(can_remat_after(si, remat, pos, live)) {
		ir_node         *copy,
						*proj_copy;
		op_t            *op;

		DBG((si->dbg, LEVEL_3, "\t  >inserting remat %+F\n", remat->op));

		copy = insert_copy_after(si, remat->op, pos);

		ir_snprintf(buf, sizeof(buf), "remat2_%N_%N", copy, pos);
		op = obstack_alloc(si->obst, sizeof(*op));
		op->is_remat = 1;
		op->attr.remat.remat = remat;
		op->attr.remat.pre = 0;
896
		op->attr.remat.ilp = lpp_add_var_default(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos), 0.0);
897
898
899
900
901
902
903
904
905
906
907

		set_irn_link(copy, op);
		pset_insert_ptr(si->all_possible_remats, copy);
		if(remat->proj) {
			proj_copy = insert_copy_after(si, remat->proj, copy);
			set_irn_n(proj_copy, 0, copy);
			set_irn_link(proj_copy, op);
			pset_insert_ptr(si->all_possible_remats, proj_copy);
		} else {
			proj_copy = NULL;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
908
909

		return copy;
910
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
911
912

	return NULL;
913
914
}

Adam Szalkowski's avatar
Adam Szalkowski committed
915
static ir_node *
Adam Szalkowski's avatar
Adam Szalkowski committed
916
insert_remat_before(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
{
	char     buf[256];

	if(can_remat_before(si, remat, pos, live)) {
		ir_node         *copy,
						*proj_copy;
		op_t            *op;

		DBG((si->dbg, LEVEL_3, "\t  >inserting remat %+F\n", remat->op));

		copy = insert_copy_before(si, remat->op, pos);

		ir_snprintf(buf, sizeof(buf), "remat_%N_%N", copy, pos);
		op = obstack_alloc(si->obst, sizeof(*op));
		op->is_remat = 1;
		op->attr.remat.remat = remat;
		op->attr.remat.pre = 1;
934
		op->attr.remat.ilp = lpp_add_var_default(si->lpp, buf, lpp_binary, remat->cost*execution_frequency(si, pos), 0.0);
935
936
937
938
939
940
941
942
943
944
945

		set_irn_link(copy, op);
		pset_insert_ptr(si->all_possible_remats, copy);
		if(remat->proj) {
			proj_copy = insert_copy_after(si, remat->proj, copy);
			set_irn_n(proj_copy, 0, copy);
			set_irn_link(proj_copy, op);
			pset_insert_ptr(si->all_possible_remats, proj_copy);
		} else {
			proj_copy = NULL;
		}
Adam Szalkowski's avatar
Adam Szalkowski committed
946
947

		return copy;
948
	}
Adam Szalkowski's avatar
Adam Szalkowski committed
949
950

	return NULL;
951
952
}

Adam Szalkowski's avatar
Adam Szalkowski committed
953
954
static int
get_block_n_succs(const ir_node *block) {
955
956
957
958
959
960
961
962
963
964
965
	const ir_edge_t *edge;

	assert(edges_activated(current_ir_graph));

	edge = get_block_succ_first(block);
	if (! edge)
		return 0;

	edge = get_block_succ_next(block, edge);
	return edge ? 2 : 1;
}
966

Adam Szalkowski's avatar
Adam Szalkowski committed
967
968
969
static int
is_merge_edge(const ir_node * bb)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
970
971
972
973
	if(opt_goodwin)
		return get_block_n_succs(bb) == 1;
	else
		return 1;
Adam Szalkowski's avatar
Adam Szalkowski committed
974
975
976
977
978
}

static int
is_diverge_edge(const ir_node * bb)
{
Adam Szalkowski's avatar
Adam Szalkowski committed
979
980
981
982
	if(opt_goodwin)
		return get_Block_n_cfgpreds(bb) == 1;
	else
		return 1;
Adam Szalkowski's avatar
Adam Szalkowski committed
983
984
}

985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
static void
walker_regclass_copy_insertor(ir_node * irn, void * data)
{
	spill_ilp_t    *si = data;

	if(is_Phi(irn) && has_reg_class(si, irn)) {
		int n;

		for(n=get_irn_arity(irn)-1; n>=0; --n) {
			ir_node  *phi_arg = get_irn_n(irn, n);
			ir_node  *bb = get_Block_cfgpred_block(get_nodes_block(irn), n);

			if(!has_reg_class(si, phi_arg)) {
				ir_node   *copy = be_new_Copy(si->cls, si->chordal_env->irg, bb, phi_arg);
				ir_node   *pos = sched_block_last_noncf(si, bb);
				op_t      *op = obstack_alloc(si->obst, sizeof(*op));
For faster browsing, not all history is shown. View entire blame