linearize.c

   1 /*
   2  * Linearize - walk the statement tree (but _not_ the expressions)
   3  * to generate a linear version of it and the basic blocks.
   4  *
   5  * NOTE! We're not interested in the actual sub-expressions yet,
   6  * even though they can generate conditional branches and
   7  * subroutine calls. That's all "local" behaviour.
   8  *
   9  * Copyright (C) 2004 Linus Torvalds
  10  */
  11
  12 #include <string.h>
  13 #include <stdarg.h>
  14 #include <stdlib.h>
  15 #include <stdio.h>
  16
  17 #include "parse.h"
  18 #include "expression.h"
  19 #include "linearize.h"
  20
  21 static struct entrypoint *alloc_entrypoint(void)
  22 {
  23         return __alloc_entrypoint(0);
  24 }
  25
  26 static struct basic_block *alloc_basic_block(void)
  27 {
  28         return __alloc_basic_block(0);
  29 }
  30
  31 static void show_bb(struct basic_block *bb)
  32 {
  33         struct statement *stmt;
  34
  35         printf("bb: %p\n", bb);
  36         FOR_EACH_PTR(bb->stmts, stmt) {
  37                 show_statement(stmt);
  38         } END_FOR_EACH_PTR;
  39
  40         if (bb->next) {
  41                 printf("\tgoto .L%p\n", bb->next->bb_target);
  42         } else {
  43                 printf("\tdefault return\n");
  44         }
  45         printf("\n");
  46 }
  47
  48 static void show_entry(struct entrypoint *ep)
  49 {
  50         struct symbol *sym;
  51         struct basic_block *bb;
  52
  53         printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
  54
  55         FOR_EACH_PTR(ep->syms, sym) {
  56                 printf("   sym: %p %s\n", sym, show_ident(sym->ident));
  57         } END_FOR_EACH_PTR;
  58
  59         printf("\n");
  60
  61         FOR_EACH_PTR(ep->bbs, bb) {
  62                 show_bb(bb);
  63         } END_FOR_EACH_PTR;
  64
  65         printf("\n");
  66 }
  67
  68 static struct basic_block * new_basic_block(struct basic_block_list **bbs)
  69 {
  70         struct basic_block *bb = alloc_basic_block();
  71         add_bb(bbs, bb);
  72         return bb;
  73 }
  74
  75 static struct basic_block * linearize_statement(struct symbol_list **syms,
  76         struct basic_block_list **bbs,
  77         struct basic_block *bb,
  78         struct statement *stmt)
  79 {
  80         if (!stmt)
  81                 return bb;
  82
  83         switch (stmt->type) {
  84         case STMT_NONE:
  85                 break;
  86
  87         case STMT_ASM:
  88         case STMT_EXPRESSION:
  89                 add_statement(&bb->stmts, stmt);
  90                 break;
  91
  92         case STMT_RETURN:
  93                 add_statement(&bb->stmts, stmt);
  94                 bb = new_basic_block(bbs);
  95                 break;
  96
  97         case STMT_CASE:
  98         case STMT_LABEL: {
  99                 struct basic_block *new_bb = new_basic_block(bbs);
 100                 struct symbol *sym = stmt->label_identifier;
 101
 102                 bb->next = sym;
 103                 sym->bb_target = new_bb;
 104
 105                 bb = linearize_statement(syms, bbs, new_bb, stmt->label_statement);
 106                 break;
 107         }
 108
 109         case STMT_GOTO: {
 110                 struct basic_block *new_bb = new_basic_block(bbs);
 111                 struct symbol *sym = stmt->goto_label;
 112
 113                 bb->next = sym;
 114                 bb = new_bb;
 115                 break;
 116         }
 117
 118         case STMT_COMPOUND: {
 119                 struct statement *s;
 120                 concat_symbol_list(stmt->syms, syms);
 121                 FOR_EACH_PTR(stmt->stmts, s) {
 122                         bb = linearize_statement(syms, bbs, bb, s);
 123                 } END_FOR_EACH_PTR;
 124                 break;
 125         }
 126
 127         /*
 128          * This could take 'likely/unlikely' into account, and
 129          * switch the arms around appropriately..
 130          */
 131         case STMT_IF: {
 132                 struct symbol *target = alloc_symbol(stmt->pos, SYM_LABEL);
 133                 struct statement *goto_bb = alloc_statement(stmt->pos, STMT_CONDFALSE);
 134                 struct basic_block *last_bb;
 135
 136                 add_statement(&bb->stmts, goto_bb);
 137                 last_bb = new_basic_block(bbs);
 138
 139                 goto_bb->bb_conditional = stmt->if_conditional;
 140                 goto_bb->bb_target = target;
 141
 142                 bb = linearize_statement(syms, bbs, bb, stmt->if_true);
 143                 bb->next = target;
 144                 target->bb_target = last_bb;
 145
 146                 if (stmt->if_false) {
 147                         struct symbol *else_target = alloc_symbol(stmt->pos, SYM_LABEL);
 148                         struct basic_block *else_bb = new_basic_block(bbs);
 149
 150                         else_target->bb_target = else_bb;
 151                         else_bb = linearize_statement(syms, bbs, else_bb, stmt->if_false);
 152                         goto_bb->bb_target = else_target;
 153                         else_bb->next = target;
 154                 }
 155
 156                 bb = last_bb;
 157                 break;
 158         }
 159
 160         case STMT_SWITCH:
 161                 add_statement(&bb->stmts, stmt);
 162                 bb = new_basic_block(bbs);
 163                 break;
 164
 165         case STMT_ITERATOR: {
 166                 struct statement  *pre_statement = stmt->iterator_pre_statement;
 167                 struct expression *pre_condition = stmt->iterator_pre_condition;
 168                 struct statement  *statement = stmt->iterator_statement;
 169                 struct statement  *post_statement = stmt->iterator_post_statement;
 170                 struct expression *post_condition = stmt->iterator_post_condition;
 171                 struct symbol *loop_top = NULL, *loop_bottom = NULL;
 172
 173                 concat_symbol_list(stmt->iterator_syms, syms);
 174                 bb = linearize_statement(syms, bbs, bb, pre_statement);
 175                 if (pre_condition) {
 176                         if (pre_condition->type == EXPR_VALUE) {
 177                                 if (!pre_condition->value) {
 178                                         loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 179                                         bb->next = loop_bottom;
 180                                         bb = new_basic_block(bbs);
 181                                 }
 182                         } else {
 183                                 struct statement *pre_cond = alloc_statement(stmt->pos, STMT_CONDFALSE);
 184                                 loop_bottom = alloc_symbol(stmt->pos, SYM_LABEL);
 185                                 pre_cond->bb_conditional = pre_condition;
 186                                 pre_cond->bb_target = loop_bottom;
 187                                 add_statement(&bb->stmts, pre_cond);
 188                         }
 189                 }
 190
 191                 if (!post_condition || post_condition->type != EXPR_VALUE || post_condition->value) {
 192                         struct basic_block *loop = new_basic_block(bbs);
 193                         loop_top = alloc_symbol(stmt->pos, SYM_LABEL);
 194                         loop_top->bb_target = loop;
 195                         bb->next = loop_top;
 196                         bb = loop;
 197                 }
 198
 199                 bb = linearize_statement(syms, bbs, bb, statement);
 200
 201                 if (stmt->iterator_continue->used) {
 202                         struct basic_block *cont = new_basic_block(bbs);
 203                         stmt->iterator_continue->bb_target = cont;
 204                         bb->next = stmt->iterator_continue;
 205                         bb = cont;
 206                 }
 207
 208                 bb = linearize_statement(syms, bbs, bb, post_statement);
 209
 210                 if (!post_condition) {
 211                         bb->next = loop_top;
 212                 } else {
 213                         if (post_condition->type != EXPR_VALUE || post_condition->value) {
 214                                 struct statement *post_cond = alloc_statement(stmt->pos, STMT_CONDTRUE);
 215                                 post_cond->bb_conditional = post_condition;
 216                                 post_cond->bb_target = loop_top;
 217                                 add_statement(&bb->stmts, post_cond);
 218                         }
 219                 }
 220
 221                 if (stmt->iterator_break->used) {
 222                         struct basic_block *brk = new_basic_block(bbs);
 223                         stmt->iterator_break->bb_target = brk;
 224                         bb->next = stmt->iterator_break;
 225                         bb = brk;
 226                 }
 227                 break;
 228         }
 229
 230         default:
 231                 break;
 232         }
 233         return bb;
 234 }
 235
 236 void linearize_symbol(struct symbol *sym)
 237 {
 238         struct symbol *base_type;
 239
 240         if (!sym)
 241                 return;
 242         base_type = sym->ctype.base_type;
 243         if (!base_type)
 244                 return;
 245         if (base_type->type == SYM_FN) {
 246                 if (base_type->stmt) {
 247                         struct entrypoint *ep = alloc_entrypoint();
 248                         struct basic_block *bb;
 249
 250                         ep->name = sym;
 251                         bb = new_basic_block(&ep->bbs);
 252                         concat_symbol_list(base_type->arguments, &ep->syms);
 253                         linearize_statement(&ep->syms, &ep->bbs, bb, base_type->stmt);
 254                         show_entry(ep);
 255                 }
 256         }
 257 }