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

/**
 * @file
 * @author   Christian Helmer
9
 * @brief    loop inversion and loop unrolling
10
 *
11
 */
Christoph Mallon's avatar
Christoph Mallon committed
12
13

#include <math.h>
Matthias Braun's avatar
Matthias Braun committed
14
15
#include <stdbool.h>

Matthias Braun's avatar
Matthias Braun committed
16
#include "util.h"
Christoph Mallon's avatar
Christoph Mallon committed
17
#include "array.h"
18
#include "debug.h"
Matthias Braun's avatar
Matthias Braun committed
19
#include "panic.h"
Christoph Mallon's avatar
Christoph Mallon committed
20
#include "irbackedge_t.h"
21
#include "ircons_t.h"
Christoph Mallon's avatar
Christoph Mallon committed
22
#include "irdom.h"
23
#include "iredges_t.h"
24
#include "irgmod.h"
Christoph Mallon's avatar
Christoph Mallon committed
25
#include "irgopt.h"
26
#include "irgwalk.h"
Christoph Mallon's avatar
Christoph Mallon committed
27
#include "irloop_t.h"
28
#include "irnode_t.h"
Christoph Mallon's avatar
Christoph Mallon committed
29
30
#include "irnodemap.h"
#include "iroptimize.h"
31
32
#include "irouts.h"
#include "irtools.h"
Christoph Mallon's avatar
Christoph Mallon committed
33
#include "opt_init.h"
34

35
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
36
37
38
39
40

/**
 * Convenience macro for iterating over every phi node of the given block.
 * Requires phi list per block.
 */
41
#define for_each_phi(block, phi) \
Christoph Mallon's avatar
Christoph Mallon committed
42
	for (ir_node *phi = get_Block_phis((block)); phi; phi = get_Phi_next(phi))
43

Christoph Mallon's avatar
Christoph Mallon committed
44
45
#define for_each_phi_safe(block, phi, next) \
	for (ir_node *phi = get_Block_phis((block)), *next = NULL; phi ? next = get_Phi_next(phi), true : false; phi = next)
46

47
/* Currently processed loop. */
48
static ir_loop *cur_loop;
49

50
/* Flag for kind of unrolling. */
Christoph Mallon's avatar
Christoph Mallon committed
51
typedef enum unrolling_kind_flag {
52
53
54
	constant,
	invariant
} unrolling_kind_flag;
55

56
/* Condition for performing visiting a node during copy_walk. */
Matthias Braun's avatar
Matthias Braun committed
57
typedef bool walker_condition(const ir_node *);
58

59
60
/* Node and position of a predecessor. */
typedef struct entry_edge {
61
	ir_node *node;
Christoph Mallon's avatar
Christoph Mallon committed
62
	int      pos;
63
	ir_node *pred;
64
} entry_edge;
65

66
67
68
69
/* Node info for unrolling. */
typedef struct unrolling_node_info {
	ir_node **copies;
} unrolling_node_info;
70

71
/* Outs of the nodes head. */
72
static entry_edge *cur_head_outs;
73

74
/* Information about the loop head */
Matthias Braun's avatar
Matthias Braun committed
75
76
static ir_node *loop_head       = NULL;
static bool     loop_head_valid = true;
77

78
79
/* List of all inner loops, that are processed. */
static ir_loop **loops;
80

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/* Stats */
typedef struct loop_stats_t {
	unsigned loops;
	unsigned inverted;
	unsigned too_large;
	unsigned too_large_adapted;
	unsigned cc_limit_reached;
	unsigned calls_limit;

	unsigned u_simple_counting_loop;
	unsigned constant_unroll;
	unsigned invariant_unroll;

	unsigned unhandled;
} loop_stats_t;

static loop_stats_t stats;

/* Set stats to sero */
Matthias Braun's avatar
Matthias Braun committed
100
static void reset_stats(void)
101
102
103
104
105
{
	memset(&stats, 0, sizeof(loop_stats_t));
}

/* Print stats */
Matthias Braun's avatar
Matthias Braun committed
106
static void print_stats(void)
107
108
{
	DB((dbg, LEVEL_2, "---------------------------------------\n"));
Christoph Mallon's avatar
Christoph Mallon committed
109
110
111
112
113
114
115
116
117
	DB((dbg, LEVEL_2, "loops             :   %d\n", stats.loops));
	DB((dbg, LEVEL_2, "inverted          :   %d\n", stats.inverted));
	DB((dbg, LEVEL_2, "too_large         :   %d\n", stats.too_large));
	DB((dbg, LEVEL_2, "too_large_adapted :   %d\n", stats.too_large_adapted));
	DB((dbg, LEVEL_2, "cc_limit_reached  :   %d\n", stats.cc_limit_reached));
	DB((dbg, LEVEL_2, "calls_limit       :   %d\n", stats.calls_limit));
	DB((dbg, LEVEL_2, "u_simple_counting :   %d\n", stats.u_simple_counting_loop));
	DB((dbg, LEVEL_2, "constant_unroll   :   %d\n", stats.constant_unroll));
	DB((dbg, LEVEL_2, "invariant_unroll  :   %d\n", stats.invariant_unroll));
118
119
120
121
122
	DB((dbg, LEVEL_2, "=======================================\n"));
}

