iroptimize.h 35.1 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
22
 * @brief   Available Optimisations of libFirm.
23
 * @version $Id$
24
25
26
27
28
 */
#ifndef FIRM_IROPTIMIZE_H
#define FIRM_IROPTIMIZE_H

#include "firm_types.h"
29
#include "nodeops.h"
30
#include "begin.h"
31
32
33
34
35
36
37
38
39
40

/**
 * Control flow optimization.
 *
 * Removes empty blocks doing if simplifications and loop simplifications.
 * A block is empty if it contains only a Jmp node and Phi nodes.
 * Merges single entry single exit blocks with their predecessor
 * and propagates dead control flow by calling equivalent_node().
 * Independent of compiler flag it removes Tuples from cf edges,
 * Bad predecessors from Blocks and Phis, and unnecessary predecessors of End.
41
 * Destroys backedge information.
42
43
44
45
46
 *
 * @bug Chokes on Id nodes if called in a certain order with other
 *      optimizations.  Call local_optimize_graph() before to remove
 *      Ids.
 */
Michael Beck's avatar
Michael Beck committed
47
FIRM_API void optimize_cf(ir_graph *irg);
48

49
50
51
52
53
54
55
/**
 * Creates an ir_graph pass for optimize_cf().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
56
FIRM_API ir_graph_pass_t *optimize_cf_pass(const char *name);
57

58
/**
59
 * Perform path-sensitive jump threading on the given graph.
60
61
62
 *
 * @param irg  the graph
 */
Michael Beck's avatar
Michael Beck committed
63
FIRM_API void opt_jumpthreading(ir_graph* irg);
64

65
66
67
68
69
70
71
/**
 * Creates an ir_graph pass for opt_jumpthreading().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
72
FIRM_API ir_graph_pass_t *opt_jumpthreading_pass(const char *name);
73

74
75
76
77
78
79
/**
 * Try to simplify boolean expression in the given ir graph.
 * eg. x < 5 && x < 6 becomes x < 5
 *
 * @param irg  the graph
 */
Michael Beck's avatar
Michael Beck committed
80
FIRM_API void opt_bool(ir_graph *irg);
81

82
83
84
85
86
87
88
/**
 * Creates an ir_graph pass for opt_bool().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
89
FIRM_API ir_graph_pass_t *opt_bool_pass(const char *name);
90

91
92
93
94
/**
 * Try to reduce the number of conv nodes in the given ir graph.
 *
 * @param irg  the graph
95
96
 *
 * @return non-zero if the optimization could be applied, 0 else
97
 */
Michael Beck's avatar
Michael Beck committed
98
FIRM_API int conv_opt(ir_graph *irg);
99

100
101
102
103
104
105
106
/**
 * Creates an ir_graph pass for conv_opt().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
107
FIRM_API ir_graph_pass_t *conv_opt_pass(const char *name);
108

109
110
111
112
113
114
115
116
117
118
119
120
121
/**
 * A callback that checks whether a entity is an allocation
 * routine.
 */
typedef int (*check_alloc_entity_func)(ir_entity *ent);

/**
 * Do simple and fast escape analysis for one graph.
 *
 * @param irg       the graph
 * @param callback  a callback function to check whether a
 *                  given entity is a allocation call
 */
Michael Beck's avatar
Michael Beck committed
122
FIRM_API void escape_enalysis_irg(ir_graph *irg,
123
                                  check_alloc_entity_func callback);
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

/**
 * Do simple and fast escape analysis for all graphs.
 *
 * This optimization implements a simple and fast but inexact
 * escape analysis. Some addresses might be marked as 'escaped' even
 * if they are not.
 * The advantage is a low memory footprint and fast speed.
 *
 * @param run_scalar_replace  if this flag in non-zero, scalar
 *                            replacement optimization is run on graphs with removed
 *                            allocation
 * @param callback            a callback function to check whether a
 *                            given entity is a allocation call
 *
 * This optimization removes allocation which are not used (rare) and replace
 * allocation that can be proved dead at the end of the graph which stack variables.
 *
 * The creation of stack variable allows scalar replacement to be run only
 * on those graphs that have been changed.
 *
 * This is most effective on Java where no other stack variables exists.
 */
Michael Beck's avatar
Michael Beck committed
147
FIRM_API void escape_analysis(int run_scalar_replace,
148
                              check_alloc_entity_func callback);
149
150
151
152
153
154
155
156
157
158
159
160
161
162

/**
 * Optimize function calls by handling const functions.
 *
 * This optimization first detects all "const functions", i.e.,
 * IR graphs that neither read nor write memory (and hence did
 * not create exceptions, as these use memory in Firm).
 *
 * The result of calls to such functions depends only on its
 * arguments, hence those calls are no more pinned.
 *
 * This is a rather strong criteria, so do not expect that a
 * lot of functions will be found. Moreover, all of them might
 * already be inlined if inlining is activated.
163
 * Anyway, it might be good for handling builtin's
164
165
166
167
168
169
170
171
172
173
174
175
 * even if the later read/write memory (but we know how).
 *
 * This optimizations read the irg_const_function property of
 * entities and and sets the irg_const_function property of
 * graphs.
 *
 * If callee information is valid, we also optimize polymorphic Calls.
 *
 * @param force_run  if non-zero, an optimization run is started even
 *                   if no const function graph was detected.
 *                   Else calls are only optimized if at least one
 *                   const function graph was detected.
176
177
 * @param callback   a callback function to check whether a
 *                   given entity is a allocation call
178
 *
179
 * If the frontend created external entities with the irg_const_function
180
181
182
183
184
 * property set, the force_run parameter should be set, else
 * should be unset.
 *
 * @note This optimization destroys the link fields of nodes.
 */
