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 CLASSNAME "STRENGTH_RED_EXAMPLE"
38 #define METHODNAME1 "STRENGTH_RED_EXAMPLE_m1"
39 #define METHODNAME2 "STRENGTH_RED_EXAMPLE_m2"
40 #define METHODNAME3 "STRENGTH_RED_EXAMPLE_m3"
41 #define METHODNAME4 "STRENGTH_RED_EXAMPLE_m4"
42 #define METHODNAME5 "STRENGTH_RED_EXAMPLE_m5"
43 #define METHODNAME6 "STRENGTH_RED_EXAMPLE_m6"
44 #define METHODNAME7 "STRENGTH_RED_EXAMPLE_m7"
45 #define METHODNAME8 "STRENGTH_RED_EXAMPLE_m8"
46 #define METHODNAME9 "STRENGTH_RED_EXAMPLE_m9"
47 #define METHODTPNAME "STRENGTH_RED_EXAMPLE_meth_tp"
54 #define PRIM_NAME "int"
59 static int arr_pos = 1;
60 static type *typ, *typ2;
62 static ir_node *r1, *f, *r, *c2;
69 static void function_begin(type *owner, type *mtp, char *fct_name, loop_dir_t loop_dir) {
72 /* The entity for the procedure */
73 entity *ent = new_entity (owner, new_id_from_str (fct_name), mtp);
74 /* The parameter and result types of the procedure. */
75 set_method_param_type(mtp, 0, typ);
76 set_method_res_type(mtp, 0, typ);
78 /* make type infromation for the array */
79 type *array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
81 /* set the bounds for the array */
82 set_array_bounds(array_type, 0,
83 new_Const(mode_Iu, new_tarval_from_long (L_BOUND, mode_Iu)),
84 new_Const(mode_Iu, new_tarval_from_long (U_BOUND, mode_Iu)));
85 /* The array is an entity of the global typ */
86 entity *array_ent = new_entity( owner, new_id_from_chars("a", 1), array_type);
88 /** The code of the procedure **/
90 /* Generates start and end blocks and nodes, and a first, initial block */
92 new_ir_graph (ent, NRLOCS);
94 /* The value position used for: */
96 if(fct_name == METHODNAME7)
97 c2 = new_Const (mode_Is, new_tarval_from_long (5, mode_Is));
99 /* Generate the constant and assign it to b. The assignment is resolved to a
101 if (loop_dir == loop_forward) {
102 set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
104 set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (10, mode_Is)));
106 sym.entity_p = array_ent ;
107 set_value (arr_pos, new_SymConst(sym, symconst_addr_ent));
110 /* We know all predecessors of the block and all set_values and set_stores are
111 preformed. We can mature the block. */
112 mature_immBlock (get_irg_current_block(current_ir_graph));
114 /* Generate a conditional branch */
116 add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
118 if (loop_dir == loop_forward) {
119 cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(10, mode_Is)),
120 get_value(i_pos, mode_Is));
121 x = new_Cond (new_Proj(cmp, mode_b, Gt));
123 cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(0, mode_Is)),
124 get_value(i_pos, mode_Is));
125 x = new_Cond (new_Proj(cmp, mode_b, Lt));
127 f = new_Proj (x, mode_X, 0);
128 t = new_Proj (x, mode_X, 1);
130 /* generate and fill the loop body block */
132 add_immBlock_pred (r, t);
138 static void function_end(ir_node *b) {
139 ir_node *x = new_Jmp ();
141 add_immBlock_pred(r1, x);
145 add_immBlock_pred(get_cur_block(), f);
146 mature_immBlock (get_cur_block());
147 /* The Return statement */
149 ir_node *in[1], *store ;
153 x = new_Return (store, 1, in);
155 add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
157 mature_immBlock (r1);
158 /* finalize the end block generated in new_ir_graph() */
159 mature_immBlock (get_irg_end_block(current_ir_graph));
167 entity *ent, *array_ent, *array_ent2;
168 type *proc_tp, *array_type, *array_type2; /* type information for the method main */
169 ir_node *x,*x1 , *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
172 printf("\nCreating an IR graph: IF_EXAMPLE...\n");
176 arch_dep_set_opts(arch_dep_none);
178 do_node_verification(NODE_VERIFICATION_REPORT);
180 typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
182 typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
184 /** The global array variable a **/
187 /** Type information for the procedure **/
188 owner = get_glob_type();
189 /* Type information for the procedure */
190 proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)),
192 set_method_param_type(proc_tp, 0, typ);
193 set_method_res_type(proc_tp, 0, typ);
196 /* --------------------------------------------------------------------- */
198 /* The entity for the procedure */
199 ent = new_entity (owner,
200 new_id_from_str (METHODNAME1),
202 /* The parameter and result types of the procedure. */
204 /* make type infromation for the array */
205 array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
206 array_type2 = new_type_array(new_id_from_chars("array2", 6),N_DIMS, typ2);
207 /* set the bounds for the array */
208 set_array_bounds(array_type, 0,
209 new_Const(mode_Iu, new_tarval_from_long (L_BOUND, mode_Iu)),
210 new_Const(mode_Iu, new_tarval_from_long (U_BOUND, mode_Iu)));
211 set_array_bounds(array_type2, 0,
212 new_Const(mode_Iu, new_tarval_from_long (L_BOUND, mode_Iu)),
213 new_Const(mode_Iu, new_tarval_from_long (U_BOUND, mode_Iu)));
215 /* The array is an entity of the global typ */
216 array_ent = new_entity( owner, new_id_from_chars("a", 1), array_type);
217 array_ent2 = new_entity( owner, new_id_from_chars("a2", 2), array_type2);
219 /** The code of the procedure **/
222 /* Generates start and end blocks and nodes, and a first, initial block */
225 irg = new_ir_graph (ent, NRLOCS);
227 /* The value position used for: */
230 /* Generate the constant and assign it to b. The assignment is resovled to a
232 set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
235 /* We know all predecessors of the block and all set_values and set_stores are
236 preformed. We can mature the block. */
237 mature_immBlock (get_irg_current_block(irg));
239 /* Generate a conditional branch */
241 add_immBlock_pred(get_irg_current_block(irg), x);
242 cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(10, mode_Is)),
243 get_value(i_pos, mode_Is));
244 x = new_Cond (new_Proj(cmp, mode_b, Gt));
245 f = new_Proj (x, mode_X, 0);
246 t = new_Proj (x, mode_X, 1);
248 /* generate and fill the then block */
250 add_immBlock_pred (r, t);
252 ir_node *b, *c, *d, *res;
253 symconst_symbol sym, sym2;
254 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
255 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
256 ir_node *b2 = new_Const (mode_Is, new_tarval_from_long (12, mode_Is));
257 sym.entity_p = array_ent ;
258 sym2.entity_p = array_ent2 ;
259 d = new_SymConst(sym, symconst_addr_ent);
260 ir_node *d2 = new_SymConst(sym2, symconst_addr_ent);
261 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
262 //ir_node *res2 = new_Add(d2, get_value(i_pos, mode_Is), mode_P);
263 ir_node *res2 = new_Add(d2, new_Mul(get_value(i_pos, mode_Is), b2, mode_Is), mode_P);
264 //res2 = new_Add(res2, new_Const (mode_Is, new_tarval_from_long (12, mode_Is)), mode_P);
265 set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
266 new_tarval_from_long (19,mode_Is))),
268 set_store (new_Proj (new_Store (get_store (), res2, new_Const (mode_Is,
269 new_tarval_from_long (16,mode_Is))),
271 d = new_SymConst(sym, symconst_addr_ent);
272 res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
273 set_store (new_Proj (new_Store (get_store (), res, new_Const
274 (mode_Is, new_tarval_from_long (15,mode_Is))),
277 set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c , mode_Is));
282 add_immBlock_pred(r1, x);
283 mature_immBlock (r1);
286 ir_node *b1 = new_Const (mode_Is, new_tarval_from_long (45, mode_Is));
287 add_immBlock_pred(get_irg_current_block(irg), f);
288 cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(0, mode_Is)), b1);
289 x = new_Cond (new_Proj(cmp, mode_b, 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 (mode_Is,
298 new_tarval_from_long (19, mode_Is))), mode_M, 0));
299 set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c , mode_Is));
303 mature_immBlock (block);
305 add_immBlock_pred(r2, x1);
306 mature_immBlock (r2);
308 block = new_immBlock();
309 add_immBlock_pred(block, f1);
310 mature_immBlock (block);
311 /* The Return statement */
313 ir_node *in[1], *store ;
314 in[0] = get_value (i_pos, mode_Is);
317 x = new_Return (store, 1, in);
319 add_immBlock_pred(get_irg_end_block(irg), x);
321 /* finalize the end block generated in new_ir_graph() */
322 mature_immBlock (get_irg_end_block(irg));
325 /* -------------------------------------------------------------------------------- */
327 function_begin(owner, proc_tp, METHODNAME2, loop_forward);
329 q = new_Const (mode_Is, new_tarval_from_long (15, mode_Is));
330 ir_node *q1 = new_Const (mode_Is, new_tarval_from_long (13, mode_Is));
331 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
332 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
333 mul = new_Mul(q, get_value(i_pos, mode_Is), mode_Is);
335 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
336 res = new_Add(q1, res, mode_P);
337 set_store (new_Proj (new_Store (get_store (), res, mul),
340 set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
344 /* -------------------------------------------------------------------------- */
346 function_begin(owner, proc_tp, METHODNAME3, loop_backward);
348 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
349 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
350 ir_node *b3 = new_Const (mode_Is, new_tarval_from_long (8, mode_Is));
353 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
354 res = new_Add(b, res, mode_P);
355 res = new_Add(b3, res, mode_P);
356 ir_node *res3 = new_Add(b3, res, mode_P);
357 res = new_Add(res3, res, mode_P);
358 set_store (new_Proj (new_Store (get_store (), res, get_value(i_pos, mode_Is)), mode_M, 0));
361 set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
365 /* -------------------------------------------------------------------------- */
367 function_begin(owner, proc_tp, METHODNAME4, loop_forward);
369 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
370 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
371 ir_node *b4 = new_Const (mode_Is, new_tarval_from_long (8, mode_Is));
373 set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
374 ir_node *mul4 = new_Mul(get_value(i_pos, mode_Is), b4, mode_Is);
375 res = new_Add(mul4, get_value(arr_pos, mode_P), mode_P);
376 set_store (new_Proj (new_Store (get_store (), res,get_value(i_pos, mode_Is)),
378 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
379 set_store (new_Proj (new_Store (get_store (), res,get_value(i_pos, mode_Is)),
384 /* -------------------------------------------------------------------------- */
386 function_begin(owner, proc_tp, METHODNAME5, loop_backward);
388 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
389 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
391 set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
393 ir_node * res5 = new_Add (c, b, mode_Is);
394 res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
395 res = new_Add(res, b, mode_P);
396 res = new_Add(res, res5, mode_P);
397 set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
398 new_tarval_from_long (19, mode_Is))),
403 /* -------------------------------------------------------------------------- */
405 function_begin(owner, proc_tp, METHODNAME6, loop_forward);
407 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
408 ir_node *c1 = new_Const (mode_Is, new_tarval_from_long (5, mode_Is));
409 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
412 set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
414 res = new_Add( get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is),
415 b, mode_Is), mode_P);
416 res = new_Sub(c1, res, mode_P);
417 res = new_Add( b, res, mode_P);
418 res = new_Add(b, res, mode_P);
419 set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
420 new_tarval_from_long (19, mode_Is))),
425 /* -------------------------------------------------------------------------- */
427 function_begin(owner, proc_tp, METHODNAME7, loop_backward);
429 c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
430 b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
431 ir_node *b7 = new_Const (mode_Is,
432 new_tarval_from_long (19, mode_Is));
437 res = get_value(i_pos, mode_Is);
438 res = new_Add(res, b, mode_Is);
439 res = new_Add(res, b7, mode_Is);
440 res = new_Mul(res, b, mode_Is);
441 res = new_Add(get_value(arr_pos, mode_P), res, mode_P);
442 ir_node *res7 = new_Add( get_value(i_pos, mode_Is), b7, mode_Is);
443 set_store (new_Proj (new_Store (get_store (), res, res7),
445 set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
448 /* -------------------------------------------------------------------------- */
450 int i, n_irgs = get_irp_n_irgs();
452 printf("Done building the graph. Dumping and optimizing it.\n");
453 dump_consts_local(1);
454 turn_off_edge_labels();
455 for (i = 0; i < n_irgs; ++i) {
456 current_ir_graph = get_irp_irg(i);
457 irg_vrfy(current_ir_graph);
458 finalize_cons (current_ir_graph);
460 /* output the vcg file */
461 //dump_ir_block_graph (current_ir_graph, "-early");
462 construct_backedges(current_ir_graph);
463 dump_ir_block_graph (current_ir_graph, 0);
465 set_opt_strength_red_verbose(2);
466 set_firm_verbosity(2);
467 optimize_reassociation(current_ir_graph);
468 reduce_strength(current_ir_graph);
470 // remove_critical_cf_edges(current_ir_graph);
471 //set_opt_global_cse(1);
472 //place_code(current_ir_graph);
473 //set_opt_global_cse(0);
474 // optimize_reassociation(current_ir_graph);
476 dump_loop_tree(current_ir_graph, "");
477 dump_ir_block_graph (current_ir_graph, "-strength_reduced");
479 //printf("use xvcg to view this graph:\n");
480 //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");