3 * File name: testprograms/strength_red_example.c
4 * Purpose: Shows how strength red works
5 * Author: Beyhan Veliev
9 * Copyright: (c) 2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
23 * This file constructs the ir for the following pseudo-program:
37 #define new_Const_int(n) new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
40 #define CLASSNAME "STRENGTH_RED_EXAMPLE"
41 #define METHODNAME1 "STRENGTH_RED_EXAMPLE_m1"
42 #define METHODNAME2 "STRENGTH_RED_EXAMPLE_m2"
43 #define METHODNAME3 "STRENGTH_RED_EXAMPLE_m3"
44 #define METHODNAME4 "STRENGTH_RED_EXAMPLE_m4"
45 #define METHODNAME5 "STRENGTH_RED_EXAMPLE_m5"
46 #define METHODNAME6 "STRENGTH_RED_EXAMPLE_m6"
47 #define METHODNAME7 "STRENGTH_RED_EXAMPLE_m7"
48 #define METHODNAME8 "STRENGTH_RED_EXAMPLE_m8"
49 #define METHODNAME9 "STRENGTH_RED_EXAMPLE_m9"
50 #define METHODTPNAME "STRENGTH_RED_EXAMPLE_meth_tp"
57 #define PRIM_NAME "int"
62 static int arr_pos = 1;
63 static ir_type *typ, *typ2;
65 static ir_node *r1, *f, *r, *c2;
73 * Constructs a new (method-)function of the form
75 * typ fct_name(typ arg) {
76 * for (i = start_value; i < end_value;) { ... }
79 * After return, the loop body is the current block.
81 * @param owner owner-type of this (method-)function
82 * @param mtp the method type of this function
83 * @param fct_name the name of the function
84 * @param loop_dir the loop direction
86 static void function_begin(ir_type *owner, ir_type *mtp, char *fct_name, loop_dir_t loop_dir) {
90 int start_value, end_value;
93 if (loop_dir == loop_forward) {
104 /* The entity for the procedure */
105 entity *ent = new_entity (owner, new_id_from_str(fct_name), mtp);
107 /* make type infromation for the array */
108 ir_type *array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
110 /* set the bounds for the array */
111 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
113 /* The array is an entity of the owner type */
114 entity *array_ent = new_entity(owner, new_id_from_str("a"), array_type);
116 /** The code of the procedure **/
118 /* Generates start and end blocks and nodes, and a first, initial block */
120 new_ir_graph(ent, NRLOCS);
122 /* The value position used for: */
124 if (fct_name == METHODNAME7)
125 c2 = new_Const_int(5);
127 /* Generate the constant and assign it to b. The assignment is resolved to a
129 set_value(i_pos, new_Const_int(start_value));
131 sym.entity_p = array_ent;
132 set_value(arr_pos, new_SymConst(sym, symconst_addr_ent));
135 /* We know all predecessors of the block and all set_values and set_stores are
136 preformed. We can mature the block. */
137 mature_immBlock(get_irg_current_block(current_ir_graph));
139 /* Generate a conditional branch */
141 add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
143 cmp = new_Cmp(new_Const_int(end_value), get_value(i_pos, mode_Is));
144 x = new_Cond(new_Proj(cmp, mode_b, cmp_dir));
146 f = new_Proj(x, mode_X, 0);
147 t = new_Proj(x, mode_X, 1);
149 /* generate and fill the loop body block */
151 add_immBlock_pred(r, t);
157 * finishes a builded function.
159 * @param b the return value
161 static void function_end(ir_node *b) {
162 ir_node *x = new_Jmp();
164 add_immBlock_pred(r1, x);
168 add_immBlock_pred(get_cur_block(), f);
169 mature_immBlock (get_cur_block());
170 /* The Return statement */
172 ir_node *in[1], *store ;
176 x = new_Return(store, 1, in);
178 add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
181 /* finalize the end block generated in new_ir_graph() */
182 mature_immBlock(get_irg_end_block(current_ir_graph));
190 entity *ent, *array_ent, *array_ent2;
191 ir_type *proc_tp, *array_type, *array_type2; /* type information for the method main */
192 ir_node *x,*x1 , *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
195 printf("\nCreating an IR graph: IF_EXAMPLE...\n");
199 arch_dep_set_opts(arch_dep_none);
201 do_node_verification(FIRM_VERIFICATION_REPORT);
203 typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
205 typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
207 /** The global array variable a **/
210 /** Type information for the procedure **/
211 owner = get_glob_type();
212 /* Type information for the procedure */
213 proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)), NRARGS, NRES);
214 set_method_param_type(proc_tp, 0, typ);
215 set_method_res_type(proc_tp, 0, typ);
218 /* --------------------------------------------------------------------- */
220 /* The entity for the procedure */
221 ent = new_entity (owner,
222 new_id_from_str (METHODNAME1),
224 /* The parameter and result types of the procedure. */
226 /* make type infromation for the array */
227 array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
228 array_type2 = new_type_array(new_id_from_chars("array2", 6),N_DIMS, typ2);
229 /* set the bounds for the array */
230 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
231 set_array_bounds_int(array_type2, 0, L_BOUND, U_BOUND);
233 /* The array is an entity of the global typ */
234 array_ent = new_entity( owner, new_id_from_str("a"), array_type);
235 array_ent2 = new_entity( owner, new_id_from_str("a2"), array_type2);
237 /** The code of the procedure **/
240 /* Generates start and end blocks and nodes, and a first, initial block */
243 irg = new_ir_graph(ent, NRLOCS);
245 /* The value position used for: */
248 /* Generate the constant and assign it to b. The assignment is resovled to a
250 set_value (i_pos, new_Const_int(0));
253 /* We know all predecessors of the block and all set_values and set_stores are
254 preformed. We can mature the block. */
255 mature_immBlock (get_irg_current_block(irg));
257 /* Generate a conditional branch */
259 add_immBlock_pred(get_irg_current_block(irg), x);
260 cmp = new_Cmp(new_Const_int(10), get_value(i_pos, mode_Is));
261 x = new_Cond(new_Proj(cmp, mode_b, pn_Cmp_Gt));
262 f = new_Proj(x, mode_X, 0);
263 t = new_Proj(x, mode_X, 1);
265 /* generate and fill the then block */
267 add_immBlock_pred (r, t);
269 ir_node *b, *c, *d, *res;
270 symconst_symbol sym, sym2;
271 c = new_Const_int(1);
272 b = new_Const_int(4);
273 ir_node *b2 = new_Const_int(12);
274 sym.entity_p = array_ent ;
275 sym2.entity_p = array_ent2 ;
276 d = new_SymConst(sym, symconst_addr_ent);
277 ir_node *d2 = new_SymConst(sym2, symconst_addr_ent);
278 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
279 //ir_node *res2 = new_Add(d2, get_value(i_pos, mode_Is), mode_P);
280 ir_node *res2 = new_Add(d2, new_Mul(get_value(i_pos, mode_Is), b2, mode_Is), mode_P);
281 //res2 = new_Add(res2, new_Const_int(12), mode_P);
282 set_store (new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
283 set_store (new_Proj(new_Store(get_store(), res2, new_Const_int(16)), mode_M, 0));
284 d = new_SymConst(sym, symconst_addr_ent);
285 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
286 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(15)), mode_M, 0));
288 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
293 add_immBlock_pred(r1, x);
297 ir_node *b1 = new_Const_int(45);
298 add_immBlock_pred(get_irg_current_block(irg), f);
299 cmp = new_Cmp(new_Const_int(0), b1);
300 x = new_Cond (new_Proj(cmp, mode_b, pn_Cmp_Lt));
301 f1 = new_Proj (x, mode_X, 0);
302 t1 = new_Proj (x, mode_X, 1);
304 ir_node *block = new_immBlock();
305 add_immBlock_pred(block, t1);
306 b1 = new_Sub (b1, get_value(i_pos, mode_Is), mode_Is);
307 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
308 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
309 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
313 mature_immBlock(block);
315 add_immBlock_pred(r2, x1);
318 block = new_immBlock();
319 add_immBlock_pred(block, f1);
320 mature_immBlock(block);
321 /* The Return statement */
323 ir_node *in[1], *store ;
324 in[0] = get_value(i_pos, mode_Is);
327 x = new_Return(store, 1, in);
329 add_immBlock_pred(get_irg_end_block(irg), x);
331 /* finalize the end block generated in new_ir_graph() */
332 mature_immBlock(get_irg_end_block(irg));
335 /* -------------------------------------------------------------------------------- */
337 function_begin(owner, proc_tp, METHODNAME2, loop_forward);
339 q = new_Const_int(15);
340 ir_node *q1 = new_Const_int(13);
341 c = new_Const_int(1);
342 b = new_Const_int(4);
343 mul = new_Mul(q, get_value(i_pos, mode_Is), mode_Is);
345 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
346 res = new_Add(q1, res, mode_P);
347 set_store(new_Proj(new_Store (get_store(), res, mul), mode_M, 0));
349 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
353 /* -------------------------------------------------------------------------- */
355 function_begin(owner, proc_tp, METHODNAME3, loop_backward);
357 c = new_Const_int(1);
358 b = new_Const_int(4);
359 ir_node *b3 = new_Const_int(8);
361 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
362 res = new_Add(b, res, mode_P);
363 res = new_Add(b3, res, mode_P);
364 ir_node *res3 = new_Add(b3, res, mode_P);
365 res = new_Add(res3, res, mode_P);
366 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
369 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
373 /* -------------------------------------------------------------------------- */
375 function_begin(owner, proc_tp, METHODNAME4, loop_forward);
377 c = new_Const_int(1);
378 b = new_Const_int(4);
379 ir_node *b4 = new_Const_int(8);
381 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
382 ir_node *mul4 = new_Mul(get_value(i_pos, mode_Is), b4, mode_Is);
383 res = new_Add(mul4, get_value(arr_pos, mode_P), mode_P);
384 set_store (new_Proj (new_Store (get_store (), res,get_value(i_pos, mode_Is)),
386 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
387 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
391 /* -------------------------------------------------------------------------- */
393 function_begin(owner, proc_tp, METHODNAME5, loop_backward);
395 c = new_Const_int(1);
396 b = new_Const_int(4);
398 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
400 ir_node * res5 = new_Add (c, b, mode_Is);
401 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
402 res = new_Add(res, b, mode_P);
403 res = new_Add(res, res5, mode_P);
404 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
408 /* -------------------------------------------------------------------------- */
410 function_begin(owner, proc_tp, METHODNAME6, loop_forward);
412 c = new_Const_int(1);
413 ir_node *c1 = new_Const_int(5);
414 b = new_Const_int(4);
416 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
418 res = new_Add( get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is),
419 b, mode_Is), mode_P);
420 res = new_Sub(c1, res, mode_P);
421 res = new_Add( b, res, mode_P);
422 res = new_Add(b, res, mode_P);
423 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
427 /* -------------------------------------------------------------------------- */
429 function_begin(owner, proc_tp, METHODNAME7, loop_backward);
431 c = new_Const_int(1);
432 b = new_Const_int(4);
433 ir_node *b7 = new_Const_int(19);
436 res = get_value(i_pos, mode_Is);
437 res = new_Add(res, b, mode_Is);
438 res = new_Add(res, b7, mode_Is);
439 res = new_Mul(res, b, mode_Is);
440 res = new_Add(get_value(arr_pos, mode_P), res, mode_P);
441 ir_node *res7 = new_Add( get_value(i_pos, mode_Is), b7, mode_Is);
442 set_store(new_Proj(new_Store(get_store(), res, res7), mode_M, 0));
443 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
446 /* -------------------------------------------------------------------------- */
448 int i, n_irgs = get_irp_n_irgs();
450 printf("Done building the graph. Dumping and optimizing it.\n");
451 dump_consts_local(1);
452 turn_off_edge_labels();
453 for (i = 0; i < n_irgs; ++i) {
454 current_ir_graph = get_irp_irg(i);
455 irg_vrfy(current_ir_graph);
456 irg_finalize_cons (current_ir_graph);
458 /* output the vcg file */
459 //dump_ir_block_graph (current_ir_graph, "-early");
460 construct_backedges(current_ir_graph);
461 dump_ir_block_graph (current_ir_graph, 0);
463 set_opt_strength_red_verbose(0);
464 set_firm_verbosity(0);
465 optimize_reassociation(current_ir_graph);
466 reduce_strength(current_ir_graph);
468 // remove_critical_cf_edges(current_ir_graph);
469 //set_opt_global_cse(1);
470 //place_code(current_ir_graph);
471 //set_opt_global_cse(0);
472 // optimize_reassociation(current_ir_graph);
474 dump_loop_tree(current_ir_graph, "");
475 dump_ir_block_graph (current_ir_graph, "-strength_reduced");
477 //printf("use xvcg to view this graph:\n");
478 //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");