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
23
#include "irdom.h"
#include "iredges.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
28
29
30
#include "irloop_t.h"
#include "irnode.h"
#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 */
Matthias Braun's avatar
Matthias Braun committed
266
267
268
			foreach_out_edge_kind(node, edge, EDGE_KIND_BLOCK) {
				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
279
280
281
					++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",
								node, pred));
					/* 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

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

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

373
374
		assert(pred_val != NULL);

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

379
380
381
	return phi;
}

382

383
384
385
386
387
/**
 * 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
388
static void construct_ssa(ir_node *const orig_block, ir_node *const orig_val, ir_node *const second_block, ir_node *const second_val)
389
390
391
392
393
394
395
{
	assert(orig_block && orig_val && second_block && second_val &&
			"no parameter of construct_ssa may be NULL");

	if (orig_val == second_val)
		return;

Christoph Mallon's avatar
Christoph Mallon committed
396
	ir_graph *const irg = get_irn_irg(orig_val);
397
398
399
400
401
402
403
404
405
	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;

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

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

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

Christoph Mallon's avatar
Christoph Mallon committed
417
418
419
		ir_node       *newval;
		ir_node *const user_block = get_nodes_block(user);
		int      const j          = get_edge_src_pos(edge);
420
421
422
		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);
423
424
425
		} else {
			newval = search_def_and_create_phis(user_block, mode, 1);
		}
426
427
		if (newval != user && !is_Bad(newval))
			set_irn_n(user, j, newval);
428
429
430
431
432
433
	}

	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
}


434
/***** Unrolling Helper Functions *****/
435

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

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

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

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


463
/***** Inversion Helper Functions *****/
464

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

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

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

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

486
487
/* 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
488
static bool is_nodes_block_marked(const ir_node *const node)
489
{
Matthias Braun's avatar
Matthias Braun committed
490
	return get_Block_mark(get_block_const(node));
491
}
492

493
494
/* 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
495
static void extend_irn(ir_node *const n, ir_node *const newnode, bool const new_is_backedge)
496
{
Christoph Mallon's avatar
Christoph Mallon committed
497
498
499
500
	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);
501

502
503
504
505
506
507
	/* 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
508
		for (int i = 0; i < arity; ++i) {
509
510
			bes[i] = is_backedge(n, i);
		}
Christoph Mallon's avatar
Christoph Mallon committed
511
		bes[arity] = new_is_backedge;
512
513
	}

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

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

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

532
533
/* 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
534
static void extend_ins_by_copy(ir_node *const block, int const pos)
535
536
{
	/* Extend block by copy of definition at pos */
Christoph Mallon's avatar
Christoph Mallon committed
537
538
	ir_node *const pred   = get_Block_cfgpred(block, pos);
	ir_node *const new_in = get_inversion_copy(pred);
539
	DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred));
Matthias Braun's avatar
Matthias Braun committed
540
	extend_irn(block, new_in, false);
541

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

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

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

568
569
/* 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
570
static ir_node *copy_node(ir_node *const node)
Christian Helmer's avatar
Christian Helmer committed
571
{
Christoph Mallon's avatar
Christoph Mallon committed
572
573
	ir_node *const cp    = exact_copy(node);
	int      const arity = get_irn_arity(node);
574

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

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

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

587

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

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

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

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

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

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

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

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

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

660
/**
661
662
663
664
665
 * 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.
666
 */
Christoph Mallon's avatar
Christoph Mallon committed
667
static void copy_walk_n(ir_node *const node, walker_condition *const walk_condition, int const copy_index)
668
{
Christoph Mallon's avatar
Christoph Mallon committed
669
	/* break condition and cycle resolver, creating temporary node copies */
670
	if (irn_visited(node)) {
671
672
673
		/* 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
674
			ir_node *const u = copy_node(node);
675
676
			set_unroll_copy(node, copy_index, u);
			DB((dbg, LEVEL_5, "The TEMP unknown of %N is created %N\n", node, u));
677
		}
678
		return;
679
	}
680

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

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

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

694
	foreach_irn_in(node, i, pred) {
695
696
697
698
699
700
		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;
701
702
		}
	}
703

704
	/* copy node / finalize temp node */
Christoph Mallon's avatar
Christoph Mallon committed
705
	ir_node *cp = get_unroll_copy(node, copy_index);
706
707
708
709
710
711
712
713
	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));
714
715
	}

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

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

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

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

739
740
741
		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))) {
742
743
744
745
746
747
				set_Block_mark(block, 0);
				--inversion_blocks_in_cc;
				DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n",
						block, inversion_blocks_in_cc));

				break;
748
749
750
751
752
			}
		}
	}
}

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

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

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

772
/**
773
 * Populates head_entries with (node, pred_pos) tuple
774
775
776
 * 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.
777
 */
Christoph Mallon's avatar
Christoph Mallon committed
778
static void get_head_outs(ir_node *const node, void *const env)
779
{
Christoph Mallon's avatar
Christoph Mallon committed
780
	(void)env;
781

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

792
	/* Find df loops inside the cc */
793
	if (is_Phi(node) && get_nodes_block(node) == loop_head) {
794
795
		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
796
				entry_edge const entry = { .node = node, .pos = i, .pred = pred };
797
798
				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",
799
						node, i, entry.pred, get_irn_irg(node), get_irg_start_block(get_irn_irg(node))));
800
			}
801
802
803
		}
	}
}
804

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

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

817
	/* Get node count */
Christoph Mallon's avatar
Christoph Mallon committed
818
	unsigned nodes_n = 0;
819
820
821
822
823
824
825
826
827
828
	foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) {
		++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);
829
		return;
830
831
832
	}

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