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 "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 METHODTPNAME "STRENGTH_RED_EXAMPLE_meth_tp"
  44 #define NRARGS 1
  45 #define NRES 1
  46 #define L_BOUND 0
  47 #define U_BOUND 10
  48 #define N_DIMS 1
  49   /** The type int.   **/
  50 #define PRIM_NAME "int"
  51
  52
  53
  54 static int i_pos = 0;
  55 static int arr_pos = 1;
  56 static type *typ;
  57
  58 static ir_node *r1, *f, *r;
  59
  60 typedef enum {
  61   loop_forward,
  62   loop_backward,
  63 } loop_dir_t;
  64
  65 static void function_begin(type *owner, type *mtp, char *fct_name, loop_dir_t loop_dir) {
  66   symconst_symbol sym;
  67   ir_node *x, *t, *cmp;
  68   /* The entity for the procedure */
  69   entity *ent = new_entity (owner,  new_id_from_str (fct_name), mtp);
  70   /* The parameter and result types of the procedure. */
  71   set_method_param_type(mtp, 0, typ);
  72   set_method_res_type(mtp, 0, typ);
  73
  74   /* make type infromation for the array */
  75   type *array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
  76
  77   /* set the bounds for the array */
  78   set_array_bounds(array_type, 0,
  79                    new_Const(mode_Iu, new_tarval_from_long (L_BOUND, mode_Iu)),
  80                    new_Const(mode_Iu, new_tarval_from_long (U_BOUND, mode_Iu)));
  81   /* The array is an entity of the global typ */
  82   entity *array_ent = new_entity( owner, new_id_from_chars("a", 1), array_type);
  83
  84   /** The code of the procedure **/
  85
  86   /* Generates start and end blocks and nodes, and a first, initial block */
  87 #define NRLOCS 2
  88   new_ir_graph (ent, NRLOCS);
  89
  90   /* The value position used for: */
  91   i_pos = 0;
  92
  93   /* Generate the constant and assign it to b. The assignment is resolved to a
  94      dataflow edge. */
  95   if (loop_dir == loop_forward) {
  96     set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
  97   } else {
  98     set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (10, mode_Is)));
  99   }
 100   sym.entity_p =  array_ent ;
 101   set_value (arr_pos, new_SymConst(sym, symconst_addr_ent));
 102
 103   x = new_Jmp ();
 104
 105   /* We know all predecessors of the block and all set_values and set_stores are
 106      preformed.   We can mature the block.  */
 107   mature_immBlock (get_irg_current_block(current_ir_graph));
 108
 109   /* Generate a conditional branch */
 110   r1 = new_immBlock();
 111   add_immBlock_pred(get_irg_current_block(current_ir_graph), x);
 112
 113   if (loop_dir == loop_forward) {
 114     cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(10, mode_Is)),
 115                   get_value(i_pos, mode_Is));
 116     x = new_Cond (new_Proj(cmp, mode_b, Gt));
 117   } else {
 118     cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(0, mode_Is)),
 119                   get_value(i_pos, mode_Is));
 120     x = new_Cond (new_Proj(cmp, mode_b, Lt));
 121   }
 122   f = new_Proj (x, mode_X, 0);
 123   t = new_Proj (x, mode_X, 1);
 124
 125   /* generate and fill the loop body block */
 126   r = new_immBlock ();
 127   add_immBlock_pred (r, t);
 128 }
 129
 130 static void function_end(ir_node *b) {
 131   ir_node *x = new_Jmp ();
 132   mature_immBlock (r);
 133   add_immBlock_pred(r1, x);
 134
 135
 136   new_immBlock();
 137   add_immBlock_pred(get_cur_block(), f);
 138   mature_immBlock (get_cur_block());
 139   /* The Return statement */
 140   {
 141     ir_node *in[1], *store ;
 142     in[0] = b;
 143     store = get_store();
 144
 145      x = new_Return (store, 1, in);
 146   }
 147   add_immBlock_pred(get_irg_end_block(current_ir_graph), x);
 148
 149   mature_immBlock (r1);
 150   /* finalize the end block generated in new_ir_graph() */
 151   mature_immBlock (get_irg_end_block(current_ir_graph));
 152 }
 153
 154 int
 155 main(void)
 156 {
 157   ir_graph *irg;
 158   type *owner;
 159   entity *ent, *array_ent;
 160   type *proc_tp, *array_type; /* type information for the method main */
 161   ir_node *x,*x1 ,  *r, *t, *f, *f1, *t1, *cmp, *r1, *r2;
 162   int i_pos;
 163
 164   printf("\nCreating an IR graph: IF_EXAMPLE...\n");
 165
 166   init_firm (NULL);
 167
 168   do_node_verification(NODE_VERIFICATION_REPORT);
 169
 170   typ = new_type_primitive(new_id_from_chars(PRIM_NAME, strlen(PRIM_NAME)), mode_Is);
 171
 172   /** The global array variable a **/
 173
 174
 175   /** Type information for the procedure **/
 176   owner = get_glob_type();
 177   /* Type information for the procedure */
 178   proc_tp = new_type_method(new_id_from_chars(METHODTPNAME, strlen(METHODTPNAME)),
 179                               NRARGS, NRES);
 180   set_method_param_type(proc_tp, 0, typ);
 181   set_method_res_type(proc_tp, 0, typ);
 182
 183
 184   /* --------------------------------------------------------------------- */
 185
 186   /* The entity for the procedure */
 187   ent = new_entity (owner,
 188                     new_id_from_str (METHODNAME1),
 189                     proc_tp);
 190   /* The parameter and result types of the procedure. */
 191
 192   /* make type infromation for the array */
 193   array_type = new_type_array(new_id_from_chars("array", 5),N_DIMS, typ);
 194
 195   /* set the bounds for the array */
 196   set_array_bounds(array_type, 0,
 197                    new_Const(mode_Iu, new_tarval_from_long (L_BOUND, mode_Iu)),
 198                    new_Const(mode_Iu, new_tarval_from_long (U_BOUND, mode_Iu)));
 199   /* The array is an entity of the global typ */
 200   array_ent = new_entity( owner, new_id_from_chars("a", 1), array_type);
 201
 202   /** The code of the procedure **/
 203
 204
 205   /* Generates start and end blocks and nodes, and a first, initial block */
 206 #undef NRLOCS
 207 #define NRLOCS 1
 208   irg = new_ir_graph (ent, NRLOCS);
 209
 210   /* The value position used for: */
 211   i_pos = 0;
 212
 213   /* Generate the constant and assign it to b. The assignment is resovled to a
 214      dataflow edge. */
 215   set_value (i_pos, new_Const (mode_Is, new_tarval_from_long (0, mode_Is)));
 216   x = new_Jmp ();
 217
 218   /* We know all predecessors of the block and all set_values and set_stores are
 219      preformed.   We can mature the block.  */
 220    mature_immBlock (get_irg_current_block(irg));
 221
 222   /* Generate a conditional branch */
 223   r1 = new_immBlock();
 224   add_immBlock_pred(get_irg_current_block(irg), x);
 225   cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(10, mode_Is)),
 226                 get_value(i_pos, mode_Is));
 227   x = new_Cond (new_Proj(cmp, mode_b, Gt));
 228   f = new_Proj (x, mode_X, 0);
 229   t = new_Proj (x, mode_X, 1);
 230
 231   /* generate and fill the then block */
 232   r = new_immBlock ();
 233   add_immBlock_pred (r, t);
 234
 235   ir_node *b, *c, *d, *res;
 236   symconst_symbol sym;
 237   c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
 238   b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
 239   sym.entity_p =  array_ent ;
 240   d = new_SymConst(sym, symconst_addr_ent);
 241   res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 242   set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
 243                                   new_tarval_from_long (19,mode_Is))),
 244                        mode_M, 0));
 245   set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c , mode_Is));
 246
 247   x = new_Jmp ();
 248   mature_immBlock (r);
 249
 250   add_immBlock_pred(r1, x);
 251   mature_immBlock (r1);
 252
 253   r2 = new_immBlock();
 254   add_immBlock_pred(get_irg_current_block(irg), f);
 255   cmp = new_Cmp(new_Const (mode_Is, new_tarval_from_long(0, mode_Is)),get_value(i_pos, mode_Is));
 256   x = new_Cond (new_Proj(cmp, mode_b, Lt));
 257   f1 = new_Proj (x, mode_X, 0);
 258   t1 = new_Proj (x, mode_X, 1);
 259
 260   ir_node *block = new_immBlock();
 261   add_immBlock_pred(block, t1);
 262
 263   res = new_Add(d, new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 264   set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
 265                        new_tarval_from_long (19, mode_Is))), mode_M, 0));
 266   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c , mode_Is));
 267
 268   x1 = new_Jmp ();
 269
 270   mature_immBlock (block);
 271
 272   add_immBlock_pred(r2, x1);
 273   mature_immBlock (r2);
 274
 275   block = new_immBlock();
 276   add_immBlock_pred(block, f1);
 277   mature_immBlock (block);
 278   /* The Return statement */
 279   {
 280     ir_node *in[1], *store ;
 281     in[0] = get_value (i_pos, mode_Is);
 282     store = get_store();
 283
 284      x = new_Return (store, 1, in);
 285   }
 286   add_immBlock_pred(get_irg_end_block(irg), x);
 287
 288   /* finalize the end block generated in new_ir_graph() */
 289   mature_immBlock (get_irg_end_block(irg));
 290
 291
 292   /* -------------------------------------------------------------------------------- */
 293
 294   function_begin(owner, proc_tp, METHODNAME2, loop_forward);
 295
 296   c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
 297   b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
 298
 299   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 300   set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
 301                                   new_tarval_from_long (19, mode_Is))),
 302                        mode_M, 0));
 303
 304   set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 305
 306   function_end(b);
 307
 308   /* -------------------------------------------------------------------------- */
 309
 310   function_begin(owner, proc_tp, METHODNAME3, loop_backward);
 311
 312   c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
 313   b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
 314
 315
 316   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 317   set_store (new_Proj (new_Store (get_store (), res, get_value(i_pos, mode_Is)), mode_M, 0));
 318
 319   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 320
 321   function_end(b);
 322
 323   /* -------------------------------------------------------------------------- */
 324
 325   function_begin(owner, proc_tp, METHODNAME4, loop_forward);
 326
 327   c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
 328   b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
 329
 330   set_value (i_pos, new_Add(get_value(i_pos, mode_Is), c, mode_Is));
 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,get_value(i_pos, mode_Is)),
 334                        mode_M, 0));
 335
 336   function_end(b);
 337
 338   /* -------------------------------------------------------------------------- */
 339
 340   function_begin(owner, proc_tp, METHODNAME5, loop_backward);
 341
 342   c = new_Const (mode_Is, new_tarval_from_long (1, mode_Is));
 343   b = new_Const (mode_Is, new_tarval_from_long (4, mode_Is));
 344
 345   set_value (i_pos, new_Sub(get_value(i_pos, mode_Is), c, mode_Is));
 346
 347
 348   res = new_Add(get_value(arr_pos, mode_P), new_Mul(get_value(i_pos, mode_Is), b, mode_Is), mode_P);
 349   set_store (new_Proj (new_Store (get_store (), res, new_Const (mode_Is,
 350                                   new_tarval_from_long (19, mode_Is))),
 351                        mode_M, 0));
 352
 353   function_end(b);
 354
 355   /* -------------------------------------------------------------------------- */
 356
 357   int i, n_irgs = get_irp_n_irgs();
 358
 359   printf("Done building the graph.  Dumping and optimizing it.\n");
 360   dump_consts_local(1);
 361   turn_off_edge_labels();
 362   for (i = 0; i < n_irgs; ++i) {
 363     current_ir_graph = get_irp_irg(i);
 364     irg_vrfy(current_ir_graph);
 365     finalize_cons (current_ir_graph);
 366
 367     /* output the vcg file */
 368     //dump_ir_block_graph (current_ir_graph, "-early");
 369     construct_backedges(current_ir_graph);
 370     //dump_ir_block_graph (current_ir_graph, 0);
 371     dump_all_types(0);
 372     set_opt_strength_red_verbose(2);
 373     set_firm_verbosity(2);
 374     reduce_strength(current_ir_graph);
 375
 376     //dump_loop_tree(current_ir_graph, "");
 377     dump_ir_block_graph (current_ir_graph, "-strength_reduced");
 378   }
 379   //printf("use xvcg to view this graph:\n");
 380   //printf("/ben/goetz/bin/xvcg GRAPHNAME\n\n");
 381
 382   return (0);
 383 }