Michael Beck's avatar
Michael Beck committed
185
FIRM_API void optimize_funccalls(int force_run,
186
                                 check_alloc_entity_func callback);
187

188
189
190
191
192
193
194
195
196
197
198
199
200
/**
 * Creates an ir_prog pass for optimize_funccalls().
 *
 * @param name       the name of this pass or NULL
 * @param force_run  if non-zero, an optimization run is started even
 *                   if no const function graph was detected.
 *                   Else calls are only optimized if at least one
 *                   const function graph was detected.
 * @param callback   a callback function to check whether a
 *                   given entity is a allocation call
 *
 * @return  the newly created ir_prog pass
 */
Michael Beck's avatar
Michael Beck committed
201
FIRM_API ir_prog_pass_t *optimize_funccalls_pass(const char *name,
202
203
                                                 int force_run,
                                                 check_alloc_entity_func callback);
204

205
206
207
208
209
210
211
212
213
/**
 * Does Partial Redundancy Elimination combined with
 * Global Value Numbering.
 * Can be used to replace place_code() completely.
 *
 * Based on VanDrunen and Hosking 2004.
 *
 * @param irg  the graph
 */
Michael Beck's avatar
Michael Beck committed
214
FIRM_API void do_gvn_pre(ir_graph *irg);
215

216
217
218
/**
 * Creates an ir_graph pass for do_gvn_pre().
 *
219
 * @param name     the name of this pass or NULL
220
221
222
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
223
FIRM_API ir_graph_pass_t *do_gvn_pre_pass(const char *name);
224

225
/**
226
227
228
 * This function is called to evaluate, if a
 * mux(@p sel, @p mux_false, @p mux_true) should be built for the current
 * architecture.
229
230
231
 * If it returns non-zero, a mux is created, else the code
 * is not modified.
 * @param sel        A selector of a Cond.
232
 * @param phi_list   phi node to be converted
233
234
235
 * @param i          First data predecessor involved in if conversion
 * @param j          Second data predecessor involved in if conversion
 */
236
237
typedef int (*arch_allow_ifconv_func)(ir_node *sel, ir_node *mux_false,
                                      ir_node *mux_true);
238
239
240
241
242
243
244
245
246

/**
 * Perform If conversion on a graph.
 *
 * @param irg The graph.
 *
 * Cannot handle blocks with Bad control predecessors, so call it after control
 * flow optimization.
 */
247
FIRM_API void opt_if_conv(ir_graph *irg);
248

249
250
251
252
253
254
255
/**
 * Creates an ir_graph pass for opt_if_conv().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
256
FIRM_API ir_graph_pass_t *opt_if_conv_pass(const char *name);
257

258
/**
259
260
261
 * Tries to reduce dependencies for memory nodes where possible by parallelizing
 * them and synchronizing with Sync nodes
 * @param irg   the graph where memory operations should be parallelized
262
 */
Michael Beck's avatar
Michael Beck committed
263
FIRM_API void opt_parallelize_mem(ir_graph *irg);
264

Michael Beck's avatar
Michael Beck committed
265
266
267
268
269
270
271
/**
 * Creates an ir_graph pass for opt_sync().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
272
FIRM_API ir_graph_pass_t *opt_parallelize_mem_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
273

Michael Beck's avatar
Michael Beck committed
274
275
276
277
278
279
280
281
282
283
284
/*
 * Check if we can replace the load by a given const from
 * the const code irg.
 *
 * @param load   the load to replace
 * @param c      the constant
 *
 * @return in the modes match or can be transformed using a reinterpret cast
 *         returns a copy of the constant (possibly Conv'ed) on the
 *         current_ir_graph
 */
Michael Beck's avatar
Michael Beck committed
285
FIRM_API ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c);
Michael Beck's avatar
Michael Beck committed
286

287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
/**
 * Load/Store optimization.
 *
 * Removes redundant non-volatile Loads and Stores.
 * May introduce Bad nodes if exceptional control flow
 * is removed. The following cases are optimized:
 *
 * Load without result: A Load which has only a memory use
 *   is removed.
 *
 * Load after Store: A Load after a Store is removed, if
 *   the Load doesn't have an exception handler OR is in
 *   the same block as the Store.
 *
 * Load after Load: A Load after a Load is removed, if the
 *   Load doesn't have an exception handler OR is in the
 *   same block as the previous Load.
 *
 * Store before Store: A Store immediately before another
 *   Store in the same block is removed, if the Store doesn't
 *   have an exception handler.
 *
 * Store after Load: A Store after a Load is removed, if the
 *   Store doesn't have an exception handler.
311
312
 *
 * @return non-zero if the optimization could be applied, 0 else
313
 */
