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;
44 /** Detect basic iteration variables.
46 * The variable ir represented by a subgraph as this:
56 * Where op is a Add or Sub, and init is loop invariant.
57 * @@@ So far we only accept Phi nodes with two predecessors.
58 * We could expand this to Phi nodes where all preds are either
59 * op or loop invariant.
61 * @param n A phi node.
63 static struct induct_var_info *is_induction_variable (ir_node *n) {
65 ir_node *phi_pred_0, *phi_pred_1, *add_r, *add_l, *sub_r, *sub_l ;
66 ir_op *phi_pred_0_op, *phi_pred_1_op;
67 struct induct_var_info *info;
70 info->operation_code = NULL;
71 info->increment = NULL;
75 info->init_pred_pos = -1;
76 info->op_pred_pos = -1;
78 assert(get_irn_op(n) == op_Phi);
80 /* The necessary conditions for the phi node. */
81 if (get_irn_arity(n) != 2 ||
82 !has_backedges(get_nodes_block(n)) )
85 /* The predecessors of the phi node. */
86 phi_pred_0 = get_Phi_pred(n, 0);
87 phi_pred_1 = get_Phi_pred(n, 1);
89 /*The operation of the predecessors. */
90 phi_pred_0_op = get_irn_op(get_Phi_pred(n, 0));
91 phi_pred_1_op = get_irn_op(get_Phi_pred(n, 1));
93 /*Compute if the induction variable is added or substracted wiht a constant . */
94 if (phi_pred_0_op == op_Add){
95 info->operation_code = op_Add;
96 add_l = get_Add_left(phi_pred_0);
97 add_r = get_Add_right(phi_pred_0);
98 info->op_pred_pos = 0;
100 info->increment = add_r;
101 } else if (add_r == n){
102 info->increment = add_l;
104 } else if (phi_pred_1_op == op_Add){
105 info->operation_code = op_Add ;
106 add_l = get_Add_left(phi_pred_1);
107 add_r = get_Add_right(phi_pred_1);
108 info->op_pred_pos = 1;
110 info->increment = add_r;
111 } else if (add_r == n){
112 info->increment = add_l;
114 } else if (phi_pred_0_op == op_Sub){
115 info->operation_code = op_Sub;
116 sub_r = get_Sub_right(phi_pred_0);
117 sub_l = get_Sub_left(phi_pred_0);
118 info->op_pred_pos = 0;
120 info->increment = sub_r;
121 } else if (sub_r == n){
122 info->increment = sub_l;
124 } else if (phi_pred_1_op == op_Sub){
125 info->operation_code = op_Sub;
126 sub_r = get_Sub_right(phi_pred_1);
127 sub_l = get_Sub_left(phi_pred_1);
128 info->op_pred_pos = 1;
130 info->increment = sub_r;
135 /*Compute the position of the backedge. */
136 if (is_backedge(get_nodes_block(n), 0)){
138 info->init_pred_pos = 1;
139 info->op = get_Phi_pred(n, 0);
140 info->init = get_Phi_pred(n, 1);
141 } else if (is_backedge(get_nodes_block(n), 1)){
143 info->init_pred_pos = 0;
144 info->op = get_Phi_pred(n, 1);
145 info->init = get_Phi_pred(n, 0);
148 if (info->be_pos == 0) {
149 if (get_Block_dom_depth(get_nodes_block(phi_pred_1)) >=
150 get_Block_dom_depth(get_nodes_block(n))) {
153 } else if (get_Block_dom_depth(get_nodes_block(phi_pred_0)) >=
154 get_Block_dom_depth(get_nodes_block(n))) return NULL;
156 if (get_Block_dom_depth(get_nodes_block(info->increment)) >=
157 get_Block_dom_depth(get_nodes_block(n))) return NULL;
165 * @param *srong The node to be reduce.
166 * @param *env Free environment pointer.
168 * The node for reduce mus be in a loop whit *phi and *add.The *phi node muss
169 * have 2 predecessors a Const and a Add node. The predecessors of Add node muss * be *phi and a Const node. The nodes a, b, c muss be Const with dom_depth < * phi.
172 void reduce_a_node(ir_node *strong, void *env) {
173 ir_node *phi, *l, *r, *c;
176 // This "if" finds the node for reduce.
178 op_strong = get_irn_op(strong);
179 if (op_strong == op_Mul/* || op_strong == op_Div */) {
181 l = get_binop_left (strong);
182 r = get_binop_right(strong);
184 ir_loop *l_strong = get_irn_loop(get_nodes_block(strong));
186 // This "if" finds the Phi predecessors for the node that must be reduced.
187 if ((get_irn_op(l) == op_Phi) &&
188 is_induction_variable(l) != NULL &&
189 (get_irn_loop(get_nodes_block(l)) == l_strong)) {
192 } else if ((get_irn_op(r) == op_Phi) &&
193 is_induction_variable(r) != NULL &&
194 (get_irn_loop(get_nodes_block(r)) == l_strong)) {
199 if (get_Block_dom_depth(get_nodes_block(c)) >=
200 get_Block_dom_depth(get_nodes_block(phi))) return;
202 if (get_opt_strength_red_verbosity() == 2) {
203 printf("Reducing node: "); DDMN(strong);
204 printf(" iter var is "); DDMN(ivi.op);
205 printf(" in graph "); DDMG(current_ir_graph);
208 ir_node *inc = NULL, *init = NULL, *new_phi, *in[2], *new_op = NULL, *block_init, *block_inc;
209 ir_node *init_block = get_nodes_block(ivi.init);
210 ir_node *increment_block = get_nodes_block(ivi.increment);
211 ir_node *c_block = get_nodes_block(c) ;
213 if (get_Block_dom_depth(increment_block) >= get_Block_dom_depth(c_block))
214 block_inc = increment_block;
218 if (get_Block_dom_depth(init_block) >= get_Block_dom_depth(c_block))
219 block_init = init_block;
221 block_init = c_block;
223 /* Compute new loop invariant increment and initialization values. */
224 if (op_strong == op_Mul) {
225 inc = new_r_Mul (current_ir_graph, block_inc, ivi.increment, c, get_irn_mode(c));
226 init = new_r_Mul (current_ir_graph, block_init, ivi.init, c, get_irn_mode(ivi.init));
227 } else if (op_strong == op_Div) {
228 inc = new_r_Div (current_ir_graph, block_inc, get_irg_initial_mem(get_irn_irg(strong)),
230 init = new_r_Div (current_ir_graph, block_init, get_irg_initial_mem(get_irn_irg(strong)),
235 /* Generate a new basic induction variable. Break the data flow loop
236 initially by using an Unknown node. */
237 in[ivi.op_pred_pos] = new_Unknown(get_irn_mode(init));
238 in[ivi.init_pred_pos] = init;
239 new_phi = new_r_Phi(current_ir_graph, get_nodes_block(phi), 2, in, get_irn_mode(init));
241 if (ivi.operation_code == op_Add)
242 new_op = new_r_Add(current_ir_graph, get_nodes_block(ivi.op), inc, new_phi,
244 else if (ivi.operation_code == op_Sub)
245 new_op = new_r_Sub(current_ir_graph, get_nodes_block(ivi.op), new_phi, inc,
247 set_Phi_pred(new_phi, ivi.op_pred_pos, new_op);
249 /* Replace the use of the strength reduced value. */
250 exchange(strong, new_phi);
256 /* Performs strength reduction for the passed graph. */
257 void reduce_strength(ir_graph *irg) {
259 if (!get_optimize() || !get_opt_strength_red()) return;
261 /* -- Precompute some information -- */
262 /* Call algorithm that computes the backedges */
263 construct_cf_backedges(irg);
264 /* Call algorithm that computes the dominator trees. */
267 /* -- Search expressions that can be optimized -- */
268 irg_walk_graph(irg, NULL, reduce_a_node, NULL);