build.cc

   1 #include "suif_inc.h"
   2 #include <map>
   3 #include <algorithm>
   4 #include "dump.h"
   5 #include "build.h"
   6 #include <isl/aff.h>
   7
   8 #define value_to_int(v) ((int)mpz_get_si(v))
   9
  10 struct transformer {
  11     FILE        *out;
  12     int          indent;
  13
  14     isl_ast_node        *tree;
  15     tree_proc    *tp;
  16     symtab_ann   *sa;
  17
  18     map<int, instruction *>             nr2insn;
  19     map<instruction *, domain_ann *>    insn2dom;
  20     std::map<isl_id *, var_sym *>       it;
  21
  22     transformer(tree_proc *t, __isl_keep isl_ast_node *tree);
  23     void build(tree_node *root);
  24     void visit(tree_node *t);
  25
  26     instruction *scan(__isl_keep isl_ast_expr *e);
  27     instruction *scan_id(__isl_keep isl_ast_expr *e);
  28     instruction *scan_op(__isl_keep isl_ast_expr *e);
  29     instruction *scan_int(__isl_keep isl_ast_expr *e);
  30     tree_node_list *scan_block(__isl_keep isl_ast_node *block);
  31     tree_node_list *scan(__isl_keep isl_ast_node *node);
  32     tree_node_list *scan_user(__isl_keep isl_ast_node *node);
  33     tree_node_list *scan_for(__isl_keep isl_ast_node *node);
  34     tree_node_list *scan_if(__isl_keep isl_ast_node *node);
  35
  36     tree_node_list *scan_substitutions(__isl_keep isl_ast_expr *subs,
  37                                         domain_ann *dom);
  38
  39     var_sym *name(__isl_keep isl_id *id);
  40 };
  41
  42 transformer::transformer(tree_proc *t, __isl_keep isl_ast_node *tree) :
  43     tp(t), tree(tree)
  44 {
  45     sa = (symtab_ann *)tp->peek_annote(k_domain_symtab);
  46 }
  47
  48 void transformer::visit(tree_node *t)
  49 {
  50     if (!t->peek_annote(k_static_root))
  51         return;
  52     build(t);
  53 }
  54
  55 static void visit (tree_node *t, void *d)
  56 {
  57     ((transformer *)d)->visit(t);
  58 }
  59
  60 void build(tree_proc *tp, __isl_keep isl_ast_node *tree)
  61 {
  62     transformer b(tp, tree);
  63     //unused_start_symtab(tp->scope(), TRUE, FALSE);
  64     tp->map(::visit, (void *) &b);
  65     forward_propagate(tp, FPK_ALL);
  66     fold_all_constants(tp);
  67     proc_dead_code(tp);
  68     proc_unused_syms(tp, TRUE, FALSE);
  69     //unused_end_symtab(tp->scope());
  70 }
  71
  72 void transformer::build(tree_node *root)
  73 {
  74     block::set_proc(tp);
  75
  76     out            = stdout;
  77     indent         = 0;
  78
  79     dumper d(tp, NULL);
  80     d.scan();
  81     for (int i = 0; i < d.nodes.size(); ++i) {
  82         domain_ann *dom = d.nodes[i];
  83         instruction *insn = dom->insn;
  84         nr2insn[insn->number()] = insn;
  85         insn2dom[insn] = dom;
  86     }
  87
  88     tree_node_list *list = scan(tree);
  89
  90     tree_node_list *tnl = ((tree_block*) root)->body();
  91     tnl->clear();
  92     tree_node_list_iter tnli(list);
  93     while (!tnli.is_empty()) {
  94         tnl->append(tnli.step());
  95     }
  96 }
  97
  98 instruction *transformer::scan_id(__isl_keep isl_ast_expr *e)
  99 {
 100         isl_id *id = isl_ast_expr_get_id(e);
 101         var_sym *var = name(id);
 102         isl_id_free(id);
 103         return block(var).make_instruction();
 104 }
 105
 106 instruction *transformer::scan_int(__isl_keep isl_ast_expr *e)
 107 {
 108         isl_val *v;
 109         v = isl_ast_expr_get_val(e);
 110         block b((int) isl_val_get_num_si(v));
 111         isl_val_free(v);
 112         return b.make_instruction();
 113 }
 114
 115 var_sym *transformer::name(__isl_keep isl_id *id)
 116 {
 117         const char *name = isl_id_get_name(id);
 118         map<var_sym *, Param_Iterator *>::iterator gi;
 119
 120         for (gi = sa->vars.begin(); gi != sa->vars.end(); ++gi) {
 121                 if (!strcmp(gi->second->base_name(), name))
 122                         return gi->first;
 123         }
 124
 125         if (it.find(id) == it.end())
 126                 it[id] = tp->symtab()->new_unique_var(type_signed, "c");
 127
 128         return it[id];
 129 }
 130
 131 tree_node_list *transformer::scan_if(__isl_keep isl_ast_node *node)
 132 {
 133         isl_ast_node *then;
 134         isl_ast_expr *cond;
 135
 136         cond = isl_ast_node_if_get_cond(node);
 137         then = isl_ast_node_if_get_then(node);
 138
 139         block code = block::IF(block(scan(cond)), block(scan(then)));
 140
 141         isl_ast_node_free(then);
 142         isl_ast_expr_free(cond);
 143
 144         return code.make_tree_node_list();
 145 }
 146
 147 static bool is_empty_upper_bound(__isl_keep isl_ast_expr *ub)
 148 {
 149         if (isl_ast_expr_get_type(ub) != isl_ast_expr_op)
 150                 return false;
 151         if (isl_ast_expr_get_op_type(ub) != isl_ast_op_min)
 152                 return false;
 153         return isl_ast_expr_get_op_n_arg(ub) == 0;
 154 }
 155
 156 static instruction *subtract_one(instruction *ins)
 157 {
 158         block one(ins);
 159         one.set(block::op(one, bop_sub, 1));
 160         return one.make_instruction();
 161 }
 162
 163 tree_node_list *transformer::scan_for(__isl_keep isl_ast_node *node)
 164 {
 165         isl_ast_expr *cond;
 166         isl_ast_expr *lb, *ub, *inc;
 167         isl_ast_node *body;
 168         enum isl_ast_op_type type;
 169         bool strict;
 170
 171         body = isl_ast_node_for_get_body(node);
 172
 173         if (isl_ast_node_for_is_degenerate(node)) {
 174                 tree_node_list *list;
 175                 isl_ast_expr *it = isl_ast_node_for_get_iterator(node);
 176                 isl_id *id = isl_ast_expr_get_id(it);
 177                 isl_ast_expr *val = isl_ast_node_for_get_init(node);
 178                 block &b = block(name(id)).doasignop(aop_eq, block(scan(val)));
 179                 list = b.make_tree_node_list();
 180                 isl_ast_expr_free(val);
 181                 isl_ast_expr_free(it);
 182                 isl_id_free(id);
 183                 block code = scan(body);
 184                 isl_ast_node_free(body);
 185
 186                 list->append(code.make_tree_node_list());
 187
 188                 return list;
 189         }
 190
 191         cond = isl_ast_node_for_get_cond(node);
 192         assert(isl_ast_expr_get_type(cond) == isl_ast_expr_op);
 193         type = isl_ast_expr_get_op_type(cond);
 194         assert(type == isl_ast_op_le || type == isl_ast_op_lt);
 195         strict = type == isl_ast_op_lt;
 196         ub = isl_ast_expr_get_op_arg(cond, 1);
 197         isl_ast_expr_free(cond);
 198
 199         if (is_empty_upper_bound(ub)) {
 200                 /* If no upper bound, then assume infinite loop */
 201                 /* We create a while loop with a test */
 202                 /* that simply jumps back to the top */
 203                 tree_node_list* list = new tree_node_list();
 204                 label_sym *top, *cnt, *brk;
 205                 top = block::get_proc()->proc_syms()->new_unique_label("L_top");
 206                 cnt = block::get_proc()->proc_syms()->new_unique_label("L_cnt");
 207                 brk = block::get_proc()->proc_syms()->new_unique_label("L_brk");
 208                 block code = scan(body);
 209                 isl_ast_node_free(body);
 210                 tree_instr *ti = new tree_instr(new in_bj(io_jmp, top));
 211                 tree_node_list *tnl = new tree_node_list;
 212                 tnl->append(ti);
 213                 tree_loop *tl = new tree_loop(code.make_tree_node_list(), tnl,
 214                                               cnt, brk, top);
 215                 list->append(tl);
 216                 isl_ast_expr_free(ub);
 217                 return list;
 218         } else {
 219                 isl_ast_expr *it = isl_ast_node_for_get_iterator(node);
 220                 isl_id *id = isl_ast_expr_get_id(it);
 221                 instruction *ub_ins = scan(ub);
 222                 if (strict)
 223                         ub_ins = subtract_one(ub_ins);
 224                 lb = isl_ast_node_for_get_init(node);
 225                 inc = isl_ast_node_for_get_inc(node);
 226                 block code = block::FOR(name(id),
 227                                   scan(lb), ub_ins, scan(inc), scan(body));
 228                 isl_ast_node_free(body);
 229                 isl_ast_expr_free(it);
 230                 isl_id_free(id);
 231                 isl_ast_expr_free(inc);
 232                 isl_ast_expr_free(lb);
 233                 isl_ast_expr_free(ub);
 234                 return code.make_tree_node_list();
 235         }
 236 }
 237
 238 tree_node_list *transformer::scan_substitutions(
 239         __isl_keep isl_ast_expr *subs, domain_ann *dom)
 240 {
 241         int n = isl_ast_expr_get_op_n_arg(subs) - 1;
 242         tree_node_list *list = new tree_node_list();
 243         assert(dom);
 244         for (int i = 0; i < n; ++i) {
 245                 isl_ast_expr *expr;
 246
 247                 expr = isl_ast_expr_get_op_arg(subs, 1 + i);
 248                 assert(tp->symtab()->lookup_var(dom->its[i]->name()) ==
 249                                                                 dom->its[i]);
 250                 block b = block(dom->its[i]).doasignop(aop_eq,
 251                                                         block(scan(expr)));
 252                 list->append(b.make_tree_node_list());
 253                 isl_ast_expr_free(expr);
 254         }
 255         return list;
 256 }
 257
 258 tree_node_list *transformer::scan_user(__isl_keep isl_ast_node *node)
 259 {
 260         pdg::node *p_node;
 261         instruction *insn;
 262         isl_ast_expr *expr, *arg;
 263         isl_id *id;
 264         domain_ann *dom;
 265
 266         expr = isl_ast_node_user_get_expr(node);
 267         arg = isl_ast_expr_get_op_arg(expr, 0);
 268         id = isl_ast_expr_get_id(arg);
 269         p_node = (pdg::node *) isl_id_get_user(id);
 270         isl_id_free(id);
 271         isl_ast_expr_free(arg);
 272
 273         insn = nr2insn[p_node->statement->operation];
 274         dom = insn2dom[insn];
 275
 276         tree_node_list *s = scan_substitutions(expr, dom);
 277         block b_subs(s);
 278         tree_node_list *r = block(b_subs, block(insn)).make_tree_node_list();
 279         delete s;
 280
 281         isl_ast_expr_free(expr);
 282
 283         return r;
 284 }
 285
 286 tree_node_list *transformer::scan(__isl_keep isl_ast_node *node)
 287 {
 288         enum isl_ast_node_type type;
 289
 290         type = isl_ast_node_get_type(node);
 291         switch (type) {
 292         case isl_ast_node_for:
 293                 return scan_for(node);
 294         case isl_ast_node_if:
 295                 return scan_if(node);
 296         case isl_ast_node_block:
 297                 return scan_block(node);
 298         case isl_ast_node_user:
 299                 return scan_user(node);
 300         case isl_ast_node_error:
 301                 assert(0);
 302         }
 303 }
 304
 305 tree_node_list *transformer::scan_block(__isl_keep isl_ast_node *block)
 306 {
 307         tree_node_list *list = new tree_node_list();
 308         isl_ast_node_list *node_list = isl_ast_node_block_get_children(block);
 309         int n = isl_ast_node_list_n_ast_node(node_list);
 310
 311         for (int i = 0; i < n; ++i) {
 312                 isl_ast_node *node;
 313                 node = isl_ast_node_list_get_ast_node(node_list, i);
 314                 list->append(scan(node));
 315                 isl_ast_node_free(node);
 316         }
 317         isl_ast_node_list_free(node_list);
 318
 319         return list;
 320 }
 321
 322 instruction *transformer::scan(__isl_keep isl_ast_expr *e)
 323 {
 324         enum isl_ast_expr_type type;
 325
 326         type = isl_ast_expr_get_type(e);
 327         switch (type) {
 328         case isl_ast_expr_id:
 329                 return scan_id(e);
 330         case isl_ast_expr_op:
 331                 return scan_op(e);
 332         case isl_ast_expr_int:
 333                 return scan_int(e);
 334         default:
 335                 assert(0);
 336         }
 337 }
 338
 339 instruction *transformer::scan_op(__isl_keep isl_ast_expr *e)
 340 {
 341         isl_ast_expr *arg;
 342         int n_arg = isl_ast_expr_get_op_n_arg(e);
 343         enum isl_ast_op_type type = isl_ast_expr_get_op_type(e);
 344         binary_op bop;
 345
 346         if (n_arg == 1) {
 347                 assert(type == isl_ast_op_minus);
 348                 arg = isl_ast_expr_get_op_arg(e, 0);
 349                 block b(block::op(uop_minus, scan(arg)));
 350                 isl_ast_expr_free(arg);
 351                 return b.make_instruction();
 352         }
 353
 354         switch (type) {
 355         case isl_ast_op_le:
 356                 bop = bop_leq;
 357                 break;
 358         case isl_ast_op_ge:
 359                 bop = bop_geq;
 360                 break;
 361         case isl_ast_op_eq:
 362                 bop = bop_eq;
 363                 break;
 364         case isl_ast_op_and:
 365                 bop = bop_land;
 366                 break;
 367         case isl_ast_op_or:
 368                 bop = bop_lor;
 369                 break;
 370         case isl_ast_op_max:
 371                 bop = bop_max;
 372                 break;
 373         case isl_ast_op_min:
 374                 bop = bop_min;
 375                 break;
 376         case isl_ast_op_add:
 377                 bop = bop_add;
 378                 break;
 379         case isl_ast_op_sub:
 380                 bop = bop_sub;
 381                 break;
 382         case isl_ast_op_mul:
 383                 bop = bop_mul;
 384                 break;
 385         case isl_ast_op_pdiv_q:
 386         case isl_ast_op_div:
 387                 bop = bop_div;
 388                 break;
 389         case isl_ast_op_pdiv_r:
 390                 bop = bop_mod;
 391                 break;
 392         case isl_ast_op_fdiv_q:
 393                 bop = bop_divfloor;
 394                 break;
 395         default:
 396                 assert(0);
 397         }
 398
 399         arg = isl_ast_expr_get_op_arg(e, n_arg - 1);
 400         block one(scan(arg));
 401         isl_ast_expr_free(arg);
 402         while (--n_arg) {
 403                 arg = isl_ast_expr_get_op_arg(e, n_arg - 1);
 404                 one.set(block::op(scan(arg), bop, one));
 405                 isl_ast_expr_free(arg);
 406         }
 407         return one.make_instruction();
 408 }