Michael Beck's avatar
Michael Beck committed
314
FIRM_API int optimize_load_store(ir_graph *irg);
315

Michael Beck's avatar
Michael Beck committed
316
317
318
319
320
321
322
/**
 * Creates an ir_graph pass for optimize_load_store().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
323
FIRM_API ir_graph_pass_t *optimize_load_store_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
324

325
326
327
328
329
/**
 * New experimental alternative to optimize_load_store.
 * Based on a dataflow analysis, so load/stores are moved out of loops
 * where possible
 */
Michael Beck's avatar
Michael Beck committed
330
FIRM_API int opt_ldst(ir_graph *irg);
331

Michael Beck's avatar
Michael Beck committed
332
333
334
335
336
337
338
/**
 * Creates an ir_graph pass for opt_ldst().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
339
FIRM_API ir_graph_pass_t *opt_ldst_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
340

341
/**
342
 * Optimize loops by peeling or unrolling them if beneficial.
Michael Beck's avatar
Michael Beck committed
343
 *
344
 * @param irg  The graph whose loops will be processed
Michael Beck's avatar
Michael Beck committed
345
 *
346
 * This function did not change the graph, only its frame type.
347
348
 * The layout state of the frame type will be set to layout_undefined
 * if entities were removed.
Michael Beck's avatar
Michael Beck committed
349
 */
Michael Beck's avatar
Michael Beck committed
350
FIRM_API void loop_optimization(ir_graph *irg);
Michael Beck's avatar
Michael Beck committed
351

352
353
354
355
356
357
/**
 * Optimize the frame type of an irg by removing
 * never touched entities.
 *
 * @param irg  The graph whose frame type will be optimized
 *
358
 * This function did not change the graph, only its frame type.
359
360
361
 * The layout state of the frame type will be set to layout_undefined
 * if entities were removed.
 */
Michael Beck's avatar
Michael Beck committed
362
FIRM_API void opt_frame_irg(ir_graph *irg);
363

Michael Beck's avatar
Michael Beck committed
364
365
366
367
368
369
370
/**
 * Creates an ir_graph pass for opt_frame_irg().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
371
FIRM_API ir_graph_pass_t *opt_frame_irg_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
372

373
374
375
376
377
/** Possible flags for the Operator Scalar Replacement. */
typedef enum osr_flags {
	osr_flag_none               = 0,  /**< no additional flags */
	osr_flag_lftr_with_ov_check = 1,  /**< do linear function test replacement
	                                       only if no overflow can occur. */
378
379
380
	osr_flag_ignore_x86_shift   = 2,  /**< ignore Multiplications by 2, 4, 8 */
	osr_flag_keep_reg_pressure  = 4   /**< do NOT increase register pressure by introducing new
	                                       induction variables. */
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
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
} osr_flags;

/* FirmJNI cannot handle identical enum values... */

/** default setting */
#define osr_flag_default osr_flag_lftr_with_ov_check

/**
 * Do the Operator Scalar Replacement optimization and linear
 * function test replacement for loop control.
 * Can be switched off using the set_opt_strength_red() flag.
 * In that case, only remove_phi_cycles() is executed.
 *
 * @param irg    the graph which should be optimized
 * @param flags  set of osr_flags
 *
 * The linear function replacement test is controlled by the flags.
 * If the osr_flag_lftr_with_ov_check is set, the replacement is only
 * done if do overflow can occur.
 * Otherwise it is ALWAYS done which might be insecure.
 *
 * For instance:
 *
 * for (i = 0; i < 100; ++i)
 *
 * might be replaced by
 *
 * for (i = 0; i < 400; i += 4)
 *
 * But
 *
 * for (i = 0; i < 0x7FFFFFFF; ++i)
 *
 * will not be replaced by
 *
 * for (i = 0; i < 0xFFFFFFFC; i += 4)
 *
 * because of overflow.
 *
 * More bad cases:
 *
 * for (i = 0; i <= 0xF; ++i)
 *
 * will NOT be transformed into
 *
 * for (i = 0xFFFFFFF0; i <= 0xFFFFFFFF; ++i)
 *
 * although here is no direct overflow. The OV occurs when the ++i
 * is executed (and would created an endless loop here!).
 *
 * For the same reason, a loop
 *
 * for (i = 0; i <= 9; i += x)
 *
 * will NOT be transformed because we cannot estimate whether an overflow
 * might happen adding x.
 *
 * Note that i < a + 400 is also not possible with the current implementation
 * although this might be allowed by other compilers...
 *
 * Note further that tests for equality can be handled some simpler (but are not
 * implemented yet).
 *
 * This algorithm destroys the link field of nodes.
 */
Michael Beck's avatar
Michael Beck committed
446
FIRM_API void opt_osr(ir_graph *irg, unsigned flags);
447