/* Commandline parameters */
typedef struct loop_opt_params_t {
Christoph Mallon's avatar
Christoph Mallon committed
123
124
125
126
127
128
129
130
131
132
133
134
	unsigned max_loop_size;     /* Maximum number of nodes  [nodes]*/
	int      depth_adaption;    /* Loop nest depth adaption [percent] */
	unsigned allowed_calls;     /* Number of calls allowed [number] */
	bool     count_phi;         /* Count phi nodes */

	unsigned max_cc_size;       /* Maximum condition chain size [nodes] */
	unsigned max_branches;

	unsigned max_unrolled_loop_size;    /* [nodes] */
	bool     allow_const_unrolling;
	bool     allow_invar_unrolling;
	unsigned invar_unrolling_min_size;  /* [nodes] */
135
136
137
} loop_opt_params_t;

static loop_opt_params_t opt_params;
138
139
140

/* Loop analysis informations */
typedef struct loop_info_t {
Christoph Mallon's avatar
Christoph Mallon committed
141
142
143
144
	unsigned   nodes;      /* node count */
	unsigned   branches;   /* number of conditions */
	unsigned   calls;      /* number of calls */
	unsigned   cf_outs;    /* number of cf edges which leave the loop */
145
	ir_node   *cf_out;     /* single loop leaving cf edge */
Christoph Mallon's avatar
Christoph Mallon committed
146
	int        be_src_pos; /* position of the single own backedge in the head */
147
148

	/* for inversion */
Christoph Mallon's avatar
Christoph Mallon committed
149
	unsigned cc_size; /* nodes in the condition chain */
150
151

	/* for unrolling */
Christoph Mallon's avatar
Christoph Mallon committed
152
153
154
155
	unsigned max_unroll;       /* Number of unrolls satisfying max_loop_size */
	unsigned exit_cond;        /* 1 if condition==true exits the loop.  */
	unsigned latest_value:1;   /* 1 if condition is checked against latest counter value */
	unsigned decreasing:1;     /* Step operation is_Sub, or step is<0 */
156
157

	/* IV informations of a simple loop */
158
159
160
161
162
	ir_node *start_val;
	ir_node *step;
	ir_node *end_val;
	ir_node *iteration_phi;
	ir_node *add;
163

Christoph Mallon's avatar
Christoph Mallon committed
164
165
	ir_node            *duff_cond;   /* Duff mod */
	unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */
166
167
168
169
170
} loop_info_t;

/* Information about the current loop */
static loop_info_t loop_info;

171
/* Outs of the condition chain (loop inversion). */
172
static ir_node **cc_blocks;
173
174
175
176
177
178
179
180
181
182
183
/* Array of df loops found in the condition chain. */
static entry_edge *head_df_loop;
/* Number of blocks in cc */
static unsigned inversion_blocks_in_cc;


/* Cf/df edges leaving the loop.
 * Called entries here, as they are used to enter the loop with walkers. */
static entry_edge *loop_entries;
/* Number of unrolls to perform */
static int unroll_nr;
184
/* Phase is used to keep copies of nodes. */
185
186
static ir_nodemap     map;
static struct obstack obst;
187

188
189
190
191
192
193
194
195
/* Loop operations.  */
typedef enum loop_op_t {
	loop_op_inversion,
	loop_op_unrolling,
	loop_op_peeling
} loop_op_t;

/* Returns the maximum nodes for the given nest depth */
Christoph Mallon's avatar
Christoph Mallon committed
196
static unsigned get_max_nodes_adapted(unsigned const depth)
197
{
198
199
	double perc = 100.0 + (double)opt_params.depth_adaption;
	double factor = pow(perc / 100.0, depth);
200

201
	return (int)((double)opt_params.max_loop_size * factor);
202
}
203

204
/* Returns 0 if the node or block is not in cur_loop. */
Christoph Mallon's avatar
Christoph Mallon committed
205
static bool is_in_loop(const ir_node *const node)
206
{
Matthias Braun's avatar
Matthias Braun committed
207
	return get_irn_loop(get_block_const(node)) == cur_loop;
208
}
209

210
211
/* Returns 0 if the given edge is not a backedge
 * with its pred in the cur_loop. */
