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 # include <reassoc.h>
  16 # include "firm.h"
  17
  18 # include "irvrfy.h"
  19 # include "irdump.h"
  20
  21
  22 /**
  23 *  This file constructs the ir for the following pseudo-program:
  24 *
  25 *  int a[10];
  26 *
  27 *  void main(void) {
  28 *    int i = 0;
  29 *
  30 *    while (i < 10)  {
  31 *       a[i] = 19;
  32 *       i++
  33 *    }
  34 *  }
  35 **/
  36
  37 #define new_Const_int(n)        new_Const(mode_Is, new_tarval_from_long(n, mode_Is))
  38
  39
  40 #define CLASSNAME "STRENGTH_RED_EXAMPLE"
  41 #define METHODNAME1 "STRENGTH_RED_EXAMPLE_m1"
  42 #define METHODNAME2 "STRENGTH_RED_EXAMPLE_m2"
  43 #define METHODNAME3 "STRENGTH_RED_EXAMPLE_m3"
  44 #define METHODNAME4 "STRENGTH_RED_EXAMPLE_m4"
  45 #define METHODNAME5 "STRENGTH_RED_EXAMPLE_m5"
  46 #define METHODNAME6 "STRENGTH_RED_EXAMPLE_m6"
  47 #define METHODNAME7 "STRENGTH_RED_EXAMPLE_m7"
  48 #define METHODNAME8 "STRENGTH_RED_EXAMPLE_m8"
  49 #define METHODNAME9 "STRENGTH_RED_EXAMPLE_m9"
  50 #define METHODTPNAME "STRENGTH_RED_EXAMPLE_meth_tp"
  51 #define NRARGS 1
  52 #define NRES 1
  53 #define L_BOUND 0
  54 #define U_BOUND 10
  55 #define N_DIMS 1
  56   /** The type int.   **/
  57 #define PRIM_NAME "int"
  58
  59
  60
  61 static int i_pos = 0;
  62 static int arr_pos = 1;
  63 static ir_type *typ, *typ2;
  64
  65 static ir_node *r1, *f, *r, *c2;
  66
  67 typedef enum {
  68   loop_forward,
  69   loop_backward,
  70 } loop_dir_t;
  71
  72 /**
  73  * Constructs a new (method-)function of the form
  74  *
  75  * typ fct_name(typ arg) {
  76  *   for (i = start_value; i < end_value;) { ... }
  77  * }
  78  *
  79  * After return, the loop body is the current block.
  80  *
  81  * @param owner        owner-type of this (method-)function
  82  * @param mtp          the method type of this function
  83  * @param fct_name     the name of the function
  84  * @param loop_dir     the loop direction
  85  */
  86 static void function_begin(ir_type *owner, ir_type *mtp, char *fct_name, loop_dir_t loop_dir) {
  87   symconst_symbol sym;
  88   ir_node *x, *t, *cmp;
  89
  90   int start_value, end_value;
  91   pn_Cmp cmp_dir;
  92
  93   if (loop_dir == loop_forward) {
  94     start_value = 0;
  95     end_value   = 10;
  96     cmp_dir     = pn_Cmp_Gt;
  97   }
  98   else {
  99     start_value = 10;
 100     end_value   = 0;
 101     cmp_dir     = pn_Cmp_Lt;
 102   }
 103
 104   /* The entity for the procedure */
 105   entity *ent = new_entity (owner,  new_id_from_str(fct_name), mtp);
 106
 107   /* make type infromation for the array */
 108   ir_type *array_type = new_type_array(new_id_from_str("array"), N_DIMS, typ);
 109
 110   /* set the bounds for the array */
 111   set_array_bounds_int(array_type, 0, L_BOUND, U_BOUND);
 112
 113   /* The array is an entity of the owner type */
 114   entity *array_ent = new_entity(owner, new_id_from_str("a"), array_type);
 115
 116   /** The code of the procedure **/
 117
 118   /* Generates start and end blocks and nodes, and a first, initial block */
 119 #define NRLOCS 2
 120   new_ir_graph(ent, NRLOCS);
 121
 122   /* The value position used for: */
 123   i_pos = 0;
 124   if (fct_name == METHODNAME7)
 125     c2 = new_Const_int(5);
 126
 127   /* Generate the constant and assign it to b. The assignment is resolved to a
 128      dataflow edge. */
 129   set_value(i_pos, new_Const_int(start_value));
 130
 131   sym.entity_p = array_ent;
 132   set_value(arr_pos, new_SymConst(sym, symconst_addr_ent));
 133   x = new_Jmp();
 134
 135   /* We know all predecessors of the block and all set_values and set_stores are
 136      preformed.   We can mature the block.  */
 137   mature_immBlock(get_irg_current_block(current_ir_graph));
 138
 139   /* Generate a conditional branch */
 140   r1 = new_immBlock();
 141   add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
 142
 143   cmp = new_Cmp(new_Const_int(end_value), get_value(i_pos, mode_Is));
 144   x = new_Cond(new_Proj(cmp, mode_b, cmp_dir));
 145
 146   f = new_Proj(x, mode_X, 0);
 147   t = new_Proj(x, mode_X, 1);
 148
 149   /* generate and fill the loop body block */
 150   r = new_immBlock();
 151   add_immBlock_pred(r, t);
 152 }
 153
 154 int x;
 155
 156 /**
 157  * finishes a builded function.
 158  *
 159  * @param b   the return value
 160  */
 161 static void function_end(ir_node *b) {
 162   ir_node *x = new_Jmp();
 163   mature_immBlock (r);
 164   add_immBlock_pred(r1, x);
 165
 166
 167   new_immBlock();
 168   add_immBlock_pred(get_cur_block(), f);
 169   mature_immBlock (get_cur_block());
 170   /* The Return statement */
 171   {
 172     ir_node *in[1], *store ;
 173     in[0] = b;
 174     store = get_store();
 175
 176      x = new_Return(store, 1, in);
 177   }
 178   add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
 179
 180   mature_immBlock(r1);
 181   /* finalize the end block generated in new_ir_graph() */
 182   mature_immBlock(get_irg_end_block(current_ir_graph));
 183 }
 184
 185 int
 186 main(void)
 187 {
 188   ir_graph *irg;
 189   ir_type *owner;
 190   entity *ent, *array_ent, *array_ent2;
 191   ir_type *proc_tp, *array_type, *array_type2; /* type information for the method main */
 192   ir_node *x,*x1 ,  *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
 193   int i_pos;
 194
 195   printf("\nCreating an IR graph: IF_EXAMPLE...\n");
 196
 197   init_firm (NULL);
 198
 199   arch_dep_set_opts(arch_dep_none);
 200
 201   do_node_verification(FIRM_VERIFICATION_REPORT);
 202
 203   typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 204
 205   typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 206
 207   /** The global array variable a **/
 208
 209
 210   /** Type information for the procedure **/
 211   owner = get_glob_type();
 212   /* Type information for the procedure */
 213   proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)), NRARGS, NRES);
 214   set_method_param_type(proc_tp, 0, typ);
 215   set_method_res_type(proc_tp, 0, typ);
 216
 217
 218   /* --------------------------------------------------------------------- */
 219
 220   /* The entity for the procedure */
 221   ent = new_entity (owner,
 222                     new_id_from_str (METHODNAME1),
 223                     proc_tp);
 224   /* The parameter and result types of the procedure. */
 225
 226   /* make type infromation for the array */
 227   array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
 228   array_type2 = new_type_array(new_id_from_chars("array2", 6),N_DIMS, typ2);
 229   /* set the bounds for the array */
 230   set_array_bounds_int(array_type,  0, L_BOUND, U_BOUND);
 231   set_array_bounds_int(array_type2, 0, L_BOUND, U_BOUND);
 232
 233   /* The array is an entity of the global typ */
 234   array_ent  = new_entity( owner, new_id_from_str("a"), array_type);
 235   array_ent2 = new_entity( owner, new_id_from_str("a2"), array_type2);
 236
 237   /** The code of the procedure **/
 238
 239
 240   /* Generates start and end blocks and nodes, and a first, initial block */
 241 #undef NRLOCS
 242 #define NRLOCS 1
 243   irg = new_ir_graph(ent, NRLOCS);
 244
 245   /* The value position used for: */
 246   i_pos = 0;
 247
 248   /* Generate the constant and assign it to b. The assignment is resovled to a
 249      dataflow edge. */
 250   set_value (i_pos, new_Const_int(0));
 251   x = new_Jmp ();
 252
 253   /* We know all predecessors of the block and all set_values and set_stores are
 254      preformed.   We can mature the block.  */
 255    mature_immBlock (get_irg_current_block(irg));
 256
 257   /* Generate a conditional branch */
 258   r1 = new_immBlock();
 259   add_immBlock_pred(get_irg_current_block(irg), x);
 260   cmp = new_Cmp(new_Const_int(10), get_value(i_pos, mode_Is));
 261   x = new_Cond(new_Proj(cmp, mode_b, pn_Cmp_Gt));
 262   f = new_Proj(x, mode_X, 0);
 263   t = new_Proj(x, mode_X, 1);
 264
 265   /* generate and fill the then block */
 266   r = new_immBlock ();
 267   add_immBlock_pred (r, t);
 268
 269   ir_node *b, *c, *d, *res;
 270   symconst_symbol sym, sym2;
 271   c = new_Const_int(1);
 272   b = new_Const_int(4);
 273   ir_node *b2 = new_Const_int(12);
 274   sym.entity_p =  array_ent ;
 275   sym2.entity_p =  array_ent2 ;
 276   d = new_SymConst(sym, symconst_addr_ent);
 277   ir_node *d2 = new_SymConst(sym2, symconst_addr_ent);
 278   res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 279   //ir_node *res2 = new_Add(d2, get_value(i_pos, mode_Is), mode_P);
 280   ir_node *res2 = new_Add(d2, new_Mul(get_value(i_pos, mode_Is), b2, mode_Is), mode_P);
 281   //res2 = new_Add(res2, new_Const_int(12), mode_P);
 282   set_store (new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
 283   set_store (new_Proj(new_Store(get_store(), res2, new_Const_int(16)), mode_M, 0));
 284   d = new_SymConst(sym, symconst_addr_ent);
 285   res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 286   set_store(new_Proj(new_Store(get_store(), res, new_Const_int(15)), mode_M, 0));
 287
 288   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 289
 290   x = new_Jmp();
 291   mature_immBlock(r);
 292
 293   add_immBlock_pred(r1, x);
 294   mature_immBlock(r1);
 295
 296   r2 = new_immBlock();
 297   ir_node *b1 = new_Const_int(45);
 298   add_immBlock_pred(get_irg_current_block(irg), f);
 299   cmp = new_Cmp(new_Const_int(0), b1);
 300   x = new_Cond (new_Proj(cmp, mode_b, pn_Cmp_Lt));
 301   f1 = new_Proj (x, mode_X, 0);
 302   t1 = new_Proj (x, mode_X, 1);
 303
 304   ir_node *block = new_immBlock();
 305   add_immBlock_pred(block, t1);
 306   b1 = new_Sub (b1, get_value(i_pos, mode_Is), mode_Is);
 307   res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 308   set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
 309   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 310
 311   x1 = new_Jmp();
 312
 313   mature_immBlock(block);
 314
 315   add_immBlock_pred(r2, x1);
 316   mature_immBlock(r2);
 317
 318   block = new_immBlock();
 319   add_immBlock_pred(block, f1);
 320   mature_immBlock(block);
 321   /* The Return statement */
 322   {
 323     ir_node *in[1], *store ;
 324     in[0] = get_value(i_pos, mode_Is);
 325     store = get_store();
 326
 327      x = new_Return(store, 1, in);
 328   }
 329   add_immBlock_pred(get_irg_end_block(irg), x);
 330
 331   /* finalize the end block generated in new_ir_graph() */
 332   mature_immBlock(get_irg_end_block(irg));
 333
 334
 335   /* -------------------------------------------------------------------------------- */
 336
 337   function_begin(owner, proc_tp, METHODNAME2, loop_forward);
 338   ir_node *mul, *q;
 339   q =  new_Const_int(15);
 340   ir_node *q1 = new_Const_int(13);
 341   c = new_Const_int(1);
 342   b = new_Const_int(4);
 343   mul = new_Mul(q, get_value(i_pos, mode_Is), mode_Is);
 344
 345   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 346   res = new_Add(q1, res, mode_P);
 347   set_store(new_Proj(new_Store (get_store(), res, mul), mode_M, 0));
 348
 349   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 350
 351   function_end(b);
 352
 353   /* -------------------------------------------------------------------------- */
 354
 355   function_begin(owner, proc_tp, METHODNAME3, loop_backward);
 356
 357   c = new_Const_int(1);
 358   b = new_Const_int(4);
 359   ir_node *b3 = new_Const_int(8);
 360
 361   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 362   res = new_Add(b, res, mode_P);
 363   res = new_Add(b3, res, mode_P);
 364   ir_node *res3 = new_Add(b3, res, mode_P);
 365   res = new_Add(res3, res, mode_P);
 366   set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
 367
 368
 369   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 370
 371   function_end(b);
 372
 373   /* -------------------------------------------------------------------------- */
 374
 375   function_begin(owner, proc_tp, METHODNAME4, loop_forward);
 376
 377   c = new_Const_int(1);
 378   b = new_Const_int(4);
 379   ir_node *b4 = new_Const_int(8);
 380
 381   set_value(i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 382   ir_node *mul4 = new_Mul(get_value(i_pos, mode_Is), b4, mode_Is);
 383   res = new_Add(mul4, get_value(arr_pos, mode_P), mode_P);
 384   set_store (new_Proj (new_Store (get_store (), res,get_value(i_pos, mode_Is)),
 385                        mode_M, 0));
 386   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 387   set_store(new_Proj(new_Store(get_store(), res, get_value(i_pos, mode_Is)), mode_M, 0));
 388
 389   function_end(b);
 390
 391   /* -------------------------------------------------------------------------- */
 392
 393   function_begin(owner, proc_tp, METHODNAME5, loop_backward);
 394
 395   c = new_Const_int(1);
 396   b = new_Const_int(4);
 397
 398   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 399
 400   ir_node * res5 = new_Add (c, b, mode_Is);
 401   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 402   res = new_Add(res, b, mode_P);
 403   res = new_Add(res, res5, mode_P);
 404   set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
 405
 406   function_end(b);
 407
 408   /* -------------------------------------------------------------------------- */
 409
 410   function_begin(owner, proc_tp, METHODNAME6, loop_forward);
 411
 412   c = new_Const_int(1);
 413   ir_node *c1 = new_Const_int(5);
 414   b = new_Const_int(4);
 415
 416   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 417
 418   res = new_Add( get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is),
 419                              b, mode_Is), mode_P);
 420   res = new_Sub(c1, res, mode_P);
 421   res = new_Add( b, res, mode_P);
 422   res = new_Add(b, res, mode_P);
 423   set_store(new_Proj(new_Store(get_store(), res, new_Const_int(19)), mode_M, 0));
 424
 425   function_end(b);
 426
 427   /* -------------------------------------------------------------------------- */
 428
 429   function_begin(owner, proc_tp, METHODNAME7, loop_backward);
 430
 431   c = new_Const_int(1);
 432   b = new_Const_int(4);
 433   ir_node *b7 = new_Const_int(19);
 434
 435   // a[i] = a[i+4]
 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   ir_node *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, 0));
 443   set_value(i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 444   function_end(b);
 445
 446   /* -------------------------------------------------------------------------- */
 447
 448   int i, 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     //dump_ir_block_graph (current_ir_graph, "-early");
 460     construct_backedges(current_ir_graph);
 461     dump_ir_block_graph (current_ir_graph, 0);
 462     dump_all_types(0);
 463     set_opt_strength_red_verbose(0);
 464     set_firm_verbosity(0);
 465     optimize_reassociation(current_ir_graph);
 466     reduce_strength(current_ir_graph);
 467
 468     // remove_critical_cf_edges(current_ir_graph);
 469     //set_opt_global_cse(1);
 470     //place_code(current_ir_graph);
 471     //set_opt_global_cse(0);
 472     // optimize_reassociation(current_ir_graph);
 473
 474     dump_loop_tree(current_ir_graph, "");
 475     dump_ir_block_graph (current_ir_graph, "-strength_reduced");
 476   }
 477   //printf("use xvcg to view this graph:\n");
 478   //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");
 479
 480   return (0);
 481 }