Michael Beck's avatar
Michael Beck committed
448
449
450
451
452
453
454
455
/**
 * Creates an ir_graph pass for remove_phi_cycles().
 *
 * @param name     the name of this pass or NULL
 * @param flags    set of osr_flags
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
456
FIRM_API ir_graph_pass_t *opt_osr_pass(const char *name, unsigned flags);
Michael Beck's avatar
Michael Beck committed
457

458
459
460
461
462
463
464
465
466
467
/**
 * Removes useless Phi cycles, i.e cycles of Phi nodes with only one
 * non-Phi node.
 * This is automatically done in opt_osr(), so there is no need to call it
 * additionally.
 *
 * @param irg    the graph which should be optimized
 *
 * This algorithm destroys the link field of nodes.
 */
Michael Beck's avatar
Michael Beck committed
468
FIRM_API void remove_phi_cycles(ir_graph *irg);
469

Michael Beck's avatar
Michael Beck committed
470
471
472
473
474
475
476
/**
 * Creates an ir_graph pass for remove_phi_cycles().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
477
FIRM_API ir_graph_pass_t *remove_phi_cycles_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
478
479


480
/** A default threshold. */
481
#define DEFAULT_CLONE_THRESHOLD 20
482
483
484
485
486
487
488
489
490
491
492
493

/**
 * Do procedure cloning. Evaluate a heuristic weight for every
 * Call(..., Const, ...). If the weight is bigger than threshold,
 * clone the entity and fix the calls.
 *
 * @param threshold   the threshold for cloning
 *
 * The threshold is an estimation of how many instructions are saved
 * when executing a cloned method. If threshold is 0.0, every possible
 * call is cloned.
 */
Michael Beck's avatar
Michael Beck committed
494
FIRM_API void proc_cloning(float threshold);
495

Michael Beck's avatar
Michael Beck committed
496
497
498
499
500
501
502
503
/**
 * Creates an ir_prog pass for proc_cloning().
 *
 * @param name        the name of this pass or NULL
 * @param threshold   the threshold for cloning
 *
 * @return  the newly created ir_prog pass
 */
Michael Beck's avatar
Michael Beck committed
504
FIRM_API ir_prog_pass_t *proc_cloning_pass(const char *name, float threshold);
Michael Beck's avatar
Michael Beck committed
505

506
507
508
509
510
511
512
513
/**
 * Reassociation.
 *
 * Applies Reassociation rules to integer expressions.
 * Beware: Works only if integer overflow might be ignored, as for C, Java
 * and for address expression.
 * Works only if Constant folding is activated.
 *
514
 * Uses loop information to detect loop-invariant (i.e. contant
515
516
517
518
519
 * inside the loop) values.
 *
 * See Muchnik 12.3.1 Algebraic Simplification and Reassociation of
 * Addressing Expressions.
 *
520
 * @return non-zero if the optimization could be applied, 0 else
521
 */
Michael Beck's avatar
Michael Beck committed
522
FIRM_API int optimize_reassociation(ir_graph *irg);
523

524
525
526
527
528
529
530
/**
 * Creates an ir_graph pass for optimize_reassociation().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
531
FIRM_API ir_graph_pass_t *optimize_reassociation_pass(const char *name);
532

533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
/**
 * Normalize the Returns of a graph by creating a new End block
 * with One Return(Phi).
 * This is the preferred input for the if-conversion.
 *
 * In pseudocode, it means:
 *
 * if (a)
 *   return b;
 * else
 *   return c;
 *
 * is transformed into
 *
 * if (a)
 *   res = b;
 * else
 *   res = c;
 * return res;
 */
Michael Beck's avatar
Michael Beck committed
553
FIRM_API void normalize_one_return(ir_graph *irg);
554

555
556
557
558
559
560
561
/**
 * Creates an ir_graph pass for normalize_one_return().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
562
FIRM_API ir_graph_pass_t *normalize_one_return_pass(const char *name);
563

564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
/**
 * Normalize the Returns of a graph by moving
 * the Returns upwards as much as possible.
 * This might be preferred for code generation.
 *
 * In pseudocode, it means:
 *
 * if (a)
 *   res = b;
 * else
 *   res = c;
 * return res;
 *
 * is transformed into
 *
 * if (a)
 *   return b;
 * else
 *   return c;
 */
Michael Beck's avatar
Michael Beck committed
584
FIRM_API void normalize_n_returns(ir_graph *irg);
585

586
587
588
589
590
591
592
/**
 * Creates an ir_graph pass for normalize_n_returns().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
593
FIRM_API ir_graph_pass_t *normalize_n_returns_pass(const char *name);
594

595
596
597
598
599
600
/**
 * Do the scalar replacement optimization.
 * Replace local compound entities (like structures and arrays)
 * with atomic values if possible. Does not handle classes yet.
 *
 * @param irg  the graph which should be optimized
601
602
 *
 * @return non-zero, if at least one entity was replaced
603
 */
Michael Beck's avatar
Michael Beck committed
604
FIRM_API int scalar_replacement_opt(ir_graph *irg);
605