Christoph Mallon's avatar
Christoph Mallon committed
212
static bool is_own_backedge(const ir_node *const n, int const pos)
213
{
Christoph Mallon's avatar
Christoph Mallon committed
214
	return is_backedge(n, pos) && is_in_loop(get_Block_cfgpred(n, pos));
215
216
}

217
/* Finds loop head and some loop_info as calls or else if necessary. */
Christoph Mallon's avatar
Christoph Mallon committed
218
static void get_loop_info(ir_node *const node, void *const env)
219
{
220
	(void)env;
221

Christoph Mallon's avatar
Christoph Mallon committed
222
223
	bool const node_in_loop = is_in_loop(node);

Matthias Braun's avatar
Matthias Braun committed
224
225
	/* collect some loop information */
	if (node_in_loop) {
226
227
228
229
		switch (get_irn_opcode(node)) {
		case iro_Call:
			++loop_info.calls;
			goto count;
Matthias Braun's avatar
Matthias Braun committed
230

231
232
233
234
235
		case iro_Phi:
			if (opt_params.count_phi)
				goto count;
				break;

236
		case iro_Address:
237
		case iro_Align:
238
239
		case iro_Confirm:
		case iro_Const:
240
		case iro_Offset:
241
		case iro_Proj:
242
		case iro_Size:
243
244
245
246
247
248
249
			break;

		default:
count:
			++loop_info.nodes;
			break;
		}
Matthias Braun's avatar
Matthias Braun committed
250
251
	}

252
253
	foreach_irn_in_r(node, i, pred) {
		bool pred_in_loop = is_in_loop(pred);
254

Matthias Braun's avatar
Matthias Braun committed
255
		if (is_Block(node) && !node_in_loop && pred_in_loop) {
256
257
			/* Count cf outs */
			++loop_info.cf_outs;
258
			loop_info.cf_out = pred;
259
260
		}

261
		/* Find the loops head/the blocks with cfpred outside of the loop */
262
263
264
265
		if (is_Block(node)) {
			unsigned outs_n = 0;

			/* Count innerloop branches */
266
			foreach_block_succ(node, edge) {
Matthias Braun's avatar
Matthias Braun committed
267
268
				ir_node *succ = get_edge_src_irn(edge);
				if (is_Block(succ) && is_in_loop(succ))
269
270
271
272
273
274
275
276
277
278
					++outs_n;
			}
			if (outs_n > 1)
				++loop_info.branches;

			if (node_in_loop && !pred_in_loop && loop_head_valid) {
				ir_node *cfgpred = get_Block_cfgpred(node, i);

				if (!is_in_loop(cfgpred)) {
					DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n",
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
279
					    node, pred));
280
281
					/* another head? We do not touch this. */
					if (loop_head && loop_head != node) {
Matthias Braun's avatar
Matthias Braun committed
282
						loop_head_valid = false;
283
284
285
					} else {
						loop_head = node;
					}
286
287
288
				}
			}
		}
289
290
	}
}
291

292
293
/* Finds all edges with users outside of the loop
 * and definition inside the loop. */
Christoph Mallon's avatar
Christoph Mallon committed
294
static void get_loop_entries(ir_node *const node, void *const env)
295
{
Christoph Mallon's avatar
Christoph Mallon committed
296
	(void)env;
297

298
	foreach_irn_in(node, i, pred) {
Christoph Mallon's avatar
Christoph Mallon committed
299
300
		if (is_in_loop(pred) && !is_in_loop(node)) {
			entry_edge const entry = { .node = node, .pos = i, .pred = pred };
301
			ARR_APP1(entry_edge, loop_entries, entry);
302
303
304
		}
	}
}
305

306
/* ssa */
307
308
309
static ir_node *ssa_second_def;
static ir_node *ssa_second_def_block;

Christian Helmer's avatar
Christian Helmer committed
310
/**
311
 * Walks the graph bottom up, searching for definitions and creates phis.
Christian Helmer's avatar
Christian Helmer committed
312
 */
Christoph Mallon's avatar
Christoph Mallon committed
313
static ir_node *search_def_and_create_phis(ir_node *const block, ir_mode *const mode, int const first)
314
{
Christoph Mallon's avatar
Christoph Mallon committed
315
	ir_graph *const irg = get_irn_irg(block);
316

Christian Helmer's avatar
Christian Helmer committed
317
	DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %N\n", block));
318
319
320

	/* Prevents creation of phi that would be bad anyway.
	 * Dead and bad blocks. */
321
322
	if (get_irn_arity(block) < 1 || is_Bad(block)) {
		DB((dbg, LEVEL_5, "ssa bad %N\n", block));
Matthias Braun's avatar
Matthias Braun committed
323
		return new_r_Bad(irg, mode);
324
	}
325

326
	if (block == ssa_second_def_block && !first) {
Christian Helmer's avatar
Christian Helmer committed
327
		DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def));
