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.
16 #include <libfirm/firm.h>
19 * This file constructs the ir for the following pseudo-program:
33 #define new_Const_int(n) new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
36 #define CLASSNAME "STRENGTH_RED_EXAMPLE"
37 #define METHODNAME1 "STRENGTH_RED_EXAMPLE_m1"
38 #define METHODNAME2 "STRENGTH_RED_EXAMPLE_m2"
39 #define METHODNAME3 "STRENGTH_RED_EXAMPLE_m3"
40 #define METHODNAME4 "STRENGTH_RED_EXAMPLE_m4"
41 #define METHODNAME5 "STRENGTH_RED_EXAMPLE_m5"
42 #define METHODNAME6 "STRENGTH_RED_EXAMPLE_m6"
43 #define METHODNAME7 "STRENGTH_RED_EXAMPLE_m7"
44 #define METHODNAME8 "STRENGTH_RED_EXAMPLE_m8"
45 #define METHODNAME9 "STRENGTH_RED_EXAMPLE_m9"
46 #define METHODTPNAME "STRENGTH_RED_EXAMPLE_meth_tp"
52 /** The ir_type int. **/
53 #define PRIM_NAME "int"
58 static int arr_pos = 1;
59 static ir_type *typ, *typ2;
61 static ir_node *r1, *f, *r, *c2;
69 * Constructs a new (method-)function of the form
71 * typ fct_name(typ arg) {
72 * for (i = start_value; i < end_value;) { ... }
75 * After return, the loop body is the current block.
77 * @param owner owner-ir_type of this (method-)function
78 * @param mtp the method ir_type of this function
79 * @param fct_name the name of the function
80 * @param loop_dir the loop direction
82 static void function_begin(ir_type *owner, ir_type *mtp, char *fct_name, loop_dir_t loop_dir) {
89 int start_value, end_value;
92 if (loop_dir == loop_forward) {
103 /* The ir_entity for the procedure */
104 ent = new_entity(owner, new_id_from_str(fct_name), mtp);
106 /* make ir_type infromation for the array */
107 array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
109 /* set the bounds for the array */
110 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
112 /* The array is an ir_entity of the owner ir_type */
113 array_ent = new_entity(owner, new_id_from_str("a"), array_type);
115 /** The code of the procedure **/
117 /* Generates start and end blocks and nodes, and a first, initial block */
119 new_ir_graph(ent, NRLOCS);
121 /* The value position used for: */
123 if (fct_name == METHODNAME7)
124 c2 = new_Const_int(5);
126 /* Generate the constant and assign it to b. The assignment is resolved to a
128 set_value(i_pos, new_Const_int(start_value));
130 sym.entity_p = array_ent;
131 set_value(arr_pos, new_SymConst(mode_P, sym, symconst_addr_ent));
134 /* We know all predecessors of the block and all set_values and set_stores are
135 preformed. We can mature the block. */
136 mature_immBlock(get_irg_current_block(current_ir_graph));
138 /* Generate a conditional branch */
140 add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
142 cmp = new_Cmp(new_Const_int(end_value), get_value(i_pos, mode_Is));
143 x = new_Cond(new_Proj(cmp, mode_b, cmp_dir));
145 f = new_Proj(x, mode_X, pn_Cond_false);
146 t = new_Proj(x, mode_X, pn_Cond_true);
148 /* generate and fill the loop body block */
150 add_immBlock_pred(r, t);
156 * finishes a builded function.
158 * @param b the return value
160 static void function_end(ir_node *b) {
161 ir_node *x = new_Jmp();
163 add_immBlock_pred(r1, x);
167 add_immBlock_pred(get_cur_block(), f);
168 mature_immBlock(get_cur_block());
169 /* The Return statement */
171 ir_node *in[1], *store ;
175 x = new_Return(store, 1, in);
177 add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
180 /* finalize the end block generated in new_ir_graph() */
181 mature_immBlock(get_irg_end_block(current_ir_graph));
189 ir_entity *ent, *array_ent, *array_ent2;
190 ir_type *proc_tp, *array_type, *array_type2; /* ir_type information for the method main */
191 ir_node *x,*x1 , *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
192 ir_node *d2, *res2, *res3, *res5, *res7;
195 ir_node *b, *c, *c1, *d, *res;
196 ir_node *b1, *b2, *b3, *b4, *b7, *block;
197 ir_node *mul, *q, *q1;
199 symconst_symbol sym, sym2;
201 printf("\nCreating an IR graph: IF_EXAMPLE...\n");
205 arch_dep_set_opts(arch_dep_none);
207 do_node_verification(FIRM_VERIFICATION_REPORT);
209 typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
211 typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
213 /** The global array variable a **/
216 /** Type information for the procedure **/
217 owner = get_glob_type();
218 /* Type information for the procedure */
219 proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)), NRARGS, NRES);
220 set_method_param_type(proc_tp, 0, typ);
221 set_method_res_type(proc_tp, 0, typ);
224 /* --------------------------------------------------------------------- */
226 /* The ir_entity for the procedure */
227 ent = new_entity(owner,
228 new_id_from_str(METHODNAME1),
230 /* The parameter and result types of the procedure. */
232 /* make ir_type infromation for the array */
233 array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
234 array_type2 = new_type_array(new_id_from_chars("array2", 6),N_DIMS, typ2);
235 /* set the bounds for the array */
236 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
237 set_array_bounds_int(array_type2, 0, L_BOUND, U_BOUND);
239 /* The array is an ir_entity of the global typ */
240 array_ent = new_entity( owner, new_id_from_str("a"), array_type);
241 array_ent2 = new_entity( owner, new_id_from_str("a2"), array_type2);
243 /** The code of the procedure **/
246 /* Generates start and end blocks and nodes, and a first, initial block */
249 irg = new_ir_graph(ent, NRLOCS);
251 /* The value position used for: */
254 /* Generate the constant and assign it to b. The assignment is resovled to a
256 set_value(i_pos, new_Const_int(0));
259 /* We know all predecessors of the block and all set_values and set_stores are
260 preformed. We can mature the block. */
261 mature_immBlock(get_irg_current_block(irg));
263 /* Generate a conditional branch */
265 add_immBlock_pred(get_irg_current_block(irg), x);
266 cmp = new_Cmp(new_Const_int(10), get_value(i_pos, mode_Is));
267 x = new_Cond(new_Proj(cmp, mode_b, pn_Cmp_Gt));
268 f = new_Proj(x, mode_X, pn_Cond_false);
269 t = new_Proj(x, mode_X, pn_Cond_true);
271 /* generate and fill the then block */
273 add_immBlock_pred(r, t);
275 c = new_Const_int(1);
276 b = new_Const_int(4);
277 b2 = new_Const_int(12);
278 sym.entity_p = array_ent ;
279 sym2.entity_p = array_ent2 ;
280 d = new_SymConst(mode_P, sym, symconst_addr_ent);
281 d2 = new_SymConst(mode_P, sym2, symconst_addr_ent);
282 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
283 res2 = new_Add(d2, new_Mul(get_value(i_pos, mode_Is), b2, mode_Is), mode_P);
284 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, pn_Store_M));
285 set_store(new_Proj(new_Store(get_store(), res2, new_Const_int(16)), mode_M, pn_Store_M));
286 d = new_SymConst(mode_P, sym, symconst_addr_ent);
287 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
288 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(15)), mode_M, pn_Store_M));
290 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
295 add_immBlock_pred(r1, x);
299 b1 = new_Const_int(45);
300 add_immBlock_pred(get_irg_current_block(irg), f);
301 cmp = new_Cmp(new_Const_int(0), b1);
302 x = new_Cond(new_Proj(cmp, mode_b, pn_Cmp_Lt));
303 f1 = new_Proj(x, mode_X, pn_Cond_false);
304 t1 = new_Proj(x, mode_X, pn_Cond_true);
306 block = new_immBlock();
307 add_immBlock_pred(block, t1);
308 b1 = new_Sub(b1, get_value(i_pos, mode_Is), mode_Is);
309 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
310 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, pn_Store_M));
311 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
315 mature_immBlock(block);
317 add_immBlock_pred(r2, x1);
320 block = new_immBlock();
321 add_immBlock_pred(block, f1);
322 mature_immBlock(block);
323 /* The Return statement */
325 ir_node *in[1], *store ;
326 in[0] = get_value(i_pos, mode_Is);
329 x = new_Return(store, 1, in);
331 add_immBlock_pred(get_irg_end_block(irg), x);
333 /* finalize the end block generated in new_ir_graph() */
334 mature_immBlock(get_irg_end_block(irg));
337 /* -------------------------------------------------------------------------------- */
339 function_begin(owner, proc_tp, METHODNAME2, loop_forward);
340 q = new_Const_int(15);
341 q1 = new_Const_int(13);
342 c = new_Const_int(1);
343 b = new_Const_int(4);
344 mul = new_Mul(q, get_value(i_pos, mode_Is), mode_Is);
346 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
347 res = new_Add(q1, res, mode_P);
348 set_store(new_Proj(new_Store(get_store(), res, mul), mode_M, pn_Store_M));
350 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
354 /* -------------------------------------------------------------------------- */
356 function_begin(owner, proc_tp, METHODNAME3, loop_backward);
358 c = new_Const_int(1);
359 b = new_Const_int(4);
360 b3 = new_Const_int(8);
362 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
363 res = new_Add(b, res, mode_P);
364 res = new_Add(b3, res, mode_P);
365 res3 = new_Add(b3, res, mode_P);
366 res = new_Add(res3, res, mode_P);
367 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, pn_Store_M));
370 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
374 /* -------------------------------------------------------------------------- */
376 function_begin(owner, proc_tp, METHODNAME4, loop_forward);
378 c = new_Const_int(1);
379 b = new_Const_int(4);
380 b4 = new_Const_int(8);
382 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
383 mul4 = new_Mul(get_value(i_pos, mode_Is), b4, mode_Is);
384 res = new_Add(mul4, get_value(arr_pos, mode_P), mode_P);
385 set_store(new_Proj(new_Store(get_store(), res,get_value(i_pos, mode_Is)),
386 mode_M, pn_Store_M));
387 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
388 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, pn_Store_M));
392 /* -------------------------------------------------------------------------- */
394 function_begin(owner, proc_tp, METHODNAME5, loop_backward);
396 c = new_Const_int(1);
397 b = new_Const_int(4);
399 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
401 res5 = new_Add(c, b, mode_Is);
402 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
403 res = new_Add(res, b, mode_P);
404 res = new_Add(res, res5, mode_P);
405 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, pn_Store_M));
409 /* -------------------------------------------------------------------------- */
411 function_begin(owner, proc_tp, METHODNAME6, loop_forward);
413 c = new_Const_int(1);
414 c1 = new_Const_int(5);
415 b = new_Const_int(4);
417 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
419 res = new_Add( get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is),
420 b, mode_Is), mode_P);
421 res = new_Sub(c1, res, mode_P);
422 res = new_Add( b, res, mode_P);
423 res = new_Add(b, res, mode_P);
424 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, pn_Store_M));
428 /* -------------------------------------------------------------------------- */
430 function_begin(owner, proc_tp, METHODNAME7, loop_backward);
432 c = new_Const_int(1);
433 b = new_Const_int(4);
434 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 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, pn_Store_M));
443 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
446 /* -------------------------------------------------------------------------- */
448 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 construct_backedges(current_ir_graph);
460 dump_ir_block_graph(current_ir_graph, 0);
462 optimize_reassociation(current_ir_graph);
463 opt_osr(current_ir_graph, osr_flag_default);
466 remove_critical_cf_edges(current_ir_graph);
467 set_opt_global_cse(1);
468 place_code(current_ir_graph);
469 set_opt_global_cse(0);
470 optimize_reassociation(current_ir_graph);
473 dump_loop_tree(current_ir_graph, "");
474 dump_ir_block_graph(current_ir_graph, "-strength_reduced");
476 printf("Use ycomp to view the graphs\n");