6 * File name: ir/opt/strength_red.c
7 * Purpose: Make strength reduction .
8 * Author: Beyhan Veliev
12 * Copyright: (c) 2003 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
21 # include "strength_red.h"
23 # include "irnode_t.h"
25 # include "irloop_t.h"
33 /* The information needed for a induction variable*/
34 struct induct_var_info {
35 ir_op *operation_code;
36 ir_node *increment, *init, *op;
41 static struct induct_var_info ivi;
43 /** Counter for verbose information about optimization. */
44 static int n_reduced_expressions;
46 /** Detect basic iteration variables.
48 * The variable ir represented by a subgraph as this:
58 * Where op is a Add or Sub, and init is loop invariant.
59 * @@@ So far we only accept Phi nodes with two predecessors.
60 * We could expand this to Phi nodes where all preds are either
61 * op or loop invariant.
63 * @param n A phi node.
65 static struct induct_var_info *is_induction_variable (ir_node *n) {
67 ir_node *phi_pred_0, *phi_pred_1, *add_r, *add_l, *sub_r, *sub_l ;
68 ir_op *phi_pred_0_op, *phi_pred_1_op;
69 struct induct_var_info *info;
72 info->operation_code = NULL;
73 info->increment = NULL;
77 info->init_pred_pos = -1;
78 info->op_pred_pos = -1;
80 assert(get_irn_op(n) == op_Phi);
82 /* The necessary conditions for the phi node. */
83 if (get_irn_arity(n) != 2 ||
84 !has_backedges(get_nodes_block(n)) )
87 /* The predecessors of the phi node. */
88 phi_pred_0 = get_Phi_pred(n, 0);
89 phi_pred_1 = get_Phi_pred(n, 1);
91 /*The operation of the predecessors. */
92 phi_pred_0_op = get_irn_op(get_Phi_pred(n, 0));
93 phi_pred_1_op = get_irn_op(get_Phi_pred(n, 1));
95 /*Compute if the induction variable is added or substracted wiht a constant . */
96 if (phi_pred_0_op == op_Add){
97 info->operation_code = op_Add;
98 add_l = get_Add_left(phi_pred_0);
99 add_r = get_Add_right(phi_pred_0);
100 info->op_pred_pos = 0;
102 info->increment = add_r;
103 } else if (add_r == n){
104 info->increment = add_l;
106 } else if (phi_pred_1_op == op_Add){
107 info->operation_code = op_Add ;
108 add_l = get_Add_left(phi_pred_1);
109 add_r = get_Add_right(phi_pred_1);
110 info->op_pred_pos = 1;
112 info->increment = add_r;
113 } else if (add_r == n){
114 info->increment = add_l;
116 } else if (phi_pred_0_op == op_Sub){
117 info->operation_code = op_Sub;
118 sub_r = get_Sub_right(phi_pred_0);
119 sub_l = get_Sub_left(phi_pred_0);
120 info->op_pred_pos = 0;
122 info->increment = sub_r;
123 } else if (sub_r == n){
124 info->increment = sub_l;
126 } else if (phi_pred_1_op == op_Sub){
127 info->operation_code = op_Sub;
128 sub_r = get_Sub_right(phi_pred_1);
129 sub_l = get_Sub_left(phi_pred_1);
130 info->op_pred_pos = 1;
132 info->increment = sub_r;
137 /*Compute the position of the backedge. */
138 if (is_backedge(get_nodes_block(n), 0)){
140 info->init_pred_pos = 1;
141 info->op = get_Phi_pred(n, 0);
142 info->init = get_Phi_pred(n, 1);
143 } else if (is_backedge(get_nodes_block(n), 1)){
145 info->init_pred_pos = 0;
146 info->op = get_Phi_pred(n, 1);
147 info->init = get_Phi_pred(n, 0);
150 if (info->be_pos == 0) {
151 if (get_Block_dom_depth(get_nodes_block(phi_pred_1)) >=
152 get_Block_dom_depth(get_nodes_block(n))) {
155 } else if (get_Block_dom_depth(get_nodes_block(phi_pred_0)) >=
156 get_Block_dom_depth(get_nodes_block(n))) return NULL;
158 if (get_Block_dom_depth(get_nodes_block(info->increment)) >=
159 get_Block_dom_depth(get_nodes_block(n))) return NULL;
165 const char *get_irg_dump_name(ir_graph *irg);
170 * @param *srong The node to be reduce.
171 * @param *env Free environment pointer.
173 * The node for reduce mus be in a loop whit *phi and *add.The *phi node muss
174 * have 2 predecessors a Const and a Add node. The predecessors of Add node muss
175 * be *phi and a Const node. The nodes a, b, c muss be Const with dom_depth <
178 void reduce_a_node(ir_node *strong, void *env) {
179 ir_node *phi, *l, *r, *c;
182 // This "if" finds the node for reduce.
184 op_strong = get_irn_op(strong);
185 if (op_strong == op_Mul/* || op_strong == op_Div */) {
187 l = get_binop_left (strong);
188 r = get_binop_right(strong);
190 ir_loop *l_strong = get_irn_loop(get_nodes_block(strong));
192 // This "if" finds the Phi predecessors for the node that must be reduced.
193 if ((get_irn_op(l) == op_Phi) &&
194 is_induction_variable(l) != NULL &&
195 (get_irn_loop(get_nodes_block(l)) == l_strong)) {
198 } else if ((get_irn_op(r) == op_Phi) &&
199 is_induction_variable(r) != NULL &&
200 (get_irn_loop(get_nodes_block(r)) == l_strong)) {
205 if (get_Block_dom_depth(get_nodes_block(c)) >=
206 get_Block_dom_depth(get_nodes_block(phi))) return;
208 /* Some statistics and user information ... */
209 if (get_opt_strength_red_verbosity() && get_firm_verbosity() > 1) {
210 printf("Reducing node: "); DDMN(strong);
211 printf(" iter var is "); DDMN(ivi.op);
212 printf(" in graph "); DDMG(current_ir_graph);
214 n_reduced_expressions++;
216 ir_node *inc = NULL, *init = NULL, *new_phi, *in[2], *new_op = NULL, *block_init, *block_inc;
217 ir_node *init_block = get_nodes_block(ivi.init);
218 ir_node *increment_block = get_nodes_block(ivi.increment);
219 ir_node *c_block = get_nodes_block(c) ;
221 if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
222 block_inc = increment_block;
226 if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
227 block_init = init_block;
229 block_init = c_block;
231 /* Compute new loop invariant increment and initialization values. */
232 if (op_strong == op_Mul) {
233 inc = new_r_Mul (current_ir_graph, block_inc, ivi.increment, c, get_irn_mode(c));
234 init = new_r_Mul (current_ir_graph, block_init, ivi.init, c, get_irn_mode(ivi.init));
235 } else if (op_strong == op_Div) {
236 inc = new_r_Div (current_ir_graph, block_inc, get_irg_initial_mem(get_irn_irg(strong)),
238 init = new_r_Div (current_ir_graph, block_init, get_irg_initial_mem(get_irn_irg(strong)),
243 /* Generate a new basic induction variable. Break the data flow loop
244 initially by using an Unknown node. */
245 in[ivi.op_pred_pos] = new_Unknown(get_irn_mode(init));
246 in[ivi.init_pred_pos] = init;
247 new_phi = new_r_Phi(current_ir_graph, get_nodes_block(phi), 2, in, get_irn_mode(init));
249 if (ivi.operation_code == op_Add)
250 new_op = new_r_Add(current_ir_graph, get_nodes_block(ivi.op), inc, new_phi,
252 else if (ivi.operation_code == op_Sub)
253 new_op = new_r_Sub(current_ir_graph, get_nodes_block(ivi.op), new_phi, inc,
255 set_Phi_pred(new_phi, ivi.op_pred_pos, new_op);
257 /* Replace the use of the strength reduced value. */
258 exchange(strong, new_phi);
264 /* Performs strength reduction for the passed graph. */
265 void reduce_strength(ir_graph *irg) {
267 if (!get_optimize() || !get_opt_strength_red()) return;
269 n_reduced_expressions = 0;
271 /* -- Precompute some information -- */
272 /* Call algorithm that computes the backedges */
273 construct_cf_backedges(irg);
274 /* Call algorithm that computes the dominator trees. */
277 /* -- Search expressions that can be optimized -- */
278 irg_walk_graph(irg, NULL, reduce_a_node, NULL);
281 if (get_opt_strength_red_verbosity()) {
282 if (n_reduced_expressions > 0)
283 printf("reduced strength of %d expressions in graph %s.\n",
284 n_reduced_expressions, get_irg_dump_name(irg));