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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   testprograms/recursion.c
   4  * Purpose:     Empty methods that recur.
   5  * Author:      Goetz Lindenmaier
   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 *
  20
  21 *
  22 **/
  23
  24 static ir_graph *make_method(char *name, int n_locs) {
  25   ir_type *proc_t   = new_type_method(new_id_from_str(name), 0, 0);
  26   /*set_method_param_type(proc_set_a, 0, class_p_ptr);*/
  27   /*set_method_param_type(proc_set_a, 1, prim_t_int);*/
  28   ir_entity *proc_e = new_entity(get_glob_type(), new_id_from_str(name), proc_t);
  29   return new_ir_graph(proc_e, n_locs);
  30 }
  31
  32
  33 static ir_node *make_Call(ir_graph *c, int n_args, ir_node **args) {
  34   ir_entity *ent = get_irg_entity(c);
  35   ir_type *mtp = get_entity_type(ent);
  36   ir_node *addr;
  37   ir_node *call;
  38   symconst_symbol sym;
  39   sym.entity_p = ent;
  40   addr = new_SymConst(mode_P, sym, symconst_addr_ent);
  41   call = new_Call(get_store(), addr, n_args, args, mtp);
  42   set_store(new_Proj(call, mode_M, pn_Call_M_regular));
  43   if (get_method_n_ress(mtp) == 1) {
  44     ir_type *restp = get_method_res_type(mtp, 0);
  45     return new_Proj(new_Proj(call, mode_T, pn_Call_T_result), get_type_mode(restp), 0);
  46   }
  47   return NULL;
  48 }
  49
  50 static void close_method(int n_ins, ir_node **ins) {
  51   ir_node *x =  new_Return(get_store(), n_ins, ins);
  52   mature_immBlock(get_cur_block());
  53   add_immBlock_pred(get_cur_end_block(), x);
  54   mature_immBlock(get_cur_end_block());
  55   irg_finalize_cons(current_ir_graph);
  56 }
  57
  58
  59 int
  60 main(void)
  61 {
  62   ir_graph *mainp;
  63   ir_graph *hs;
  64   ir_graph *ha;
  65   ir_graph *insert;
  66   ir_graph *remove;
  67   ir_graph *unheap;
  68   ir_graph *downh;
  69   ir_graph *exc;
  70   ir_graph *a, *b, *c, *d;
  71   ir_graph *self, *self1, *self2, *self3, *self4;
  72   ir_entity **free_methods;
  73   int arr_len;
  74
  75   init_firm(NULL);
  76
  77   set_opt_constant_folding(0);
  78   set_opt_cse(0);
  79
  80   set_irp_prog_name(new_id_from_str("recursion"));
  81
  82   /** The callgraph of the heapsort excample */
  83   mainp  = make_method("main", 0);
  84   hs     = make_method("hs", 0);
  85   ha     = make_method("ha", 0);
  86   insert = make_method("insert", 0);
  87   remove = make_method("remove", 0);
  88   unheap = make_method("unheap", 0);
  89   downh  = make_method("downh", 0);
  90   exc    = make_method("exc", 0);
  91
  92   set_irp_main_irg(mainp);
  93
  94   current_ir_graph = mainp;
  95   make_Call(hs, 0, NULL);
  96   close_method(0, NULL);
  97
  98   current_ir_graph = hs;
  99   make_Call(ha, 0, NULL);
 100   make_Call(remove, 0, NULL);
 101   close_method(0, NULL);
 102
 103   current_ir_graph = ha;
 104   make_Call(insert, 0, NULL);
 105   close_method(0, NULL);
 106
 107   current_ir_graph = insert;
 108   make_Call(unheap, 0, NULL);
 109   close_method(0, NULL);
 110
 111   current_ir_graph = remove;
 112   make_Call(unheap, 0, NULL);
 113   make_Call(downh, 0, NULL);
 114   close_method(0, NULL);
 115
 116   current_ir_graph = unheap;
 117   make_Call(exc, 0, NULL);
 118   close_method(0, NULL);
 119
 120   current_ir_graph = downh;
 121   make_Call(downh, 0, NULL);
 122   make_Call(exc, 0, NULL);
 123   close_method(0, NULL);
 124
 125   current_ir_graph = exc;
 126   close_method(0, NULL);
 127
 128
 129   /* A callgraph with a nested recursion. */
 130   a  = make_method("a", 0);
 131   b  = make_method("b", 0);
 132   c  = make_method("c", 0);
 133   d  = make_method("d", 0);
 134
 135   current_ir_graph = a;
 136   make_Call(b, 0, NULL);
 137   make_Call(c, 0, NULL);
 138   make_Call(b, 0, NULL);
 139   close_method(0, NULL);
 140
 141   current_ir_graph = b;
 142   close_method(0, NULL);
 143
 144   current_ir_graph = c;
 145   make_Call(b, 0, NULL);
 146   make_Call(d, 0, NULL);
 147   make_Call(a, 0, NULL);
 148   close_method(0, NULL);
 149
 150   current_ir_graph = d;
 151   make_Call(a, 0, NULL);
 152   make_Call(d, 0, NULL);
 153   close_method(0, NULL);
 154
 155   /* A callgraph with a self recursion */
 156   self  = make_method("self", 0);
 157
 158   current_ir_graph = self;
 159   make_Call(self, 0, NULL);
 160   close_method(0, NULL);
 161
 162   /* A callgraph with a self recursion over several steps*/
 163   self1 = make_method("self1", 0);
 164   self2 = make_method("self2", 0);
 165   self3 = make_method("self3", 0);
 166   self4 = make_method("self4", 0);
 167
 168   current_ir_graph = self1;
 169   make_Call(self2, 0, NULL);
 170   close_method(0, NULL);
 171
 172   current_ir_graph = self2;
 173   make_Call(self3, 0, NULL);
 174   close_method(0, NULL);
 175
 176   current_ir_graph = self3;
 177   make_Call(self4, 0, NULL);
 178   close_method(0, NULL);
 179
 180   current_ir_graph = self4;
 181   make_Call(self1, 0, NULL);
 182   close_method(0, NULL);
 183
 184   printf("Dumping Callgraph.\n");
 185
 186   cgana(&arr_len, &free_methods);
 187   compute_callgraph();
 188   find_callgraph_recursions();
 189   /*dump_callgraph("");*/
 190   /* Order of edges depends on set.c, which is not deterministic. */
 191 #ifdef INTERPROCEDURAL_VIEW
 192   cg_construct(arr_len, free_methods);
 193 #endif
 194
 195   printf("Use ycomp to view these graphs:\n");
 196   printf("ycomp GRAPHNAME\n\n");
 197   return 0;
 198 }