328
329
330
331
332
		return ssa_second_def;
	}

	/* already processed this block? */
	if (irn_visited(block)) {
Christoph Mallon's avatar
Christoph Mallon committed
333
		ir_node *const value = (ir_node *)get_irn_link(block);
Christian Helmer's avatar
Christian Helmer committed
334
		DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value));
335
336
337
338
339
340
		return value;
	}

	assert(block != get_irg_start_block(irg));

	/* a Block with only 1 predecessor needs no Phi */
Christoph Mallon's avatar
Christoph Mallon committed
341
	int const n_cfgpreds = get_Block_n_cfgpreds(block);
342
343
	if (n_cfgpreds == 1) {
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
344
		ir_node *value;
345

Christian Helmer's avatar
Christian Helmer committed
346
		DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block));
347

348
		value = search_def_and_create_phis(pred_block, mode, 0);
349
		set_irn_link(block, value);
350
		mark_irn_visited(block);
351

352
353
354
355
		return value;
	}

	/* create a new Phi */
Christoph Mallon's avatar
Christoph Mallon committed
356
357
	ir_node **const in = ALLOCAN(ir_node*, n_cfgpreds);
	for (int i = 0; i < n_cfgpreds; ++i)
358
		in[i] = new_r_Dummy(irg, mode);
359

360
361
	ir_node *const phi = mode == mode_M ? new_r_Phi_loop(block, n_cfgpreds, in)
	                                    : new_r_Phi(block, n_cfgpreds, in, mode);
362
363
	/* Important: always keep block phi list up to date. */
	add_Block_phi(block, phi);
Christian Helmer's avatar
Christian Helmer committed
364
	DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block));
365
	set_irn_link(block, phi);
366
367
368
	mark_irn_visited(block);

	/* set Phi predecessors */
Christoph Mallon's avatar
Christoph Mallon committed
369
370
	for (int i = 0; i < n_cfgpreds; ++i) {
		ir_node *const pred_block = get_Block_cfgpred_block(block, i);
371
		assert(pred_block != NULL);
Christoph Mallon's avatar
Christoph Mallon committed
372
		ir_node *const pred_val = search_def_and_create_phis(pred_block, mode, 0);
373

374
375
		assert(pred_val != NULL);

Christian Helmer's avatar
Christian Helmer committed
376
		DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val));
377
378
		set_irn_n(phi, i, pred_val);
	}
379

380
381
382
	return phi;
}

383

384
385
386
387
388
/**
 * Given a set of values this function constructs SSA-form for the users of the
 * first value (the users are determined through the out-edges of the value).
 * Works without using the dominance tree.
 */
Christoph Mallon's avatar
Christoph Mallon committed
389
static void construct_ssa(ir_node *const orig_block, ir_node *const orig_val, ir_node *const second_block, ir_node *const second_val)
390
391
{
	assert(orig_block && orig_val && second_block && second_val &&
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
392
	       "no parameter of construct_ssa may be NULL");
393
394
395
396

	if (orig_val == second_val)
		return;

Christoph Mallon's avatar
Christoph Mallon committed
397
	ir_graph *const irg = get_irn_irg(orig_val);
398
399
400
401
402
403
404
405
406
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
	inc_irg_visited(irg);

	set_irn_link(orig_block, orig_val);
	mark_irn_visited(orig_block);

	ssa_second_def_block = second_block;
	ssa_second_def       = second_val;

407
	/* Only fix the users of the first, i.e. the original node */
Christoph Mallon's avatar
Christoph Mallon committed
408
	ir_mode *const mode = get_irn_mode(orig_val);
409
	foreach_out_edge_safe(orig_val, edge) {
Christoph Mallon's avatar
Christoph Mallon committed
410
		ir_node *const user = get_edge_src_irn(edge);
411

Christoph Mallon's avatar
Christoph Mallon committed
412
		/* Ignore keeps. */
413
414
415
		if (is_End(user))
			continue;

416
		DB((dbg, LEVEL_5, "original user %N\n", user));
417

Christoph Mallon's avatar
Christoph Mallon committed
418
419
420
		ir_node       *newval;
		ir_node *const user_block = get_nodes_block(user);
		int      const j          = get_edge_src_pos(edge);
421
422
423
		if (is_Phi(user)) {
			ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
			newval = search_def_and_create_phis(pred_block, mode, 1);
424
425
426
		} else {
			newval = search_def_and_create_phis(user_block, mode, 1);
		}
427
428
		if (newval != user && !is_Bad(newval))
			set_irn_n(user, j, newval);
429
430
431
432
433
434
	}

	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
}


435
/***** Unrolling Helper Functions *****/
436

