4 * File name: testprograms/loop_unroll_exapmle.c
5 * Purpose: Shows how loopunrolling works
6 * Author: Beyhan Veliev
11 * Copyright: (c) 2004 Universität Karlsruhe
12 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
23 #include "loop_unrolling.h"
26 #define new_Const_int(n) new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
29 #define CLASSNAME "LOOP_UNROLL_EXAMPLE"
30 #define METHODNAME1 "LOOP_UNROLL_EXAMPLE_m1"
31 #define METHODNAME2 "LOOP_UNROLL_EXAMPLE_m2"
32 #define METHODNAME3 "LOOP_UNROLL_EXAMPLE_m3"
33 #define METHODNAME4 "LOOP_UNROLL_EXAMPLE_m4"
34 #define METHODNAME5 "LOOP_UNROLL_EXAMPLE_m5"
35 #define METHODNAME6 "LOOP_UNROLL_EXAMPLE_m6"
36 #define METHODNAME7 "LOOP_UNROLL_EXAMPLE_m7"
37 #define METHODNAME8 "LOOP_UNROLL_EXAMPLE_m8"
38 #define METHODNAME9 "LOOP_UNROLL_EXAMPLE_m9"
39 #define METHODTPNAME "LOOP_UNROLL_EXAMPLE_meth_tp"
46 #define PRIM_NAME "int"
51 static int arr_pos = 1;
52 static type *typ, *typ2;
54 static ir_node *r1, *f, *r, *c2;
62 * Constructs a new (method-)function of the form
64 * typ fct_name(typ arg) {
65 * for (i = start_value; i < end_value;) { ... }
68 * After return, the loop body is the current block.
70 * @param owner owner-type of this (method-)function
71 * @param mtp the method type of this function
72 * @param fct_name the name of the function
73 * @param loop_dir the loop direction
75 static void function_begin(type *owner, type *mtp, char *fct_name, loop_dir_t loop_dir) {
79 int start_value, end_value;
82 if (loop_dir == loop_forward) {
93 /* The entity for the procedure */
94 entity *ent = new_entity (owner, new_id_from_str(fct_name), mtp);
96 /* make type infromation for the array */
97 type *array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
99 /* set the bounds for the array */
100 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
102 /* The array is an entity of the owner type */
103 entity *array_ent = new_entity(owner, new_id_from_str("a"), array_type);
105 /** The code of the procedure **/
107 /* Generates start and end blocks and nodes, and a first, initial block */
109 new_ir_graph(ent, NRLOCS);
111 /* The value position used for: */
113 if (fct_name == METHODNAME7)
114 c2 = new_Const_int(5);
116 /* Generate the constant and assign it to b. The assignment is resolved to a
118 set_value(i_pos, new_Const_int(start_value));
120 sym.entity_p = array_ent;
121 set_value(arr_pos, new_SymConst(sym, symconst_addr_ent));
124 /* We know all predecessors of the block and all set_values and set_stores are
125 preformed. We can mature the block. */
126 mature_immBlock(get_irg_current_block(current_ir_graph));
128 /* Generate a conditional branch */
130 add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
132 cmp = new_Cmp(new_Const_int(end_value), get_value(i_pos, mode_Is));
133 x = new_Cond(new_Proj(cmp, mode_b, cmp_dir));
135 f = new_Proj(x, mode_X, 0);
136 t = new_Proj(x, mode_X, 1);
138 /* generate and fill the loop body block */
140 add_immBlock_pred(r, t);
146 * finishes a builded function.
148 * @param b the return value
150 static void function_end(ir_node *b) {
151 ir_node *x = new_Jmp();
153 add_immBlock_pred(r1, x);
157 add_immBlock_pred(get_cur_block(), f);
158 mature_immBlock (get_cur_block());
159 /* The Return statement */
161 ir_node *in[1], *store ;
165 x = new_Return(store, 1, in);
167 add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
170 /* finalize the end block generated in new_ir_graph() */
171 mature_immBlock(get_irg_end_block(current_ir_graph));
179 entity *ent, *array_ent, *array_ent2;
180 type *proc_tp, *array_type, *array_type2; /* type information for the method main */
181 ir_node *x,*x1 , *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
184 printf("\nCreating an IR graph: IF_EXAMPLE...\n");
188 arch_dep_set_opts(arch_dep_none);
190 do_node_verification(NODE_VERIFICATION_REPORT);
192 typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
194 typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
196 /** The global array variable a **/
199 /** Type information for the procedure **/
200 owner = get_glob_type();
201 /* Type information for the procedure */
202 proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)), NRARGS, NRES);
203 set_method_param_type(proc_tp, 0, typ);
204 set_method_res_type(proc_tp, 0, typ);
207 /* --------------------------------------------------------------------- */
209 /* The entity for the procedure */
210 ent = new_entity (owner,
211 new_id_from_str (METHODNAME1),
213 /* The parameter and result types of the procedure. */
215 /* make type infromation for the array */
216 array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
217 array_type2 = new_type_array(new_id_from_chars("array2", 6),N_DIMS, typ2);
218 /* set the bounds for the array */
219 set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
220 set_array_bounds_int(array_type2, 0, L_BOUND, U_BOUND);
222 /* The array is an entity of the global typ */
223 array_ent = new_entity( owner, new_id_from_str("a"), array_type);
224 array_ent2 = new_entity( owner, new_id_from_str("a2"), array_type2);
226 /** The code of the procedure **/
229 /* Generates start and end blocks and nodes, and a first, initial block */
232 irg = new_ir_graph(ent, NRLOCS);
234 /* The value position used for: */
237 /* Generate the constant and assign it to b. The assignment is resovled to a
239 set_value (i_pos, new_Const_int(0));
242 /* We know all predecessors of the block and all set_values and set_stores are
243 preformed. We can mature the block. */
244 mature_immBlock (get_irg_current_block(irg));
246 /* Generate a conditional branch */
248 add_immBlock_pred(get_irg_current_block(irg), x);
249 cmp = new_Cmp(new_Const_int(10), get_value(i_pos, mode_Is));
250 x = new_Cond(new_Proj(cmp, mode_b, pn_Cmp_Gt));
251 f = new_Proj(x, mode_X, 0);
252 t = new_Proj(x, mode_X, 1);
254 /* generate and fill the then block */
256 add_immBlock_pred (r, t);
258 ir_node *b, *c, *d, *res;
259 symconst_symbol sym, sym2;
260 c = new_Const_int(1);
261 b = new_Const_int(4);
262 ir_node *b2 = new_Const_int(12);
263 sym.entity_p = array_ent ;
264 sym2.entity_p = array_ent2 ;
265 d = new_SymConst(sym, symconst_addr_ent);
266 ir_node *d2 = new_SymConst(sym2, symconst_addr_ent);
267 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
268 //ir_node *res2 = new_Add(d2, get_value(i_pos, mode_Is), mode_P);
269 ir_node *res2 = new_Add(d2, new_Mul(get_value(i_pos, mode_Is), b2, mode_Is), mode_P);
270 //res2 = new_Add(res2, new_Const_int(12), mode_P);
271 set_store (new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
272 set_store (new_Proj(new_Store(get_store(), res2, new_Const_int(16)), mode_M, 0));
273 d = new_SymConst(sym, symconst_addr_ent);
274 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
275 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(15)), mode_M, 0));
277 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
282 add_immBlock_pred(r1, x);
286 ir_node *b1 = new_Const_int(45);
287 add_immBlock_pred(get_irg_current_block(irg), f);
288 cmp = new_Cmp(new_Const_int(0), b1);
289 x = new_Cond (new_Proj(cmp, mode_b, pn_Cmp_Lt));
290 f1 = new_Proj (x, mode_X, 0);
291 t1 = new_Proj (x, mode_X, 1);
293 ir_node *block = new_immBlock();
294 add_immBlock_pred(block, t1);
295 b1 = new_Sub (b1, get_value(i_pos, mode_Is), mode_Is);
296 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
297 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
298 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
302 mature_immBlock(block);
304 add_immBlock_pred(r2, x1);
307 block = new_immBlock();
308 add_immBlock_pred(block, f1);
309 mature_immBlock(block);
310 /* The Return statement */
312 ir_node *in[1], *store ;
313 in[0] = get_value(i_pos, mode_Is);
316 x = new_Return(store, 1, in);
318 add_immBlock_pred(get_irg_end_block(irg), x);
320 /* finalize the end block generated in new_ir_graph() */
321 mature_immBlock(get_irg_end_block(irg));
324 /* -------------------------------------------------------------------------------- */
326 function_begin(owner, proc_tp, METHODNAME2, loop_forward);
328 q = new_Const_int(15);
329 c = new_Const_int(5);
330 b = new_Const_int(4);
332 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
333 set_store(new_Proj(new_Store (get_store(), res, q), mode_M, 0));
335 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
339 /* -------------------------------------------------------------------------- */
341 function_begin(owner, proc_tp, METHODNAME3, loop_backward);
343 c = new_Const_int(1);
344 b = new_Const_int(4);
345 ir_node *b3 = new_Const_int(8);
347 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
348 res = new_Add(b, res, mode_P);
349 res = new_Add(b3, res, mode_P);
350 ir_node *res3 = new_Add(b3, res, mode_P);
351 res = new_Add(res3, res, mode_P);
352 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
355 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
359 /* -------------------------------------------------------------------------- */
361 function_begin(owner, proc_tp, METHODNAME4, loop_forward);
363 c = new_Const_int(1);
364 b = new_Const_int(4);
365 ir_node *b4 = new_Const_int(8);
367 set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
368 ir_node *mul4 = new_Mul(get_value(i_pos, mode_Is), b4, mode_Is);
369 res = new_Add(mul4, get_value(arr_pos, mode_P), mode_P);
370 set_store (new_Proj (new_Store (get_store (), res,get_value(i_pos, mode_Is)),
372 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
373 set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
377 /* -------------------------------------------------------------------------- */
379 function_begin(owner, proc_tp, METHODNAME5, loop_backward);
381 c = new_Const_int(1);
382 b = new_Const_int(4);
384 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
386 ir_node * res5 = new_Add (c, b, mode_Is);
387 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
388 res = new_Add(res, b, mode_P);
389 res = new_Add(res, res5, mode_P);
390 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
394 /* -------------------------------------------------------------------------- */
396 function_begin(owner, proc_tp, METHODNAME6, loop_forward);
398 c = new_Const_int(1);
399 ir_node *c1 = new_Const_int(5);
400 b = new_Const_int(4);
402 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
404 res = new_Add( get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is),
405 b, mode_Is), mode_P);
406 res = new_Sub(c1, res, mode_P);
407 res = new_Add( b, res, mode_P);
408 res = new_Add(b, res, mode_P);
409 set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
413 /* -------------------------------------------------------------------------- */
415 function_begin(owner, proc_tp, METHODNAME7, loop_backward);
417 c = new_Const_int(1);
418 b = new_Const_int(4);
419 ir_node *b7 = new_Const_int(19);
422 res = get_value(i_pos, mode_Is);
423 res = new_Add(res, b, mode_Is);
424 res = new_Add(res, b7, mode_Is);
425 res = new_Mul(res, b, mode_Is);
426 res = new_Add(get_value(arr_pos, mode_P), res, mode_P);
427 ir_node *res7 = new_Add( get_value(i_pos, mode_Is), b7, mode_Is);
428 set_store(new_Proj(new_Store(get_store(), res, res7), mode_M, 0));
429 set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
432 /* -------------------------------------------------------------------------- */
434 int i, n_irgs = get_irp_n_irgs();
436 printf("Done building the graph. Dumping and optimizing it.\n");
437 dump_consts_local(1);
438 turn_off_edge_labels();
441 #if 1 /* Use this version for testing. Loop unrolling creates random node numbers,
442 therefore we can not compare test graphs. */
443 for (i = 0; i < n_irgs; ++i) {
444 current_ir_graph = get_irp_irg(i);
445 irg_vrfy(current_ir_graph);
446 irg_finalize_cons (current_ir_graph);
448 construct_backedges(current_ir_graph);
450 set_opt_strength_red_verbose(2);
451 set_firm_verbosity(2);
453 set_opt_loop_unrolling(1);
454 optimize_loop_unrolling(current_ir_graph);
456 irg_vrfy(current_ir_graph);
459 for (i = 0; i < n_irgs; ++i) {
460 current_ir_graph = get_irp_irg(i);
461 irg_vrfy(current_ir_graph);
462 irg_finalize_cons (current_ir_graph);
464 /* output the vcg file */
465 dump_ir_block_graph (current_ir_graph, 0);
467 construct_backedges(current_ir_graph);
468 dump_ir_graph (current_ir_graph, 0);
470 set_opt_strength_red_verbose(2);
471 set_firm_verbosity(2);
473 set_opt_loop_unrolling(1);
474 optimize_loop_unrolling(current_ir_graph);
475 // optimize_reassociation(current_ir_graph);
476 //reduce_strength(current_ir_graph);
479 // remove_critical_cf_edges(current_ir_graph);
480 //set_opt_global_cse(1);
481 //place_code(current_ir_graph);
482 //set_opt_global_cse(0);
483 dump_loop_tree(current_ir_graph, "");
484 dump_ir_block_graph (current_ir_graph, "-loop-unrolling");
485 // dump_ir_graph (current_ir_graph, "-pure-loop-unrolling");
488 //printf("use xvcg to view this graph:\n");
489 //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");