606
607
608
609
610
611
612
/**
 * Creates an ir_graph pass for scalar_replacement_opt().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
613
FIRM_API ir_graph_pass_t *scalar_replacement_opt_pass(const char *name);
614

615
/**
616
617
618
619
620
621
622
623
 * Optimizes tail-recursion calls by converting them into loops.
 * Depends on the flag opt_tail_recursion.
 * Currently supports the following forms:
 *  - return func();
 *  - return x + func();
 *  - return func() - x;
 *  - return x * func();
 *  - return -func();
624
625
626
627
628
629
630
 *
 * Does not work for Calls that use the exception stuff.
 *
 * @param irg   the graph to be optimized
 *
 * @return non-zero if the optimization could be applied, 0 else
 */
Michael Beck's avatar
Michael Beck committed
631
FIRM_API int opt_tail_rec_irg(ir_graph *irg);
632

633
634
635
636
637
638
639
/**
 * Creates an ir_graph pass for opt_tail_rec_irg().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
640
FIRM_API ir_graph_pass_t *opt_tail_rec_irg_pass(const char *name);
641

642
/**
643
 * Optimize tail-recursion calls for all IR-Graphs.
644
645
646
647
648
649
650
651
 * Can currently handle:
 * - direct return value, i.e. return func().
 * - additive return value, i.e. return x +/- func()
 * - multiplicative return value, i.e. return x * func() or return -func()
 *
 * The current implementation must be run before optimize_funccalls(),
 * because it expects the memory edges pointing to calls, which might be
 * removed by optimize_funccalls().
652
 */
Michael Beck's avatar
Michael Beck committed
653
FIRM_API void opt_tail_recursion(void);
654

655
656
657
658
659
660
661
/**
 * Creates an ir_prog pass for opt_tail_recursion().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_prog pass
 */
Michael Beck's avatar
Michael Beck committed
662
FIRM_API ir_prog_pass_t *opt_tail_recursion_pass(const char *name);
663

664
665
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
/** This is the type for a method, that returns a pointer type to
 *  tp.  This is needed in the normalization. */
typedef ir_type *(*gen_pointer_type_to_func)(ir_type *tp);

/**  Insert Casts so that class type casts conform exactly with the type hierarchy.
 *
 *  Formulated in Java, this achieves the following:
 *
 *  For a class hierarchy
 *    class A {}
 *    class B extends A {}
 *    class C extends B {}
 *  we transforms a cast
 *    (A)new C()
 *  to
 *    (A)((B)new C()).
 *
 *  The algorithm works for Casts with class types, but also for Casts
 *  with all pointer types that point (over several indirections,
 *  i.e. ***A) to a class type.  Normalizes all graphs.  Computes type
 *  information (@see irtypeinfo.h) if not available.
 *  Invalidates trout information as new casts are generated.
 *
 *  @param gppt_fct A function that returns a pointer type that points
 *    to the type given as argument.  If this parameter is NULL, a default
 *    function is used that either uses trout information or performs a O(n)
 *    search to find an existing pointer type.  If it can not find a type,
 *    generates a pointer type with mode_P_mach and suffix "cc_ptr_tp".
 */
Michael Beck's avatar
Michael Beck committed
693
FIRM_API void normalize_irp_class_casts(gen_pointer_type_to_func gppt_fct);
694
695
696
697
698
699
700
701

/**  Insert Casts so that class type casts conform exactly with the type hierarchy
 *   in given graph.
 *
 *   For more details see normalize_irp_class_casts().
 *
 *  This transformation requires that type information is computed. @see irtypeinfo.h.
 */
Michael Beck's avatar
Michael Beck committed
702
FIRM_API void normalize_irg_class_casts(ir_graph *irg,
703
                                        gen_pointer_type_to_func gppt_fct);
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724

/** Optimize casting between class types.
 *
 *    class A { m(); }
 *    class B extends A { }
 *    class C extends B {}
 *  Performs the following transformations:
 *    C c = (C)(B)(A)(B)new C()  --> C c = (C)(B)newC() --> C c = new C()
 *    (Optimizing downcasts as A a = (A)(B)(new A()) --> A a = new A() can
 *     be suppressed by setting the flag opt_suppress_downcast_optimization.
 *     Downcasting A to B might cause an exception.  It is not clear
 *     whether this is modeled by the Firm Cast node, as it has no exception
 *     outputs.);
 *  If there is inh_m() that overwrites m() in B:
 *    ((A) new B()).m()  --> (new B()).inh_m()
 *  Phi((A)x, (A)y)  --> (A) Phi (x, y)  if (A) is an upcast.
 *
 *  Computes type information if not available. @see irtypeinfo.h.
 *  Typeinformation is valid after optimization.
 *  Invalidates trout information.
 */
Michael Beck's avatar
Michael Beck committed
725
FIRM_API void optimize_class_casts(void);
726

Michael Beck's avatar
Michael Beck committed
727
/**
728
729
 * CLiff Click's combo algorithm from
 *   "Combining Analyses, combining Optimizations".
Michael Beck's avatar
Michael Beck committed
730
 *
731
732
 * Does conditional constant propagation, unreachable code elimination and
 * optimistic global value numbering at once.
733
734
 *
 * @param irg  the graph to run on
Michael Beck's avatar
Michael Beck committed
735
 */
Michael Beck's avatar
Michael Beck committed
736
FIRM_API void combo(ir_graph *irg);
Michael Beck's avatar
Michael Beck committed
737