437
/* Assign the copy with index nr to node n */
Christoph Mallon's avatar
Christoph Mallon committed
438
static void set_unroll_copy(ir_node *const n, int const nr, ir_node *const cp)
439
440
{
	assert(nr != 0 && "0 reserved");
441

Christoph Mallon's avatar
Christoph Mallon committed
442
443
	unrolling_node_info *info = ir_nodemap_get(unrolling_node_info, &map, n);
	if (!info) {
444
		info = OALLOCZ(&obst, unrolling_node_info);
Christoph Mallon's avatar
Christoph Mallon committed
445
		info->copies = NEW_ARR_DZ(ir_node*, &obst, unroll_nr);
446
		ir_nodemap_insert(&map, n, info);
447
448
	}
	/* Original node */
Christoph Mallon's avatar
Christoph Mallon committed
449
	info->copies[0]  = n;
450
451
	info->copies[nr] = cp;
}
452

453
/* Returns a nodes copy if it exists, else NULL. */
Christoph Mallon's avatar
Christoph Mallon committed
454
static ir_node *get_unroll_copy(ir_node *const n, int const nr)
455
{
456
	unrolling_node_info *info = ir_nodemap_get(unrolling_node_info, &map, n);
Christoph Mallon's avatar
Christoph Mallon committed
457
	if (!info)
458
		return NULL;
459

Christoph Mallon's avatar
Christoph Mallon committed
460
	return info->copies[nr];
461
}
462
463


464
/***** Inversion Helper Functions *****/
465

466
/* Sets copy cp of node n. */
Christoph Mallon's avatar
Christoph Mallon committed
467
static void set_inversion_copy(ir_node *const n, ir_node *const cp)
468
{
469
	ir_nodemap_insert(&map, n, cp);
470
}
471

472
/* Getter of copy of n for inversion */
Christoph Mallon's avatar
Christoph Mallon committed
473
static ir_node *get_inversion_copy(ir_node *const n)
474
{
Christoph Mallon's avatar
Christoph Mallon committed
475
	return ir_nodemap_get(ir_node, &map, n);
476
477
}

478
/* Resets block mark for given node. For use with walker */
Christoph Mallon's avatar
Christoph Mallon committed
479
static void reset_block_mark(ir_node *const node, void *const env)
480
{
Christoph Mallon's avatar
Christoph Mallon committed
481
	(void)env;
482

483
484
485
	if (is_Block(node))
		set_Block_mark(node, 0);
}
486

487
488
/* Returns mark of node, or its block if node is not a block.
 * Used in this context to determine if node is in the condition chain. */
Christoph Mallon's avatar
Christoph Mallon committed
489
static bool is_nodes_block_marked(const ir_node *const node)
490
{
Matthias Braun's avatar
Matthias Braun committed
491
	return get_Block_mark(get_block_const(node));
492
}
493

494
495
/* Extends a nodes ins by node new.
 * NOTE: This is slow if a node n needs to be extended more than once. */
Christoph Mallon's avatar
Christoph Mallon committed
496
static void extend_irn(ir_node *const n, ir_node *const newnode, bool const new_is_backedge)
497
{
Christoph Mallon's avatar
Christoph Mallon committed
498
499
500
501
	int       const arity     = get_irn_arity(n);
	int       const new_arity = arity + 1;
	ir_node **const ins       = XMALLOCN(ir_node*, new_arity);
	bool     *const bes       = XMALLOCN(bool,     new_arity);
502

503
504
505
506
507
508
	/* save bes */
	/* Bes are important!
	 * Another way would be recreating the looptree,
	 * but after that we cannot distinguish already processed loops
	 * from not yet processed ones. */
	if (is_Block(n)) {
Christoph Mallon's avatar
Christoph Mallon committed
509
		for (int i = 0; i < arity; ++i) {
510
511
			bes[i] = is_backedge(n, i);
		}
Christoph Mallon's avatar
Christoph Mallon committed
512
		bes[arity] = new_is_backedge;
513
514
	}

Christoph Mallon's avatar
Christoph Mallon committed
515
	for (int i = 0; i < arity; ++i) {
516
		ins[i] = get_irn_n(n, i);
517
	}
Christoph Mallon's avatar
Christoph Mallon committed
518
	ins[arity] = newnode;
519

520
	set_irn_in(n, new_arity, ins);
521
522
523

	/* restore bes  */
	if (is_Block(n)) {
Christoph Mallon's avatar
Christoph Mallon committed
524
		for (int i = 0; i < new_arity; ++i) {
525
526
527
528
			if (bes[i])
				set_backedge(n, i);
		}
	}
Matthias Braun's avatar
Matthias Braun committed
529
530
	free(ins);
	free(bes);
531
}
532

