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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   testprograms/strength_red_example.c
   4  * Purpose:     Shows how strength red works
   5  * Author:      Beyhan Veliev
   6  * Modified by:
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16 #include <libfirm/firm.h>
  17
  18 /**
  19 *  This file constructs the ir for the following pseudo-program:
  20 *
  21 *  int a[10];
  22 *
  23 *  void main(void) {
  24 *    int i = 0;
  25 *
  26 *    while (i < 10)  {
  27 *       a[i] = 19;
  28 *       i++
  29 *    }
  30 *  }
  31 **/
  32
  33 #define new_Const_int(n)        new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
  34
  35
  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"
  47 #define NRARGS 1
  48 #define NRES 1
  49 #define L_BOUND 0
  50 #define U_BOUND 10
  51 #define N_DIMS 1
  52   /** The ir_type int.   **/
  53 #define PRIM_NAME "int"
  54
  55
  56
  57 static int i_pos = 0;
  58 static int arr_pos = 1;
  59 static ir_type *typ, *typ2;
  60
  61 static ir_node *r1, *f, *r, *c2;
  62
  63 typedef enum {
  64   loop_forward,
  65   loop_backward
  66 } loop_dir_t;
  67
  68 /**
  69  * Constructs a new (method-)function of the form
  70  *
  71  * typ fct_name(typ arg) {
  72  *   for (i = start_value; i < end_value;) { ... }
  73  * }
  74  *
  75  * After return, the loop body is the current block.
  76  *
  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
  81  */
  82 static void function_begin(ir_type *owner, ir_type *mtp, char *fct_name, loop_dir_t loop_dir) {
  83   symconst_symbol sym;
  84   ir_node *x, *t, *cmp;
  85   ir_entity *ent;
  86   ir_entity *array_ent;
  87   ir_type *array_type;
  88
  89   int start_value, end_value;
  90   pn_Cmp cmp_dir;
  91
  92   if (loop_dir == loop_forward) {
  93     start_value = 0;
  94     end_value   = 10;
  95     cmp_dir     = pn_Cmp_Gt;
  96   }
  97   else {
  98     start_value = 10;
  99     end_value   = 0;
 100     cmp_dir     = pn_Cmp_Lt;
 101   }
 102
 103   /* The ir_entity for the procedure */
 104   ent = new_entity(owner,  new_id_from_str(fct_name), mtp);
 105
 106   /* make ir_type infromation for the array */
 107   array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
 108
 109   /* set the bounds for the array */
 110   set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
 111
 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);
 114
 115   /** The code of the procedure **/
 116
 117   /* Generates start and end blocks and nodes, and a first, initial block */
 118 #define NRLOCS 2
 119   new_ir_graph(ent, NRLOCS);
 120
 121   /* The value position used for: */
 122   i_pos = 0;
 123   if (fct_name == METHODNAME7)
 124     c2 = new_Const_int(5);
 125
 126   /* Generate the constant and assign it to b. The assignment is resolved to a
 127      dataflow edge. */
 128   set_value(i_pos, new_Const_int(start_value));
 129
 130   sym.entity_p = array_ent;
 131   set_value(arr_pos, new_SymConst(mode_P, sym, symconst_addr_ent));
 132   x = new_Jmp();
 133
 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));
 137
 138   /* Generate a conditional branch */
 139   r1 = new_immBlock();
 140   add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
 141
 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));
 144
 145   f = new_Proj(x, mode_X, pn_Cond_false);
 146   t = new_Proj(x, mode_X, pn_Cond_true);
 147
 148   /* generate and fill the loop body block */
 149   r = new_immBlock();
 150   add_immBlock_pred(r, t);
 151 }
 152
 153 int x;
 154
 155 /**
 156  * finishes a builded function.
 157  *
 158  * @param b   the return value
 159  */
 160 static void function_end(ir_node *b) {
 161   ir_node *x = new_Jmp();
 162   mature_immBlock(r);
 163   add_immBlock_pred(r1, x);
 164
 165
 166   new_immBlock();
 167   add_immBlock_pred(get_cur_block(), f);
 168   mature_immBlock(get_cur_block());
 169   /* The Return statement */
 170   {
 171     ir_node *in[1], *store ;
 172     in[0] = b;
 173     store = get_store();
 174
 175      x = new_Return(store, 1, in);
 176   }
 177   add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
 178
 179   mature_immBlock(r1);
 180   /* finalize the end block generated in new_ir_graph() */
 181   mature_immBlock(get_irg_end_block(current_ir_graph));
 182 }
 183
 184 int
 185 main(void)
 186 {
 187   ir_graph *irg;
 188   ir_type *owner;
 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;
 193   int i_pos;
 194   int i, n_irgs;
 195   ir_node *b, *c, *c1, *d, *res;
 196   ir_node *b1, *b2, *b3, *b4, *b7, *block;
 197   ir_node *mul, *q, *q1;
 198   ir_node *mul4;
 199   symconst_symbol sym, sym2;
 200
 201   printf("\nCreating an IR graph: IF_EXAMPLE...\n");
 202
 203   init_firm(NULL);
 204
 205   arch_dep_set_opts(arch_dep_none);
 206
 207   do_node_verification(FIRM_VERIFICATION_REPORT);
 208
 209   typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 210
 211   typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 212
 213   /** The global array variable a **/
 214
 215
 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);
 222
 223
 224   /* --------------------------------------------------------------------- */
 225
 226   /* The ir_entity for the procedure */
 227   ent = new_entity(owner,
 228                    new_id_from_str(METHODNAME1),
 229                    proc_tp);
 230   /* The parameter and result types of the procedure. */
 231
 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);
 238
 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);
 242
 243   /** The code of the procedure **/
 244
 245
 246   /* Generates start and end blocks and nodes, and a first, initial block */
 247 #undef NRLOCS
 248 #define NRLOCS 1
 249   irg = new_ir_graph(ent, NRLOCS);
 250
 251   /* The value position used for: */
 252   i_pos = 0;
 253
 254   /* Generate the constant and assign it to b. The assignment is resovled to a
 255      dataflow edge. */
 256   set_value(i_pos, new_Const_int(0));
 257   x = new_Jmp();
 258
 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));
 262
 263   /* Generate a conditional branch */
 264   r1 = new_immBlock();
 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);
 270
 271   /* generate and fill the then block */
 272   r = new_immBlock();
 273   add_immBlock_pred(r, t);
 274
 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));
 289
 290   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 291
 292   x = new_Jmp();
 293   mature_immBlock(r);
 294
 295   add_immBlock_pred(r1, x);
 296   mature_immBlock(r1);
 297
 298   r2 = new_immBlock();
 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);
 305
 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));
 312
 313   x1 = new_Jmp();
 314
 315   mature_immBlock(block);
 316
 317   add_immBlock_pred(r2, x1);
 318   mature_immBlock(r2);
 319
 320   block = new_immBlock();
 321   add_immBlock_pred(block, f1);
 322   mature_immBlock(block);
 323   /* The Return statement */
 324   {
 325     ir_node *in[1], *store ;
 326     in[0] = get_value(i_pos, mode_Is);
 327     store = get_store();
 328
 329      x = new_Return(store, 1, in);
 330   }
 331   add_immBlock_pred(get_irg_end_block(irg), x);
 332
 333   /* finalize the end block generated in new_ir_graph() */
 334   mature_immBlock(get_irg_end_block(irg));
 335
 336
 337   /* -------------------------------------------------------------------------------- */
 338
 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);
 345
 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));
 349
 350   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 351
 352   function_end(b);
 353
 354   /* -------------------------------------------------------------------------- */
 355
 356   function_begin(owner, proc_tp, METHODNAME3, loop_backward);
 357
 358   c = new_Const_int(1);
 359   b = new_Const_int(4);
 360   b3 = new_Const_int(8);
 361
 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));
 368
 369
 370   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 371
 372   function_end(b);
 373
 374   /* -------------------------------------------------------------------------- */
 375
 376   function_begin(owner, proc_tp, METHODNAME4, loop_forward);
 377
 378   c = new_Const_int(1);
 379   b = new_Const_int(4);
 380   b4 = new_Const_int(8);
 381
 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));
 389
 390   function_end(b);
 391
 392   /* -------------------------------------------------------------------------- */
 393
 394   function_begin(owner, proc_tp, METHODNAME5, loop_backward);
 395
 396   c = new_Const_int(1);
 397   b = new_Const_int(4);
 398
 399   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 400
 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));
 406
 407   function_end(b);
 408
 409   /* -------------------------------------------------------------------------- */
 410
 411   function_begin(owner, proc_tp, METHODNAME6, loop_forward);
 412
 413   c = new_Const_int(1);
 414   c1 = new_Const_int(5);
 415   b = new_Const_int(4);
 416
 417   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 418
 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));
 425
 426   function_end(b);
 427
 428   /* -------------------------------------------------------------------------- */
 429
 430   function_begin(owner, proc_tp, METHODNAME7, loop_backward);
 431
 432   c = new_Const_int(1);
 433   b = new_Const_int(4);
 434   b7 = new_Const_int(19);
 435
 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));
 444   function_end(b);
 445
 446   /* -------------------------------------------------------------------------- */
 447
 448   n_irgs = get_irp_n_irgs();
 449
 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);
 457
 458     /* output the vcg file */
 459     construct_backedges(current_ir_graph);
 460     dump_ir_block_graph(current_ir_graph, 0);
 461     dump_all_types(0);
 462     optimize_reassociation(current_ir_graph);
 463     opt_osr(current_ir_graph, osr_flag_default);
 464
 465 #if 0
 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);
 471 #endif
 472
 473     dump_loop_tree(current_ir_graph, "");
 474     dump_ir_block_graph(current_ir_graph, "-strength_reduced");
 475   }
 476   printf("Use ycomp to view the graphs\n");
 477
 478   return 0;
 479 }