Michael Beck's avatar
Michael Beck committed
738
739
740
741
742
743
744
/**
 * Creates an ir_graph pass for combo.
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
745
FIRM_API ir_graph_pass_t *combo_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
746

747
748
749
750
751
/**
 * Inlines all small methods at call sites where the called address comes
 * from a SymConst node that references the entity representing the called
 * method.
 *
752
753
 * @param irg  the graph
 * @param size maximum function size
754
755
756
757
758
 *
 * The size argument is a rough measure for the code size of the method:
 * Methods where the obstack containing the firm graph is smaller than
 * size are inlined.  Further only a limited number of calls are inlined.
 * If the method contains more than 1024 inlineable calls none will be
759
 * inlined.
760
 * Inlining is only performed if flags `optimize' and `inlining' are set.
761
762
763
764
 * The graph may not be in state phase_building.
 * It is recommended to call local_optimize_graph() after inlining as this
 * function leaves a set of obscure Tuple nodes, e.g. a Proj-Tuple-Jmp
 * combination as control flow operation.
765
 */
Michael Beck's avatar
Michael Beck committed
766
FIRM_API void inline_small_irgs(ir_graph *irg, int size);
767

768
769
770
771
772
773
774
775
/**
 * Creates an ir_graph pass for inline_small_irgs().
 *
 * @param name   the name of this pass or NULL
 * @param size   maximum function size
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
776
FIRM_API ir_graph_pass_t *inline_small_irgs_pass(const char *name, int size);
777

778
779
/**
 * Inlineing with a different heuristic than inline_small_irgs().
780
 *
781
 * Inlines leave functions.  If inlining creates new leave
782
783
 * function inlines these, too. (If g calls f, and f calls leave h,
 * h is first inlined in f and then f in g.)
784
 *
785
 * Then inlines all small functions (this is not recursive).
786
 *
787
 * For a heuristic this inlining uses firm node counts.  It does
788
789
790
 * not count auxiliary nodes as Proj, Tuple, End, Start, Id, Sync.
 * If the ignore_runtime flag is set, calls to functions marked with the
 * mtp_property_runtime property are ignored.
791
 *
792
793
 * @param maxsize         Do not inline any calls if a method has more than
 *                        maxsize firm nodes.  It may reach this limit by
794
 *                        inlining.
795
796
797
798
799
 * @param leavesize       Inline leave functions if they have less than leavesize
 *                        nodes.
 * @param size            Inline all function smaller than size.
 * @param ignore_runtime  count a function only calling runtime functions as
 *                        leave
800
 */
Michael Beck's avatar
Michael Beck committed
801
FIRM_API void inline_leave_functions(unsigned maxsize, unsigned leavesize,
802
                                     unsigned size, int ignore_runtime);
803

804
805
806
807
808
809
/**
 * Creates an ir_prog pass for inline_leave_functions().
 *
 * @param name            the name of this pass or NULL
 * @param maxsize         Do not inline any calls if a method has more than
 *                        maxsize firm nodes.  It may reach this limit by
810
 *                        inlining.
811
812
813
814
815
816
817
818
 * @param leavesize       Inline leave functions if they have less than leavesize
 *                        nodes.
 * @param size            Inline all function smaller than size.
 * @param ignore_runtime  count a function only calling runtime functions as
 *                        leave
 *
 * @return  the newly created ir_prog pass
 */
Michael Beck's avatar
Michael Beck committed
819
FIRM_API ir_prog_pass_t *inline_leave_functions_pass(const char *name,
820
821
		unsigned maxsize, unsigned leavesize, unsigned size,
		int ignore_runtime);
822

823
824
typedef void (*opt_ptr)(ir_graph *irg);

825
826
827
828
/**
 * Heuristic inliner. Calculates a benefice value for every call and inlines
 * those calls with a value higher than the threshold.
 *
829
830
831
832
 * @param maxsize             Do not inline any calls if a method has more than
 *                            maxsize firm nodes.  It may reach this limit by
 *                            inlining.
 * @param inline_threshold    inlining threshold
833
834
 * @param after_inline_opt    optimizations performed immediately after inlining
 *                            some calls
835
 */
Michael Beck's avatar
Michael Beck committed
836
FIRM_API void inline_functions(unsigned maxsize, int inline_threshold,
837
                               opt_ptr after_inline_opt);
838

839
840
841
/**
 * Creates an ir_prog pass for inline_functions().
 *
842
843
844
 * @param name               the name of this pass or NULL
 * @param maxsize            Do not inline any calls if a method has more than
 *                           maxsize firm nodes.  It may reach this limit by
845
 *                           inlineing.
846
 * @param inline_threshold   inlining threshold
847
848
849
850
 * @param after_inline_opt   a function that is called after inlining a
 *                           procedure. You should run fast local optimisations
 *                           here which cleanup the graph before further
 *                           inlining
851
852
853
 *
 * @return  the newly created ir_prog pass
 */
Michael Beck's avatar
Michael Beck committed
854
FIRM_API ir_prog_pass_t *inline_functions_pass(const char *name,
855
		unsigned maxsize, int inline_threshold, opt_ptr after_inline_opt);