533
534
/* Extends a block by a copy of its pred at pos,
 * fixing also the phis in the same way. */
Christoph Mallon's avatar
Christoph Mallon committed
535
static void extend_ins_by_copy(ir_node *const block, int const pos)
536
537
{
	/* Extend block by copy of definition at pos */
Christoph Mallon's avatar
Christoph Mallon committed
538
539
	ir_node *const pred   = get_Block_cfgpred(block, pos);
	ir_node *const new_in = get_inversion_copy(pred);
540
	DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred));
Matthias Braun's avatar
Matthias Braun committed
541
	extend_irn(block, new_in, false);
542

543
544
	/* Extend block phis by copy of definition at pos */
	for_each_phi(block, phi) {
Christoph Mallon's avatar
Christoph Mallon committed
545
546
		ir_node *const pred = get_Phi_pred(phi, pos);
		ir_node *const cp   = get_inversion_copy(pred);
547
548
		/* If the phis in is not in the condition chain (eg. a constant),
		 * there is no copy. */
Christoph Mallon's avatar
Christoph Mallon committed
549
		ir_node *const new_phi_in = cp ? cp : pred;
550

551
		DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred));
Christoph Mallon's avatar
Christoph Mallon committed
552
		extend_irn(phi, new_phi_in, false);
553
554
555
	}
}

556
/* Returns the number of blocks backedges. With or without alien bes. */
Christoph Mallon's avatar
Christoph Mallon committed
557
static int get_backedge_n(ir_node *const block, bool const with_alien)
558
{
559
560
561
562
	int       be_n  = 0;
	int const arity = get_Block_n_cfgpreds(block);
	for (int i = 0; i < arity; ++i) {
		ir_node *const pred = get_Block_cfgpred(block, i);
563
		if (is_backedge(block, i) && (with_alien || is_in_loop(pred)))
564
565
566
567
568
			++be_n;
	}
	return be_n;
}

569
570
/* Returns a raw copy of the given node.
 * Attributes are kept/set according to the needs of loop inversion. */
Christoph Mallon's avatar
Christoph Mallon committed
571
static ir_node *copy_node(ir_node *const node)
Christian Helmer's avatar
Christian Helmer committed
572
{
Christoph Mallon's avatar
Christoph Mallon committed
573
574
	ir_node *const cp    = exact_copy(node);
	int      const arity = get_irn_arity(node);
575

576
	/* Keep backedge info */
Christoph Mallon's avatar
Christoph Mallon committed
577
	for (int i = 0; i < arity; ++i) {
578
579
580
581
		if (is_backedge(node, i))
			set_backedge(cp, i);
	}

Christoph Mallon's avatar
Christoph Mallon committed
582
	if (is_Block(cp))
583
		set_Block_mark(cp, 0);
584

Christian Helmer's avatar
Christian Helmer committed
585
586
	return cp;
}
587

588

589
/**
590
 * This walker copies all walked nodes.
591
 * If the walk_condition is true for a node, it is copied.
592
593
 * All nodes node_info->copy have to be NULL prior to every walk.
 * Order of ins is important for later usage.
594
 */
Christoph Mallon's avatar
Christoph Mallon committed
595
static void copy_walk(ir_node *const node, walker_condition *const walk_condition, ir_loop *const set_loop)
596
597
598
599
{
	/**
	 * break condition and cycle resolver, creating temporary node copies
	 */
600
	if (irn_visited(node)) {
601
		/* Here we rely on nodestate's copy being initialized with NULL */
Christian Helmer's avatar
Christian Helmer committed
602
		DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
603
		if (get_inversion_copy(node) == NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
604
			ir_node *const cp = copy_node(node);
605
606
			set_inversion_copy(node, cp);

Christian Helmer's avatar
Christian Helmer committed
607
			DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp));
608
609
610
611
		}
		return;
	}

