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 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"
  48 #define NRARGS 1
  49 #define NRES 1
  50 #define L_BOUND 0
  51 #define U_BOUND 10
  52 #define N_DIMS 1
  53   /** The type int.   **/
  54 #define PRIM_NAME "int"
  55
  56
  57
  58 static int i_pos = 0;
  59 static int arr_pos = 1;
  60 static type *typ, *typ2;
  61
  62 static ir_node *r1, *f, *r, *c2;
  63
  64 typedef enum {
  65   loop_forward,
  66   loop_backward,
  67 } loop_dir_t;
  68
  69 static void function_begin(type *owner, type *mtp, char *fct_name, loop_dir_t loop_dir) {
  70   symconst_symbol sym;
  71   ir_node *x, *t, *cmp;
  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);
  77
  78   /* make type infromation for the array */
  79   type *array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
  80
  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);
  87
  88   /** The code of the procedure **/
  89
  90   /* Generates start and end blocks and nodes, and a first, initial block */
  91 #define NRLOCS 2
  92   new_ir_graph (ent, NRLOCS);
  93
  94   /* The value position used for: */
  95   i_pos = 0;
  96   if(fct_name == METHODNAME7)
  97     c2 = new_Const (mode_Is, new_tarval_from_long (5, mode_Is));
  98
  99   /* Generate the constant and assign it to b. The assignment is resolved to a
 100      dataflow edge. */
 101   if (loop_dir == loop_forward) {
 102     set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
 103   } else {
 104     set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (10, mode_Is)));
 105   }
 106   sym.entity_p =  array_ent ;
 107   set_value (arr_pos, new_SymConst(sym, symconst_addr_ent));
 108   x = new_Jmp ();
 109
 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));
 113
 114   /* Generate a conditional branch */
 115   r1 = new_immBlock();
 116   add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
 117
 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));
 122   } else {
 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));
 126   }
 127   f = new_Proj (x, mode_X, 0);
 128   t = new_Proj (x, mode_X, 1);
 129
 130   /* generate and fill the loop body block */
 131   r = new_immBlock ();
 132   add_immBlock_pred (r, t);
 133 }
 134
 135 int x;
 136 static int y;
 137
 138 static void function_end(ir_node *b) {
 139   ir_node *x = new_Jmp ();
 140   mature_immBlock (r);
 141   add_immBlock_pred(r1, x);
 142
 143
 144   new_immBlock();
 145   add_immBlock_pred(get_cur_block(), f);
 146   mature_immBlock (get_cur_block());
 147   /* The Return statement */
 148   {
 149     ir_node *in[1], *store ;
 150     in[0] = b;
 151     store = get_store();
 152
 153      x = new_Return (store, 1, in);
 154   }
 155   add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
 156
 157   mature_immBlock (r1);
 158   /* finalize the end block generated in new_ir_graph() */
 159   mature_immBlock (get_irg_end_block(current_ir_graph));
 160 }
 161
 162 int
 163 main(void)
 164 {
 165   ir_graph *irg;
 166   type *owner;
 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;
 170   int i_pos;
 171
 172   printf("\nCreating an IR graph: IF_EXAMPLE...\n");
 173
 174   init_firm (NULL);
 175
 176   arch_dep_set_opts(arch_dep_none);
 177
 178   do_node_verification(NODE_VERIFICATION_REPORT);
 179
 180   typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 181
 182   typ2 = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 183
 184   /** The global array variable a **/
 185
 186
 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)),
 191                               NRARGS, NRES);
 192   set_method_param_type(proc_tp, 0, typ);
 193   set_method_res_type(proc_tp, 0, typ);
 194
 195
 196   /* --------------------------------------------------------------------- */
 197
 198   /* The entity for the procedure */
 199   ent = new_entity (owner,
 200                     new_id_from_str (METHODNAME1),
 201                     proc_tp);
 202   /* The parameter and result types of the procedure. */
 203
 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)));
 214
 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);
 218
 219   /** The code of the procedure **/
 220
 221
 222   /* Generates start and end blocks and nodes, and a first, initial block */
 223 #undef NRLOCS
 224 #define NRLOCS 1
 225   irg = new_ir_graph (ent, NRLOCS);
 226
 227   /* The value position used for: */
 228   i_pos = 0;
 229
 230   /* Generate the constant and assign it to b. The assignment is resovled to a
 231      dataflow edge. */
 232   set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
 233   x = new_Jmp ();
 234
 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));
 238
 239   /* Generate a conditional branch */
 240   r1 = new_immBlock();
 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);
 247
 248   /* generate and fill the then block */
 249   r = new_immBlock ();
 250   add_immBlock_pred (r, t);
 251
 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))),
 267                        mode_M, 0));
 268   set_store (new_Proj (new_Store (get_store (), res2, new_Const (mode_Is,
 269                                   new_tarval_from_long (16,mode_Is))),
 270                        mode_M, 0));
 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))),
 275                        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 (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);
 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 (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));
 300
 301   x1 = new_Jmp ();
 302
 303   mature_immBlock (block);
 304
 305   add_immBlock_pred(r2, x1);
 306   mature_immBlock (r2);
 307
 308   block = new_immBlock();
 309   add_immBlock_pred(block, f1);
 310   mature_immBlock (block);
 311   /* The Return statement */
 312   {
 313     ir_node *in[1], *store ;
 314     in[0] = get_value (i_pos, mode_Is);
 315     store = get_store();
 316
 317      x = new_Return (store, 1, in);
 318   }
 319   add_immBlock_pred(get_irg_end_block(irg), x);
 320
 321   /* finalize the end block generated in new_ir_graph() */
 322   mature_immBlock (get_irg_end_block(irg));
 323
 324
 325   /* -------------------------------------------------------------------------------- */
 326
 327   function_begin(owner, proc_tp, METHODNAME2, loop_forward);
 328   ir_node *mul, *q;
 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);
 334
 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),
 338                        mode_M, 0));
 339
 340   set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 341
 342   function_end(b);
 343
 344   /* -------------------------------------------------------------------------- */
 345
 346   function_begin(owner, proc_tp, METHODNAME3, loop_backward);
 347
 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));
 351
 352
 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));
 359
 360
 361   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 362
 363   function_end(b);
 364
 365   /* -------------------------------------------------------------------------- */
 366
 367   function_begin(owner, proc_tp, METHODNAME4, loop_forward);
 368
 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));
 372
 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)),
 377                        mode_M, 0));
 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)),
 380                        mode_M, 0));
 381
 382   function_end(b);
 383
 384   /* -------------------------------------------------------------------------- */
 385
 386   function_begin(owner, proc_tp, METHODNAME5, loop_backward);
 387
 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));
 390
 391   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 392
 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))),
 399                        mode_M, 0));
 400
 401   function_end(b);
 402
 403   /* -------------------------------------------------------------------------- */
 404
 405   function_begin(owner, proc_tp, METHODNAME6, loop_forward);
 406
 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));
 410
 411
 412  set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 413
 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))),
 421                        mode_M, 0));
 422
 423   function_end(b);
 424
 425   /* -------------------------------------------------------------------------- */
 426
 427   function_begin(owner, proc_tp, METHODNAME7, loop_backward);
 428
 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));
 433
 434
 435
 436   // a[i] = a[i+4]
 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),
 444                        mode_M, 0));
 445   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 446   function_end(b);
 447
 448   /* -------------------------------------------------------------------------- */
 449
 450   int i, n_irgs = get_irp_n_irgs();
 451
 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);
 459
 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);
 464     dump_all_types(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);
 469
 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);
 475
 476     dump_loop_tree(current_ir_graph, "");
 477     dump_ir_block_graph (current_ir_graph, "-strength_reduced");
 478   }
 479   //printf("use xvcg to view this graph:\n");
 480   //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");
 481
 482   return (0);
 483 }