856

Michael Beck's avatar
Michael Beck committed
857
/**
858
 * Combines congruent blocks into one.
Michael Beck's avatar
Michael Beck committed
859
860
861
862
863
 *
 * @param irg   The IR-graph to optimize.
 *
 * @return non-zero if the graph was transformed
 */
Michael Beck's avatar
Michael Beck committed
864
FIRM_API int shape_blocks(ir_graph *irg);
Michael Beck's avatar
Michael Beck committed
865

Michael Beck's avatar
Michael Beck committed
866
867
868
869
870
871
872
/**
 * Creates an ir_graph pass for shape_blocks().
 *
 * @param name   the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
873
FIRM_API ir_graph_pass_t *shape_blocks_pass(const char *name);
Michael Beck's avatar
Michael Beck committed
874

875
876
/**
 * Perform loop inversion on a given graph.
877
 * Loop inversion transforms a head controlled loop (like while(...) {} and
878
879
 * for(...) {}) into a foot controlled loop (do {} while(...)).
 */
Michael Beck's avatar
Michael Beck committed
880
FIRM_API void do_loop_inversion(ir_graph *irg);
881

882
883
884
885
886
/**
 * Perform loop unrolling on a given graph.
 * Loop unrolling multiplies the number loop completely by a number found
 * through a heuristic.
 */
Michael Beck's avatar
Michael Beck committed
887
FIRM_API void do_loop_unrolling(ir_graph *irg);
888

889
890
891
/**
 * Perform loop peeling on a given graph.
 */
Michael Beck's avatar
Michael Beck committed
892
FIRM_API void do_loop_peeling(ir_graph *irg);
893

894
895
896
897
898
899
900
/**
 * Creates an ir_graph pass for loop inversion.
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
901
FIRM_API ir_graph_pass_t *loop_inversion_pass(const char *name);
902
903
904
905
906
907
908
909

/**
 * Creates an ir_graph pass for loop unrolling.
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
910
FIRM_API ir_graph_pass_t *loop_unroll_pass(const char *name);
911
912
913
914
915
916
917
918

/**
 * Creates an ir_graph pass for loop peeling.
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
919
FIRM_API ir_graph_pass_t *loop_peeling_pass(const char *name);
920

921
922
typedef ir_type *(*get_Alloc_func)(ir_node *n);
/** Set a new get_Alloc_func and returns the old one. */
Michael Beck's avatar
Michael Beck committed
923
FIRM_API get_Alloc_func firm_set_Alloc_func(get_Alloc_func newf);
924

925
926
927
928
929
930
931
/**
 * Creates an ir_graph pass for set_vrp_data()
 *
 * @param name The name of this pass or NULL
 *
 * @return the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
932
FIRM_API ir_graph_pass_t *set_vrp_pass(const char *name);
933

934
935
936
937
938
939
940
941
/**
 * Removes all entities which are unused.
 *
 * Unused entities have ir_visibility_local and are not used directly or
 * indirectly through entities/code visible outside the compilation unit.
 * This is usually conservative than gc_irgs, but does not respect properties
 * of object-oriented programs.
 */
Michael Beck's avatar
Michael Beck committed
942
FIRM_API void garbage_collect_entities(void);
943
944

/** Pass for garbage_collect_entities */
Michael Beck's avatar
Michael Beck committed
945
FIRM_API ir_prog_pass_t *garbage_collect_entities_pass(const char *name);
946

947
948
/**
 * Performs dead node elimination by copying the ir graph to a new obstack.
949
950
951
952
953
954
955
956
957
958
 *
 *  The major intention of this pass is to free memory occupied by
 *  dead nodes and outdated analyzes information.  Further this
 *  function removes Bad predecessors from Blocks and the corresponding
 *  inputs to Phi nodes.  This opens optimization potential for other
 *  optimizations.  Further this phase reduces dead Block<->Jmp
 *  self-cycles to Bad nodes.
 *
 *  Dead_node_elimination is only performed if options `optimize' and
 *  `opt_dead_node_elimination' are set.  The graph may
959
 *  not be in state phase_building.  The outs datastructure is freed,
960
961
962
963
964
965
 *  the outs state set to outs_none.  Backedge information is conserved.
 *  Removes old attributes of nodes.  Sets link field to NULL.
 *  Callee information must be freed (irg_callee_info_none).
 *
 * @param irg  The graph to be optimized.
 */
Michael Beck's avatar
Michael Beck committed
966
FIRM_API void dead_node_elimination(ir_graph *irg);
967
968
969
970
971
972
973
974