612
613
614
615
	/* Walk */
	mark_irn_visited(node);

	if (!is_Block(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
616
		ir_node *const pred = get_nodes_block(node);
617
		if (walk_condition(pred))
Christian Helmer's avatar
Christian Helmer committed
618
			DB((dbg, LEVEL_5, "walk block %N\n", pred));
619
		copy_walk(pred, walk_condition, set_loop);
620
621
	}

Christoph Mallon's avatar
Christoph Mallon committed
622
623
	int       const arity = get_irn_arity(node);
	ir_node **const cpin  = ALLOCAN(ir_node*, arity);
624

625
	foreach_irn_in(node, i, pred) {
626
		if (walk_condition(pred)) {
Christian Helmer's avatar
Christian Helmer committed
627
			DB((dbg, LEVEL_5, "walk node %N\n", pred));
628
			copy_walk(pred, walk_condition, set_loop);
629
			cpin[i] = get_inversion_copy(pred);
Christian Helmer's avatar
Christian Helmer committed
630
			DB((dbg, LEVEL_5, "copy of %N gets new in %N which is copy of %N\n",
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
631
			    node, get_inversion_copy(pred), pred));
632
633
634
635
636
		} else {
			cpin[i] = pred;
		}
	}

637
	/* copy node / finalize temp node */
Christoph Mallon's avatar
Christoph Mallon committed
638
	ir_node *cp;
639
	if (get_inversion_copy(node) == NULL) {
640
		/* No temporary copy existent */
641
642
		cp = copy_node(node);
		set_inversion_copy(node, cp);
Christian Helmer's avatar
Christian Helmer committed
643
		DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
644
645
	} else {
		/* temporary copy is existent but without correct ins */
646
		cp = get_inversion_copy(node);
Christian Helmer's avatar
Christian Helmer committed
647
		DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
648
649
	}

650
	if (!is_Block(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
651
652
		ir_node *const cpblock = get_inversion_copy(get_nodes_block(node));
		set_nodes_block(cp, cpblock);
Christian Helmer's avatar
Christian Helmer committed
653
		if (is_Phi(cp))
654
655
656
			add_Block_phi(cpblock, cp);
	}

657
	/* Keeps phi list of temporary node. */
658
	set_irn_in(cp, arity, cpin);
659
660
}

661
/**
662
663
664
665
666
 * This walker copies all walked nodes.
 * If the walk_condition is true for a node, it is copied.
 * All nodes node_info->copy have to be NULL prior to every walk.
 * Order of ins is important for later usage.
 * Takes copy_index, to phase-link copy at specific index.
667
 */
Christoph Mallon's avatar
Christoph Mallon committed
668
static void copy_walk_n(ir_node *const node, walker_condition *const walk_condition, int const copy_index)
669
{
Christoph Mallon's avatar
Christoph Mallon committed
670
	/* break condition and cycle resolver, creating temporary node copies */
671
	if (irn_visited(node)) {
672
673
674
		/* Here we rely on nodestate's copy being initialized with NULL */
		DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node));
		if (get_unroll_copy(node, copy_index) == NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
675
			ir_node *const u = copy_node(node);
676
677
			set_unroll_copy(node, copy_index, u);
			DB((dbg, LEVEL_5, "The TEMP unknown of %N is created %N\n", node, u));
678
		}
679
		return;
680
	}
681

682
683
	/* Walk */
	mark_irn_visited(node);
684

685
	if (!is_Block(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
686
		ir_node *const block = get_nodes_block(node);
687
688
689
		if (walk_condition(block))
			DB((dbg, LEVEL_5, "walk block %N\n", block));
		copy_walk_n(block, walk_condition, copy_index);
690
691
	}

Christoph Mallon's avatar
Christoph Mallon committed
692
693
	int       const arity = get_irn_arity(node);
	ir_node **const cpin  = ALLOCAN(ir_node*, arity);
694

695
	foreach_irn_in(node, i, pred) {
696
697
698
699
700
701
		if (walk_condition(pred)) {
			DB((dbg, LEVEL_5, "walk node %N\n", pred));
			copy_walk_n(pred, walk_condition, copy_index);
			cpin[i] = get_unroll_copy(pred, copy_index);
		} else {
			cpin[i] = pred;
702
703
		}
	}
704

705
	/* copy node / finalize temp node */
Christoph Mallon's avatar
Christoph Mallon committed
706
	ir_node *cp = get_unroll_copy(node, copy_index);
707
708
709
710
711
712
713
714
	if (cp == NULL || is_Unknown(cp)) {
		cp = copy_node(node);
		set_unroll_copy(node, copy_index, cp);
		DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp));
	} else {
		/* temporary copy is existent but without correct ins */
		cp = get_unroll_copy(node, copy_index);
		DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp));
715
716
	}

717
	if (!is_Block(node)) {
Christoph Mallon's avatar
Christoph Mallon committed
718
719
720
		ir_node *const block   = get_nodes_block(node);
		ir_node *const cpblock = get_unroll_copy(block, copy_index);
		set_nodes_block(cp, cpblock);
721
722
		if (is_Phi(cp))
			add_Block_phi(cpblock, cp);
723
	}
724

725
	/* Keeps phi list of temporary node. */
726
	set_irn_in(cp, arity, cpin);
727
}
728

