2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Operator Strength Reduction.
24 * @author Michael Beck
27 * Implementation of the Operator Strength Reduction algorithm
28 * by Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick.
30 #ifndef FIRM_OPT_OPT_OSR_H
31 #define FIRM_OPT_OPT_OSR_H
33 #include "firm_types.h"
35 /** Possible flags for the Operator Scalar Replacement. */
36 typedef enum osr_flags {
37 osr_flag_none = 0, /**< no additional flags */
38 osr_flag_lftr_with_ov_check = 1, /**< do linear function test replacement
39 only if no overflow can occur. */
40 osr_flag_ignore_x86_shift = 2 /**< ignore Multiplications by 2, 4, 8 */
43 /* FirmJNI cannot handle identical enum values... */
45 /** default setting */
46 #define osr_flag_default osr_flag_lftr_with_ov_check
49 * Do the Operator Scalar Replacement optimization and linear
50 * function test replacement for loop control.
51 * Can be switched off using the set_opt_strength_red() flag.
52 * In that case, only remove_phi_cycles() is executed.
54 * @param irg the graph which should be optimized
55 * @param flags set of osr_flags
57 * The linear function replacement test is controlled by the flags.
58 * If the osr_flag_lftr_with_ov_check is set, the replacement is only
59 * done if do overflow can occur.
60 * Otherwise it is ALWAYS done which might be insecure.
64 * for (i = 0; i < 100; ++i)
66 * might be replaced by
68 * for (i = 0; i < 400; i += 4)
72 * for (i = 0; i < 0x7FFFFFFF; ++i)
74 * will not be replaced by
76 * for (i = 0; i < 0xFFFFFFFC; i += 4)
78 * because of overflow.
82 * for (i = 0; i <= 0xF; ++i)
84 * will NOT be transformed into
86 * for (i = 0xFFFFFFF0; i <= 0xFFFFFFFF; ++i)
88 * although here is no direct overflow. The OV occurs when the ++i
89 * is executed (and would created an endless loop here!).
91 * For the same reason, a loop
93 * for (i = 0; i <= 9; i += x)
95 * will NOT be transformed because we cannot estimate whether an overflow
96 * might happen adding x.
98 * Note that i < a + 400 is also not possible with the current implementation
99 * although this might be allowed by other compilers...
101 * Note further that tests for equality can be handled some simpler (but are not
104 * This algorithm destroys the link field of nodes.
106 void opt_osr(ir_graph *irg, unsigned flags);
109 * Removes useless Phi cycles, i.e cycles of Phi nodes with only one
111 * This is automatically done in opt_osr(), so there is no need to call it
114 * @param irg the graph which should be optimized
116 * This algorithm destroys the link field of nodes.
118 void remove_phi_cycles(ir_graph *irg);
120 #endif /* FIRM_OPT_OPT_OSR_H */