nsz Git - libfirm/blob - testprograms/loop_unroll_example.c

   1
   2 /*
   3  * Project:     libFIRM
   4  * File name:   testprograms/loop_unroll_exapmle.c
   5  * Purpose:     Shows how loopunrolling works
   6  * Author:      Beyhan Veliev
   7  * Modified by:
   8  * Created:
   9  * CVS-ID:      $Id$
  10  *
  11  * Copyright:   (c) 2004 Universität Karlsruhe
  12  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15 # include <stdio.h>
  16 # include <string.h>
  17 # include <reassoc.h>
  18 # include "firm.h"
  19
  20 # include "irvrfy.h"
  21 # include "irdump.h"
  22
  23 #include "loop_unrolling.h"
  24
  25
  26 #define new_Const_int(n)        new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
  27
  28
  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"
  40 #define NRARGS 1
  41 #define NRES 1
  42 #define L_BOUND 0
  43 #define U_BOUND 10
  44 #define N_DIMS 1
  45   /** The type int.   **/
  46 #define PRIM_NAME "int"
  47
  48
  49
  50 static int i_pos = 0;
  51 static int arr_pos = 1;
  52 static ir_type *typ, *typ2;
  53
  54 static ir_node *r1, *f, *r, *c2;
  55
  56 typedef enum {
  57   loop_forward,
  58   loop_backward,
  59 } loop_dir_t;
  60
  61 /**
  62  * Constructs a new (method-)function of the form
  63  *
  64  * typ fct_name(typ arg) {
  65  *   for (i = start_value; i < end_value;) { ... }
  66  * }
  67  *
  68  * After return, the loop body is the current block.
  69  *
  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
  74  */
  75 static void function_begin(ir_type *owner, ir_type *mtp, char *fct_name, loop_dir_t loop_dir) {
  76   symconst_symbol sym;
  77   ir_node *x, *t, *cmp;
  78
  79   int start_value, end_value;
  80   pn_Cmp cmp_dir;
  81
  82   if (loop_dir == loop_forward) {
  83     start_value = 0;
  84     end_value   = 11;
  85     cmp_dir     = pn_Cmp_Ge;
  86   }
  87   else {
  88     start_value = 10;
  89     end_value   = 0;
  90     cmp_dir     = pn_Cmp_Lt;
  91   }
  92
  93   /* The entity for the procedure */
  94   entity *ent = new_entity (owner,  new_id_from_str(fct_name), mtp);
  95
  96   /* make type infromation for the array */
  97   ir_type *array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
  98
  99   /* set the bounds for the array */
 100   set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
 101
 102   /* The array is an entity of the owner type */
 103   entity *array_ent = new_entity(owner, new_id_from_str("a"), array_type);
 104
 105   /** The code of the procedure **/
 106
 107   /* Generates start and end blocks and nodes, and a first, initial block */
 108 #define NRLOCS 2
 109   new_ir_graph(ent, NRLOCS);
 110
 111   /* The value position used for: */
 112   i_pos = 0;
 113   if (fct_name == METHODNAME7)
 114     c2 = new_Const_int(5);
 115
 116   /* Generate the constant and assign it to b. The assignment is resolved to a
 117      dataflow edge. */
 118   set_value(i_pos, new_Const_int(start_value));
 119
 120   sym.entity_p = array_ent;
 121   set_value(arr_pos, new_SymConst(sym, symconst_addr_ent));
 122   x = new_Jmp();
 123
 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));
 127
 128   /* Generate a conditional branch */
 129   r1 = new_immBlock();
 130   add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
 131
 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));
 134
 135   f = new_Proj(x, mode_X, 0);
 136   t = new_Proj(x, mode_X, 1);
 137
 138   /* generate and fill the loop body block */
 139   r = new_immBlock();
 140   add_immBlock_pred(r, t);
 141 }
 142
 143 int x;
 144
 145 /**
 146  * finishes a builded function.
 147  *
 148  * @param b   the return value
 149  */
 150 static void function_end(ir_node *b) {
 151   ir_node *x = new_Jmp();
 152   mature_immBlock (r);
 153   add_immBlock_pred(r1, x);
 154
 155
 156   new_immBlock();
 157   add_immBlock_pred(get_cur_block(), f);
 158   mature_immBlock (get_cur_block());
 159   /* The Return statement */
 160   {
 161     ir_node *in[1], *store ;
 162     in[0] = b;
 163     store = get_store();
 164
 165      x = new_Return(store, 1, in);
 166   }
 167   add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
 168
 169   mature_immBlock(r1);
 170   /* finalize the end block generated in new_ir_graph() */
 171   mature_immBlock(get_irg_end_block(current_ir_graph));
 172 }
 173
 174 int
 175 main(void)
 176 {
 177   ir_graph *irg;
 178   ir_type *owner;
 179   entity *ent, *array_ent, *array_ent2;
 180   ir_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;
 182   int i_pos;
 183
 184   printf("\nCreating an IR graph: IF_EXAMPLE...\n");
 185
 186   init_firm (NULL);
 187
 188   arch_dep_set_opts(arch_dep_none);
 189
 190   do_node_verification(FIRM_VERIFICATION_REPORT);
 191
 192   typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 193
 194   typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 195
 196   /** The global array variable a **/
 197
 198
 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);
 205
 206
 207   /* --------------------------------------------------------------------- */
 208
 209   /* The entity for the procedure */
 210   ent = new_entity (owner,
 211                     new_id_from_str (METHODNAME1),
 212                     proc_tp);
 213   /* The parameter and result types of the procedure. */
 214
 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);
 221
 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);
 225
 226   /** The code of the procedure **/
 227
 228
 229   /* Generates start and end blocks and nodes, and a first, initial block */
 230 #undef NRLOCS
 231 #define NRLOCS 1
 232   irg = new_ir_graph(ent, NRLOCS);
 233
 234   /* The value position used for: */
 235   i_pos = 0;
 236
 237   /* Generate the constant and assign it to b. The assignment is resovled to a
 238      dataflow edge. */
 239   set_value (i_pos, new_Const_int(0));
 240   x = new_Jmp ();
 241
 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));
 245
 246   /* Generate a conditional branch */
 247   r1 = new_immBlock();
 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);
 253
 254   /* generate and fill the then block */
 255   r = new_immBlock ();
 256   add_immBlock_pred (r, t);
 257
 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));
 276
 277   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 278
 279   x = new_Jmp();
 280   mature_immBlock(r);
 281
 282   add_immBlock_pred(r1, x);
 283   mature_immBlock(r1);
 284
 285   r2 = new_immBlock();
 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);
 292
 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));
 299
 300   x1 = new_Jmp();
 301
 302   mature_immBlock(block);
 303
 304   add_immBlock_pred(r2, x1);
 305   mature_immBlock(r2);
 306
 307   block = new_immBlock();
 308   add_immBlock_pred(block, f1);
 309   mature_immBlock(block);
 310   /* The Return statement */
 311   {
 312     ir_node *in[1], *store ;
 313     in[0] = get_value(i_pos, mode_Is);
 314     store = get_store();
 315
 316      x = new_Return(store, 1, in);
 317   }
 318   add_immBlock_pred(get_irg_end_block(irg), x);
 319
 320   /* finalize the end block generated in new_ir_graph() */
 321   mature_immBlock(get_irg_end_block(irg));
 322
 323
 324   /* -------------------------------------------------------------------------------- */
 325
 326   function_begin(owner, proc_tp, METHODNAME2, loop_forward);
 327   ir_node *q;
 328   q =  new_Const_int(15);
 329   c = new_Const_int(5);
 330   b = new_Const_int(4);
 331
 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));
 334
 335   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 336
 337   function_end(b);
 338
 339   /* -------------------------------------------------------------------------- */
 340
 341   function_begin(owner, proc_tp, METHODNAME3, loop_backward);
 342
 343   c = new_Const_int(1);
 344   b = new_Const_int(4);
 345   ir_node *b3 = new_Const_int(8);
 346
 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));
 353
 354
 355   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 356
 357   function_end(b);
 358
 359   /* -------------------------------------------------------------------------- */
 360
 361   function_begin(owner, proc_tp, METHODNAME4, loop_forward);
 362
 363   c = new_Const_int(1);
 364   b = new_Const_int(4);
 365   ir_node *b4 = new_Const_int(8);
 366
 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)),
 371                        mode_M, 0));
 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));
 374
 375   function_end(b);
 376
 377   /* -------------------------------------------------------------------------- */
 378
 379   function_begin(owner, proc_tp, METHODNAME5, loop_backward);
 380
 381   c = new_Const_int(1);
 382   b = new_Const_int(4);
 383
 384   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 385
 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));
 391
 392   function_end(b);
 393
 394   /* -------------------------------------------------------------------------- */
 395
 396   function_begin(owner, proc_tp, METHODNAME6, loop_forward);
 397
 398   c = new_Const_int(1);
 399   ir_node *c1 = new_Const_int(5);
 400   b = new_Const_int(4);
 401
 402   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 403
 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));
 410
 411   function_end(b);
 412
 413   /* -------------------------------------------------------------------------- */
 414
 415   function_begin(owner, proc_tp, METHODNAME7, loop_backward);
 416
 417   c = new_Const_int(1);
 418   b = new_Const_int(4);
 419   ir_node *b7 = new_Const_int(19);
 420
 421   // a[i] = a[i+4]
 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));
 430   function_end(b);
 431
 432   /* -------------------------------------------------------------------------- */
 433
 434   int i, n_irgs = get_irp_n_irgs();
 435
 436   printf("Done building the graph.  Dumping and optimizing it.\n");
 437   dump_consts_local(1);
 438   turn_off_edge_labels();
 439
 440
 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);
 447
 448     construct_backedges(current_ir_graph);
 449
 450     set_opt_strength_red_verbose(2);
 451     set_firm_verbosity(2);
 452     set_optimize(0);
 453     set_opt_loop_unrolling(1);
 454     optimize_loop_unrolling(current_ir_graph);
 455
 456     irg_vrfy(current_ir_graph);
 457   }
 458 #else
 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);
 463
 464     /* output the vcg file */
 465     dump_ir_block_graph (current_ir_graph, 0);
 466
 467     construct_backedges(current_ir_graph);
 468     dump_ir_graph (current_ir_graph, 0);
 469     dump_all_types(0);
 470     set_opt_strength_red_verbose(2);
 471     set_firm_verbosity(2);
 472     set_optimize(0);
 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);
 477
 478
 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");
 486   }
 487 #endif
 488   //printf("use xvcg to view this graph:\n");
 489   //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");
 490
 491   return (0);
 492 }