sebastian.buchwald1's avatar
sebastian.buchwald1 committed
729
/* Removes all Blocks with non marked predecessors from the condition chain. */
730
731
static void unmark_not_allowed_cc_blocks(void)
{
Christoph Mallon's avatar
Christoph Mallon committed
732
733
734
	size_t const blocks = ARR_LEN(cc_blocks);
	for (size_t i = 0; i < blocks; ++i) {
		ir_node *const block = cc_blocks[i];
735
736

		/* Head is an exception. */
737
738
739
		if (block == loop_head)
			continue;

740
741
742
		int const arity = get_Block_n_cfgpreds(block);
		for (int a = 0; a < arity; ++a) {
			if (!is_nodes_block_marked(get_Block_cfgpred(block, a))) {
743
744
745
				set_Block_mark(block, 0);
				--inversion_blocks_in_cc;
				DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n",
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
746
				    block, inversion_blocks_in_cc));
747
748

				break;
749
750
751
752
753
			}
		}
	}
}

754
755
/* Unmarks all cc blocks using cc_blocks except head.
 * TODO: invert head for unrolling? */
756
757
static void unmark_cc_blocks(void)
{
Christoph Mallon's avatar
Christoph Mallon committed
758
759
760
	size_t const blocks = ARR_LEN(cc_blocks);
	for (size_t i = 0; i < blocks; ++i) {
		ir_node *const block = cc_blocks[i];
761

762
763
764
		/* TODO Head is an exception. */
		/*if (block != loop_head)*/
		set_Block_mark(block, 0);
765
	}
766
767
	/*inversion_blocks_in_cc = 1;*/
	inversion_blocks_in_cc = 0;
768
769
770
771
772

	/* invalidate */
	loop_info.cc_size = 0;
}

773
/**
774
 * Populates head_entries with (node, pred_pos) tuple
775
776
777
 * whereas the node's pred at pred_pos is in the cc but not the node itself.
 * Also finds df loops inside the cc.
 * Head and condition chain blocks have been marked previously.
778
 */
Christoph Mallon's avatar
Christoph Mallon committed
779
static void get_head_outs(ir_node *const node, void *const env)
780
{
Christoph Mallon's avatar
Christoph Mallon committed
781
	(void)env;
782

783
784
	foreach_irn_in(node, i, pred) {
		if (!is_nodes_block_marked(node) && is_nodes_block_marked(pred)) {
785
786
787
			/* Saving also predecessor seems redundant, but becomes
			 * necessary when changing position of it, before
			 * dereferencing it.*/
Christoph Mallon's avatar
Christoph Mallon committed
788
			entry_edge const entry = { .node = node, .pos = i, .pred = pred };
789
			ARR_APP1(entry_edge, cur_head_outs, entry);
790
791
792
		}
	}

793
	/* Find df loops inside the cc */
794
	if (is_Phi(node) && get_nodes_block(node) == loop_head) {
795
796
		foreach_irn_in(loop_head, i, pred) {
			if (is_own_backedge(loop_head, i) && is_nodes_block_marked(pred)) {
Christoph Mallon's avatar
Christoph Mallon committed
797
				entry_edge const entry = { .node = node, .pos = i, .pred = pred };
798
799
				ARR_APP1(entry_edge, head_df_loop, entry);
				DB((dbg, LEVEL_5, "Found incc assignment node %N @%d is pred %N, graph %N %N\n",
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
800
				    node, i, entry.pred, get_irn_irg(node), get_irg_start_block(get_irn_irg(node))));
801
			}
802
803
804
		}
	}
}
805

806
/**
807
 * Find condition chains, and add them to be inverted.
808
 * A block belongs to the chain if a condition branches out of the loop.
809
 * (Some blocks need to be removed once again.)
810
 * Returns 1 if the given block belongs to the condition chain.
811
 */
Christoph Mallon's avatar
Christoph Mallon committed
812
static void find_condition_chain(ir_node *const block)
813
{
814
	mark_irn_visited(block);
815

816
	DB((dbg, LEVEL_5, "condition_chains for block %N\n", block));
817

818
	/* Get node count */
Christoph Mallon's avatar
Christoph Mallon committed
819
	unsigned nodes_n = 0;
820
	foreach_out_edge(block, edge) {
821
822
823
824
825
826
827
828
829
		++nodes_n;
	}

	/* Check if node count would exceed maximum cc size.
	 * TODO
	 * This is not optimal, as we search depth-first and break here,
	 * continuing with another subtree. */
	if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) {
		set_Block_mark(block, 0);
830
		return;
831
832
833
	}

	/* Check if block only has a jmp instruction. */
Christoph Mallon's avatar
Christoph Mallon committed
834
	bool jmp_only = true;
835
	foreach_out_edge(block, edge) {
Christoph Mallon's avatar
Christoph Mallon committed
836
		ir_node *const src = get_edge_src_irn(edge);
Matthias Braun's avatar
Matthias Braun committed
837
838
		if (!is_Block(src) && !is_Jmp(src)) {
			jmp_only = false;
Christoph Mallon's avatar
Christoph Mallon committed
839
			break;
840
		}
841
	}
Christian Helmer's avatar