/**
 * Creates an ir_graph pass for dead_node_elimination().
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
975
FIRM_API ir_graph_pass_t *dead_node_elimination_pass(const char *name);
976

977
978
/**
 * Inlines a method at the given call site.
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
 *
 *  Removes the call node and splits the basic block the call node
 *  belongs to.  Inserts a copy of the called graph between these nodes.
 *  Assumes that call is a Call node in current_ir_graph and that
 *  the type in the Call nodes type attribute is the same as the
 *  type of the called graph.
 *  Further it assumes that all Phi nodes in a block of current_ir_graph
 *  are assembled in a "link" list in the link field of the corresponding
 *  block nodes.  Further assumes that all Proj nodes are in a "link" list
 *  in the nodes producing the tuple.  (This is only an optical feature
 *  for the graph.)  Conserves this feature for the old
 *  nodes of the graph.  This precondition can be established by a call to
 *  collect_phisprojs(), see irgmod.h.
 *  As dead_node_elimination this function reduces dead Block<->Jmp
 *  self-cycles to Bad nodes.
 *
 *  Called_graph must be unequal to current_ir_graph.   Will not inline
 *  if they are equal.
 *  Sets visited masterflag in current_ir_graph to the max of the flag in
 *  current and called graph.
 *  Assumes that both, the called and the calling graph are in state
 *  "op_pin_state_pinned".
 *  It is recommended to call local_optimize_graph() after inlining as this
 *  function leaves a set of obscure Tuple nodes, e.g. a Proj-Tuple-Jmp
 *  combination as control flow operation.
 *
 *  @param call          the call node that should be inlined
 *  @param called_graph  the IR-graph that is called at call
 *
 *  @return zero if method could not be inlined (recursion for instance),
 *          non-zero if all went ok
 */
Michael Beck's avatar
Michael Beck committed
1011
FIRM_API int inline_method(ir_node *call, ir_graph *called_graph);
1012

1013
1014
/**
 * Code Placement.
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
 *
 * Pins all floating nodes to a block where they
 * will be executed only if needed.   Depends on the flag opt_global_cse.
 * Graph may not be in phase_building.  Does not schedule control dead
 * code.  Uses dominator information which it computes if the irg is not
 * in state dom_consistent.  Destroys the out information as it moves nodes
 * to other blocks.  Optimizes Tuples in Control edges.
 *
 * Call remove_critical_cf_edges() before place_code().  This normalizes
 * the control flow graph so that for all operations a basic block exists
 * where they can be optimally placed.
 */
Michael Beck's avatar
Michael Beck committed
1027
FIRM_API void place_code(ir_graph *irg);
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037

/**
 * Creates an ir_graph pass for place_code().
 * This pass enables GCSE, runs optimize_graph_df() and finally
 * place_code();
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
1038
FIRM_API ir_graph_pass_t *place_code_pass(const char *name);
1039

Christoph Mallon's avatar
Christoph Mallon committed
1040
/**
1041
 * Determine information about the values of nodes and perform simplifications
Christoph Mallon's avatar
Christoph Mallon committed
1042
1043
1044
 * using this information.  This optimization performs a data-flow analysis to
 * find the minimal fixpoint.
 */
Michael Beck's avatar
Michael Beck committed
1045
FIRM_API void fixpoint_vrp(ir_graph*);
Christoph Mallon's avatar
Christoph Mallon committed
1046

1047
1048
1049
/**
 * Creates an ir_graph pass for fixpoint_vrp().
 * This pass dDetermines information about the values of nodes
1050
 * and perform simplifications using this information.
1051
1052
1053
1054
1055
1056
1057
 * This optimization performs a data-flow analysis to
 * find the minimal fixpoint.
 *
 * @param name     the name of this pass or NULL
 *
 * @return  the newly created ir_graph pass
 */
Michael Beck's avatar
Michael Beck committed
1058
FIRM_API ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name);
1059

1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
/**
 * Check, if the value of a node is != 0.
 *
 * This is a often needed case, so we handle here Confirm
 * nodes too.
 *
 * @param n        a node representing the value
 * @param confirm  if n is confirmed to be != 0, returns
 *                 the the Confirm-node, else NULL
 */
FIRM_API int value_not_zero(const ir_node *n, ir_node_cnst_ptr *confirm);

/**
 * Check, if the value of a node cannot represent a NULL pointer.
 *
 * - If option sel_based_null_check_elim is enabled, all
 *   Sel nodes can be skipped.
 * - A SymConst(entity) is NEVER a NULL pointer
 * - A Const != NULL is NEVER a NULL pointer
 * - Confirms are evaluated
 *
 * @param n        a node representing the value
 * @param confirm  if n is confirmed to be != NULL, returns
 *                 the the Confirm-node, else NULL
 */
FIRM_API int value_not_null(const ir_node *n, ir_node_cnst_ptr *confirm);

/**
 * Check, if the value of a node can be confirmed >= 0 or <= 0,
 * If the mode of the value did not honor signed zeros, else
 * check for >= 0 or < 0.
 *
 * @param n  a node representing the value
 */
FIRM_API ir_value_classify_sign classify_value_sign(ir_node *n);

/**
 * Return the value of a Cmp if one or both predecessors
 * are Confirm nodes.
 *
1100
1101
1102
1103
 * @param cmp       the compare node that will be evaluated
 * @param left      the left operand of the Cmp
 * @param right     the right operand of the Cmp
 * @param relation  the compare relation
1104
1105
 */
FIRM_API ir_tarval *computed_value_Cmp_Confirm(
1106
	const ir_node *cmp, ir_node *left, ir_node *right, ir_relation relation);
1107

1108
#include "end.h"
1109

1110
#endif